[Haskell-beginners] Re: foldl' vs seq

[Ertugrul Soeylemez]

Gabi <bugspynet at gmail.com> wrote:

> Hi Stephen,
> Thanks for the answer. Now I got confused :)
>
> 1. What is seq used for if it doesn't force strictness ?
> 2. Why the accumulator is important ? In other words why the following
> is much slower ? Isn't it RT too ?
>
> slowSum :: [Integer] -> Integer
> slowSum[] = 0
> slowSum (x:xs) = x `seq` x + slowSum xs

Hello Gabi,

The seq function may not behave as you expect it to.  The following GHCi
session may help you understand this:

  Prelude> const 3 (seq undefined 0)
  3
  Prelude> snd (seq undefined 0, 1)
  1
  Prelude> fst (seq undefined 0, 1)
  *** Exception: Prelude.undefined

When the result of 'seq x y' is demanded, x is evaluated and then y is
returned as that result.  In the above session the first two expressions
never evaluate the seq call.  Haskell is lazy, so if you demand only the
second value of a tuple, the first one is never evaluated, even if it
contains 'seq x y'.  However, _if_ it is evaluated, it will evaluate x
first, then return y.

Your statement, x `seq` x + slowSum xs, can be rewritten in the
following way, seq x (x + slowSum xs), which makes clearer what it
means:  Upon evaluating x + slowSum xs, the value of x should be
evaluated.  In other words, your function builds the following result
thunk:

  slowSum [1,2,3] = 1 + 2 + 3 + 0

instead of:

  slowSum [1,2,3] = THUNK + THUNK + THUNK + 0

But it still builds a thunk, which will have to actually perform all the
additions.  Why?  Because nothing demands that sum until after all those
recursive calls return.  You are right in that a 'seq' is needed
somewhere, but not where you put it.  In fact the slowSum function
cannot be optimized any further, because it is not tail-recursive:

     slowSum [1,2,3]
  => 1 + slowSum [2,3]

Using prefix notation shows why the recursive call to slowSum is not the
last function call and hence is no tail recursion:

  (+) 1 (slowSum [2,3])

The problem of non-tail recursion is that the recursive calls have no
access to the "current result".  You cannot force the addition from
slowSum, because it's out of scope.

If you introduce an accumulation parameter, things change:

  fastSum :: Num a => a -> [a] -> a
  fastSum s []     = s
  fastSum s (x:xs) = fastSum (s+x) xs

Read it like:  'fastSum s xs' is the sum of the elements of xs plus the
value of s.  Reading it that way the code is self-explanatory, and
clearly it is tail-recursive, giving the function full access to the
current intermediary result (named s).  It builds the following result:

     fastSum 0 [1,2,3]
  => fastSum (0 + THUNK) [2,3]
  => fastSum (0 + THUNK + THUNK) [3]
  => fastSum (0 + THUNK + THUNK + THUNK) []
  => 0 + THUNK + THUNK + THUNK

Well, now it is tail-recursive, so it doesn't eat stack space anymore,
but it still builds that result expression instead of just giving the
end result.  This is where seq comes into play.  Now that you have
access to the intermediary result, you can force it to be evaluated
along the way:

  superFastSum :: Num a => a -> [a] -> a
  superFastSum s []     = s
  superFastSum s (x:xs) = s `seq` superFastSum (s+x) xs

Note how semantics have changed now:

     superFastSum 0 [1,2,3]
  => 0     `seq` superFastSum (0+1) [2,3]
  =>             superFastSum (0+1) [2,3]
  => (0+1) `seq` superFastSum ((0+1)+2) [3]
  =>             superFastSum (1+2) [3]
  => (1+2) `seq` superFastSum ((1+2)+3) []
  =>             superFastSum (3+3) []
  =>             3+3

The result of superFastSum on a non-empty list depends on a recursive
call to itself, but it clearly states (through seq) that _before_ that
call is evaluated, the value of s is evaluated.  So each time it
attempts to build a result expression, that expression is immediately
reduced to a value, to which the next list element is added.

The foldl' function can be used to encode such a recursion pattern
conveniently.  It's just like the superFastSum function, but takes an
arbitrary accumulation function instead of (+):

  import Data.List

  foldl' :: (a -> b -> a) -> a -> [b] -> a
  foldl' f z []     = z
  foldl' f z (x:xs) = z `seq` foldl' f (f z x) xs

  superFastSum     = foldl' (+) 0
  superFastProduct = foldl' (*) 1
  superFastLength  = foldl' (\x y -> x + 1) 0

I hope that helps.


Supplemental note #1:  Haskell compilers generally don't do common
subexpression elimination (CSE), because that may change language
semantics.  The following code will not behave as you may expect it to:

  f x `seq` print (f x)

With CSE in mind, you would expect the seq not to change anything and
just print the result, but this is wrong.  In fact it will be twice as
slow!  The reason is that to the compiler the first 'f x' is not the
same as the second 'f x'.  If you want them to be the same, you need to
make this explicit by giving them a common name:

  let y = f x in y `seq` print y

This is called memoizing and will work as expected, i.e. the seq will
not slow things down.  You can avoid some lets and wheres using the
strict function application operator:

  print $! f x


Supplemental note #2:  A better, memoizing foldl' implementation:

  foldl' :: (a -> b -> a) -> a -> [b] -> a
  foldl' f z []     = z
  foldl' f z (x:xs) =
    let r = f z x
    in r `seq` foldl' f r xs


Supplemental note #3:  I noticed that recent versions of GHC are smart
enough to know where it makes no semantic difference to force certain
calculations.  That means you can write the implementations of
superFastSum and foldl' without seq:

  superFastSumGHC = fastSum

  foldl' = foldl

However, for compatibility reasons you should still use seq.


Greets
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/