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

[Twan van Laarhoven]

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