On Tuesday 14 September 2010 23:26:47, Klaus Gy wrote:
Hi!
Inspred from the discussion http://www.haskell.org/pipermail/beginners/2010-February/003396.html , I just try to understand the seq function a bit better. When I compare these two functions:
firstSum :: Num a => a -> [a] -> a firstSum s [] = s firstSum s (x:xs) = seq help (firstSum help xs) where help = x + s
secondSum :: Num a => [a] -> a secondSum [] = 0 secondSum (x:xs) = seq help (x + help) where help = secondSum xs
What should be the difference?
That depends on the types at which you use them. For types like Int, Integer, Double, Float, Word, ..., evaluation to WHNF, what seq does, is complete evaluation. So for these types, firstSum keeps a completely evaluated accumulation parameter, runs through the list and delivers the result when the end is reached. It corresponds closely to int firstSum(int s, intList xs){ if (empty(xs)) return s; s += xs.head; return firstSum(s,xs.tail); } where an intList has an int field `head', a pointer `tail' to its tail and empty(xs) would be (xs == NULL) in C, (xs == null) in Java. Since that function is tail-recursive, it doesn't need to allocate new stack-frames and thus can run in constant (stack) space (if the Haskell version doesn't it's a bug, in C, you'd probably have to tell gcc to -foptimize-sibling-calls, then it should do fine, in Java, I don't know of a VM that does tail-call optimisation - but then, I don't know much about Java). So for these, firstSum is well behaved, pretty much the best you can get. secondSum is different, the seq there says evaluate the sum of the tail and add that to x. Of course, for Int &c, to add x to the sum of the tail, the latter has to be evaluated anyway, so the seq is rather pointless. secondSum is almost equivalent to thirdSum :: Num a => [a] -> a thirdSum = foldr (+) 0 and it more or less corresponds to the imperative version int secondSum(intList xs){ if (empty(xs)) return 0; int tailsum = secondSum(xs.tail); return (xs.head + tailsum); } This is not tail-recursive, so it needs O(length xs) stack and marches twice through the list, so to say, once to the end, building the chain of recursive calls and back to the front adding. So for Int &c, firstSum is vastly superior in space behaviour (always uses constant stack space and if the list isn't held in memory by other references, also constant heap space). Things become different when you work with lazy number types. firstSum, being tail-recursive, can't deliver anything until it has reached the end of the list. Keeping the accumulator evaluated to WHNF doesn't mean much for lazy types, so the accumulator may well build up huge thunks (but, for lazy types, evaluating a huge thunk can still run in small stack space, so that's not necessarily catastrophic). secondSum, on the other hand, can start delivering before the list has been completely traversed (depends on the behaviour of (+)). But if it can, it can probably do even better if you don't seq on the sum of the tail, so for those types, thirdSum would be the better option. Example for lazy number type: data Peano = Zero | Succ Peano deriving (Eq, Show) instance Num Peano where Zero + n = n (Succ m) + n = Succ (m + n) -- other methods fromInteger n | n <= 0 = Zero | otherwise = Succ (fromInteger (n-1)) instance Ord Peano where compare Zero Zero = EQ compare Zero _ = LT compare _ Zero = GT compare (Succ m) (Succ n) = compare m n Now try list :: [Peano] list = 4:replicate (10^5) 0 thirdSum list > 3 secondSum list > 3 firstSum list > 3 and then increase the length of the list (10^6, 10^7 instead of 10^5).
In my opinion both functions do not return a complete unevaluated thunk (secondSum returns a thunk of the form (THUNK + b) where THUNK contains a single numeral value). But it seems to me that the first function computes the output somehow linear in the sense that it does just a set of substitutions while the second functions has to create a tree to handle all the recursive calls of seq (sorry, my terminology is for sure a bit poor).
Well, it's a flat tree, it's secondSum (x:xs) = case secondSum xs of s -> x+s where the `case' is supposed to have core semantics, i.e. evaluates the expression to WHNF. So secondSum [1,2,3] ~> case secondSum [2,3] of s1 -> 1 + s1 ~> case case secondSum [3] of { s2 -> 2 + s2 } of s1 -> 1 + s1 ~> case case case secondSum [] of { s3 -> 3 + s3 } of { s2 -> 2 + s2 } of s1 -> 1 + s1 ~> case case case 0 of { s3 -> 3 + s3 } of { s2 -> 2 + s2} of s1 -> 1 + s1 ~> case case 3 of { s2 -> 2 + s2 } of s1 -> 1 + s1 ~> case 5 of s1 -> 1 + 5 ~> 6
So I would say the first function delivers a better performance. (In the discussion I mentioned, the second function was not discussed in this form with the seq implementation). Am I right with my thoughts?
Pretty much.
Thanks, fweth