CODEWITHSUNDEEP
haskelloptimizationghctail-recursionfold
hanan
hanan

Reputation: 1890

Is foldR Tail Recursive in Haskell?

I'm new to Haskell and reading Haskell from first principles, in chapter Folds page 384 I have came across FoldR and seems like its not tail recursive

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

1- can we make it tail recursive ?

2- and do it will be optimized ?

Upvotes: 4

Views: 596

Answers (4)

Mark Saving
Mark Saving

Reputation: 1797

foldr is not tail recursive itself, but depending on f, it is possible that foldr f is tail recursive. Tail recursion in Haskell is quite subtle because of lazy evaluation.

For example, consider f = (&&). In this case, we have

foldr (&&) acc lst =
   case lst of
      [] -> acc
      (x:xs) -> x && foldr (&&) acc xs
= 
   case lst of
      [] -> acc
      (x:xs) -> if x
                then foldr (&&) acc xs
                else False
=
   case lst of
      [] -> acc
      (x:xs) -> case x of
         True -> foldr (&&) acc xs
         False -> False

Note that in this case, we clearly see that foldr (&&) is tail-recursive. In fact, foldr (||) is also tail recursive. Note that the fact that foldr (&&) is tail recursive is fundamentally because of laziness. If it weren't for laziness, we would have to evaluate foldr (&&) acc xs before substituting the result into x && foldr (&&) acc xs. But because of laziness, we evaluate x first and only then determine whether we need to call foldr (&&) acc xs, and whenever we make that call, it's a tail call.

However, in most cases, foldr f will not be a tail recursive function. In particular, foldr ((+) :: Int -> Int -> Int) is not tail recursive.

Upvotes: 2

Marco Benelli
Marco Benelli

Reputation: 51

foldr is not tail recursive. Sometime it is called the true "recursive" fold while fold left is "iterative" (because of tail recursion it is equivalent to iteration).

Please note that in Haskell, because of laziness, also foldl do not guarantee constant space, that is why it exists foldl'

Upvotes: 2

dfeuer
dfeuer

Reputation: 48611

foldr is not tail recursive ... but it can be used to write functions that process lists in constant space. chi already pointed out that it can implement and efficiently. Here's how it can implement an efficient function for summing a list:

mySum :: Num a => [a] -> a
mySum xs = foldr go id xs 0
  where
    go x r acc = r $! x + acc

How's this work? Consider mySum [1,2,3]. This expands to

foldr go id [1,2,3] 0
==> -- definition of foldr
go 1 (foldr go id [2,3]) 0
==> -- definition of go
foldr go id [2,3] $! 1 + 0
==> -- strict application
foldr go id [2,3] 1

We've reduced the list size by one, and haven't accumulated anything on the "stack". The same process repeats till we get

foldr go id [] 6
==> definition of foldr
id 6
==> definition of id
6

Note: if this code is compiled by GHC with optimizations enabled (-O or -O2), then it will actually transform it into blazing-fast tail-recursive code without any further assistance from you. But even unoptimized, it will work okay and not burn up a bunch of memory/stack.

Upvotes: 5

chi
chi

Reputation: 116174

In a lazy language like Haskell, tail recursion is often a bad idea. This is one of these cases.

We might attempt to make foldr tail recursive by e.g. starting with a reverse (which is also doable in a tail-recursive way), and then accumulating the foldr result step by step, in a tail recursive way. However, that would break the foldr semantics.

With the standard foldr, we have e.g.

foldr (\_ _ -> k1) k2 (x:xs) = k1

no matter what xs is, including a bottom value like undefined or an infinite list like [0..]. Further, when xs is a finite but long list, the code above is also efficient, since it stops the computation immediately without scanning the whole list.

As a more practical example,

and :: [Bool] -> Bool
and = foldr (&&) True

makes and xs return False as soon as some element of xs evaluates to False, without scanning the rest of the list.

Concluding, turning foldr into a tail recursive function would:

  • change the semantics when dealing with partially-defined lists (1:2:undefined) or infinite ones ([0..]);
  • be less efficient on finite length lists, which would always have to be completely scanned, even when there is no need to.

Upvotes: 8

Related Questions