[Haskell] Newbie : How come that cyclic recursive lists are efficient ?

[Francis Girard]

Thank you,

I understand the point.

But I can't help thinking that the distinction between "being" a list of 
integers and "being" a function that "returns" a list of integers (without 
arguments) is not always clear in FP ... since there is not really such a 
thing as returning a value in declarative programming, neither in 
mathematical thinking.

Thank you

Francis Girard
FRANCE

Le lundi 24 Janvier 2005 18:11, Graham Klyne a écrit :
> Notice that 'hamming' *is* a list of integers, not a function to produce
> them:
>
>    hamming :: [Integer]
>
> Thus, the "magic" here is that you can define this list as a value, without
> having to actually evaluate any element until it's needed, either by direct
> reference from another function, or indirectly by the recursive definition
> to obtain a value directly required.  But once evaluated, the deferred
> evaluation is replaced by the resulting value.
>
> This is the power of lazy evaluation.  Even  fixed values (as opposed to
> function calls) aren't evaluated until they're needed.
>
> #g
> --
>
> At 10:38 24/01/05 +0100, Francis Girard wrote:
> >Hi,
> >
> >The classical Hamming problem have the following solution in Haskell :
> >
> >*** BEGIN SNAP
> >-- hamming.hs
> >
> >-- Merges two infinite lists
> >merge :: (Ord a) => [a] -> [a] -> [a]
> >merge (x:xs)(y:ys)
> >
> >   | x == y    = x : merge xs ys
> >   | x <  y    = x : merge xs (y:ys)
> >   | otherwise = y : merge (x:xs) ys
> >
> >-- Lazily produce the hamming sequence
> >hamming :: [Integer]
> >hamming
> >   = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*)
> > hamming))
> >*** END SNAP
> >
> >I just love these algorithms that run after their tail (they make my brain
> >melt) but I don't know how is it that they are efficient.
> >
> >Here, the hamming recursively calls itself three times. For this algorithm
> > to be efficient, the Haskell system, somehow, has to "remember" the
> > already generated sequence THROUGH RECURSION (i.e. not only intermediate
> > "local" results) otherwise it would end up regenerating the beginning of
> > the sequence over and over again.
> >
> >Obviously, Haskell does remember what had already been generated THROUGH
> >RECURSION since executing the program with GHCI runs quite smoothly and
> >responsively.
> >
> >That Haskell manages to do that is for me "magnifique". But I need to know
> >(if
> >only a little) about how it achieves this in order to know what I, as a
> >lambda programmer, can do, and how to compute the Big-Oh complexity of the
> >algorithm.
> >
> >Thank you,
> >
> >Francis Girard
> >FRANCE
> >
> >_______________________________________________
> >Haskell mailing list
> >Haskell at haskell.org
> >http://www.haskell.org/mailman/listinfo/haskell
>
> ------------
> Graham Klyne
> For email:
> http://www.ninebynine.org/#Contact
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell