## Partition a list numerically?

on June 9, 2009 - 8:13pm

Over on the Haskell Cafe mailing list, the topic of which of the following two definitions was better came up:

```buildPartitions xs ns = zipWith take ns . init \$ scanl (flip drop) xs ns
```

...or...

```takeList :: [Int] -> [a] -> [[a]]
takeList [] _         =  []
takeList _ []         =  []
takeList (n : ns) xs  =  head : takeList ns tail
where (head, tail) = splitAt n xs
```

...with various parties declaring the first example as "too smart", and others claiming that the second example is newbie level code. Well I'm much too lazy to try to reason out what those snippets might do at a glance. But the type signature was a pretty big hint as to what the intent was. So I fired up GHCi and played around with a few examples, and it was easy to see that the functions take a list of numbers, and a list of other things, and partitions the list of other things into chunks which have a length equal the numbers in the first list. For example: `(takeList [1,2,3] "abcdef")` evaluates to `["a","bc","def"]`.

Further down in the thread, other solutions are offered, and the following State Monad soltion was proposed:

```takeList = evalState . map (State . splitAt)
```

...while the last example seemed clever, I couldn't help but think that there was a better way to write that function. My first attempt in Prolog was:

```partition(Xs,Ls,Ps) :- maplist(length,Ps,Ls), flatten(Ps,Xs).
```

...that has a nice declarative reading to me, essentially an executable specification. (If only I could write a Haskell type signature like that.) That is saying that Ps is the result of partitioning Xs into lists of lengths in Ls if the length of every list in Ps is equal to the corresponding element in Ls, and if you can flatten the nested structure in Ps, and get your original list Xs.

And it also has the advantage of a nice operational reading. To construct the partitioned list Ps, first make a list of lists, whose internal lengths are the members of Ls, and then run the 'flatten' predicate backwards to fill in the elements from the original list Xs.

As I starting thinking about the problem more, it occured to me that this is similar to a parsing problem. So whipping up a Definite Clause Grammer solution:

```p([],[]) --> [].
p([N|Ns],[X|Xs]) --> {length(X,N)}, X, p(Ns,Xs).
```

```tL3 ns = runParser (sequence (map (flip count anyToken) ns)) () ""
```

...and a similar regex subroutine in Perl:

```sub partition { (my \$str, my @ns) = @_;
my \$r = join "", map "(.{\$_})", @ns;
return \$str =~ /\$r/;                }
```

I also tried a straightforward versions in Lisp:

```(defun part (ns xs)
(loop for n in ns collect (loop repeat n collect (pop xs))))
```

...and a fairly polytypic/generic C++ version:

```template <class Out, class F, class N> Out part(N ns, F f)
{
Out out;
typename F::const_iterator xs = f.begin();
for(typename N::const_iterator it = ns.begin();
it != ns.end(); ++it)
{
F tmp;
copy(xs,xs+*it,back_inserter(tmp));
xs+=*it;
out.push_back(tmp);
}
return out;
}
```

...which has the advantage of working with different container types, rather than just working with lists, like most of other versions. And then I tried many other variation on a theme in Haskell...

```tL4 ns xs = take (length ns) \$ tail \$ map (fst.snd) \$ iterate (\(f:fs,(_,s)) -> (fs, splitAt f s)) (ns,([],xs))

unfold1 p f g x =
if p x
then [f x]
else f x : unfold1 p f g (g x)

tL5 ns xs = tail \$ unfold1
(null.fst)
(fst.snd)
(\ (f:fs,(_,s)) -> (fs, splitAt f s))
(ns,([],xs))

tL6 ns xs = (map.map) snd \$ groupBy (\a b -> (fst a < fst b)) (zip ps xs)
where ps = concat \$ map (enumFromTo 1) ns

tL7 ns xs = rmap (zipWith section pos ns) xs
where pos = (scanl (+) 0 ns)
section n m xs = take m \$ drop n xs
rmap [] _ = []
rmap (f:fs) x = f x : rmap fs x

```

After looking at those Haskell functions, I starting thinking about the newbie
version again. I think part of problem with it is the poor names. Changing
just one name helps out:

```partition [] _         =  []
partition _ []         =  []
partition (n : ns) xs  =  chunk_of_length_n : partition ns rest
where (chunk_of_length_n, rest) = splitAt n xs
```

...but I like the following even more:

```partition (n : ns) xs  =  (take n xs) : partition ns (drop n xs)
partition _ _          =  []
```

...which has less visual clutter, and doesn't involve scanning around to find
auxillary definitions, and puts the most important part up front. But what I
would really like to write in a functional language would be something like:

$\120dpi partition [n_1,\cdots] [a_1,\cdots] = [[\underbrace{a_1,\cdots}_{n_1}],\cdots]$

...which is beautiful, but it is not obvious how I would implement that. I
think I could almost implement the following in Prolog:

```partition([N, ...],[A, ...],[[A, ...], ...]) :- length([A, ...], N).
```

...I guess I should start working on how to transform that unambiguously.

I don't know if this function has any real world uses, but I'm not all that fond of most of those solutions. Are there any better ones out there, in other languages?