* Frodo Chao <frodogr...@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/ _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users