Tail recursion (87)

37 Name: #!/usr/bin/anonymous : 2006-03-08 06:41 ID:Wr4EVlhE

Wait a minute.

foldl is iterative in haskell. foldr is recursive.

Can anyone show me a way to do foldr iteratively?

39 Name: #!/usr/bin/anonymous : 2006-03-08 17:41 ID:qq6fgBY7

>>37

foldr f z ls = foldl (flip f) z (reverse ls)

For reference, flip and reverse are defined as:

flip f x y = f y x
reverse = foldl (flip (:)) []

40 Name: #!/usr/bin/anonymous : 2006-03-08 19:54 ID:Wr4EVlhE

Both foldl and foldr in the Prelude is O(N) time. foldl is O(1) space; foldr is O(N) space.

>>39
You reversed a list, which takes O(N) time and space. Then did foldl on it which takes O(N) time, O(1) space.

The foldr in the Prelude goes forward in the list, creating a huge function, which is O(N) time and space. Then it goes backwards to simplify the function, which takes O(N) time.

Your foldr is basically the same as the one in the Prelude. The difference is that yours has two list and it traverses through the both lists once. The Prelude's has one list and a huge function. It traverses through the list and simplifies the function. I don't know what goes on in the compiler.

Return Entire thread Last 50 posts
This thread has been closed. You cannot post in this thread any longer.