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

wren ng thornton wren at freegeek.org
Sat Jun 20 22:26:54 EDT 2009

```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
```