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/
More information about the Glasgow-haskell-users
mailing list