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@haskell.org http://www.haskell.org/mailman/listinfo/haskell
------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell