# foldr oddity

Roman Cheplyaka roma at ro-che.info
Wed Oct 12 09:43:10 CEST 2011

```* 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/

```