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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
