foldr oddity

[Roman Cheplyaka]

* Frodo Chao <frodogreat at gmail.com> [2011-10-12 10:45:04+0800]
> Hi,
> 
> I came upon this when playing with foldr and filter. Compare the two
> definitions:
> 
> testr  n = foldr (\x y -> x && y) True [t | (_, t) <- zip [1 .. n] [True,
> True ..]]
> testr' n = foldr (\x y -> y && x) True [t | (_, t) <- zip [1 .. n] [True,
> True ..]]
> 
> I tried these functions on ghci (The Glorious Glasgow Haskell Compilation
> System, version 7.0.3), and get the following results (with :set +s):
> 
> testr 1000000 => True
> (0.01 secs, 7920832 bytes)
> testr' 1000000 => True
> (8.72 secs, 446585344 bytes)
> 
> This bizarre (at least to me) behavior also applies to ||. Should I mind the
> orderings of the parameters (especially the accumulator) in the function
> passed to foldr?

The definition of foldr is (equivalent to)

  foldr f a [] = a
  foldr f a (x:xs) = f x (foldr f a xs)

Thus, in testr you invoke

  foldr (&&) a [True, True ..] = True && foldr (&&) a [True, True ..]

Now, && is

  True  && x =  x
  False && _ =  False

So,
  
  True && foldr (&&) a [True, True ..]

is transformed to

  foldr (&&) a [True, True ..]

(with smaller list of True's, of course). 

You see that execution is tail-recursive here. You chop off the head
of the list, process it and then only care about the rest of the list.

In testr', however, && pattern-matches on the "a" argument to foldr. Its
evaluation requires the whole tail of the list to be traversed, so it's
not tail-recursive.

-- 
Roman I. Cheplyaka :: http://ro-che.info/