# Add 'subsequences' and 'permutations' to Data.List (ticket #1990)

Twan van Laarhoven twanvl at gmail.com
Mon Dec 24 00:58:05 EST 2007

```Twan van Laarhoven wrote:
>   permutations8b xs = xs : newPerms xs []
>     where
>      newPerms []     is = []
>      newPerms (t:ts) is = foldr (interleave id) (newPerms ts (t:is))
>                                 (permutations8b is)
>       where interleave f []         r = r
>             interleave f yys@(y:ys) r = f (t:yys++ts)
>                                        : interleave (f . (y:)) ys r

Replacing interleave with

interleave xs r = snd \$ interleave' id xs r
interleave' f []      r = (ts, r)
interleave' f y(y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
in  (y:us, f (t:y:us) : zs)

Gets rid of the (++). I call this version 8c. This has the run times:

permuations8c, permutations3 in recursion    1.969 sec
permuations8c, permutations8c in recursion   2.094 sec

The difference between these two variants is quite small, not worth the
effort in my opinion. This is also getting quite close to the optimal
non-lazy version (permutations3, 1.625 sec).

Yitzchak Gale wrote:
> So when we subtract out the control, satisfying the consistency
> property increases run time by at least a factor of 3.

What exactly are you calculating here? Subtracting the control doesn't make
sense. You are comparing apples to oranges. What if permutations1, say 1.1*
were almost as fast as the control, while permutations2 takes 1.2*. Would
you call permutations2 twice as slow? What if the control were
permutations0, the fastest possible permutations function. How can
permutations2 be twice as slow as permutations1, while it is only 1.2 times
as slow as the fastest permutations function?

> The property is nice, but is it worth that penalty?
> I'm not sure, I'd be interested in hearing other people's
> opinions.

It is not so much about that property, more about the lazyness it allows.
Permutations should give as many results as possible. This means that:

map (take n) . take (factorial n) \$ permutations ([1..n] ++ undefined)

should not give an error. Since 'undefined' is not inspected the function
can not depend on it, which gives the necessary (but not sufficient) condition:

map (take n) . take (factorial n) \$ permutations [1..]) == permutations
[1..n]

I think lazyness is very important in the standard library. If you want
things to be strict, why are you programming in Haskell? :)

Also, the constant-factor of 'permutations' hardly matters. Any program that
does something interesting will be doing more for each permutation than just
summing numbers. If you replace the trivial 'map sum' with something
slightly more complicated, which permutations function you used is not going
to matter much.

Twan
```