[Haskell-cafe] Re: Need some help with an infinite list

[wren ng thornton]

Thomas Hartman wrote:
> could someone explain sharing?
> 
> In the code below, allstrings2 is 6X as fast as allstrings. I assume
> because of sharing, but I don't intuitively see a reason why.
> 
> can someone give me some pointers, perhaps using debug.trace or other
> tools (profiling?) to show where the first version is being
> inefficient?
> 
> 
> ***********
> 
> letters = ['a'..'z']
> 
> strings 0 = [""]
> strings n = [ c : s | c <- letters, s <-  strings (n-1) x ]
> 
> allstrings = concat $ map strings [1..]
> 
> allstrings2 = let sss = [""] : [ [ c:s | c <- letters, s <- ss ] | ss <- sss ]
>               in concat $ tail sss


It's a dynamic-programming problem. Let's reword this in terms of fibonnaci:

     fibs = map fib [0..]
         where
         fib 0 = 0
         fib 1 = 1
         fib n = fib (n-1) + fib (n-2)

This is essentially what allstrings is doing. We have a basic function 
fib/strings and we use it to "count down" from our seed input to the 
value we want. But, because fib/strings is a pure function, it will 
always give equivalent output for the same input, and so once we hit 
some query we've answered before we'd like to just stop. But this 
version won't stop, it'll count all the way down to the bottom.

Haskell doesn't automatically memoize functions, so it's a key point 
that the values are only "equivalent". With allstrings2 we do 
memoization and take it a step further to return the "identical" answer, 
since we keep a copy of the answers we've given out before. The fibs 
variation is:

     fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Because we're defining fibs recursively in terms of itself, to get the 
next element of the stream we only need to keep track of the previous 
two answers we've given out. Similarly for allstrings2 because sss is 
defined in terms of itself it's always producing elements one step 
before it needs them. More particularly, because the recursion has 
"already been done" producing the next element is just a matter of 
applying (+) or applying [ c:s | c <- letters, s <- ss ] and we don't 
need to repeat the recursion.

-- 
Live well,
~wren