Is foldR Tail Recursive in Haskell?

3
votes

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 ?

4
haskelloptimizationghctail-recursionfold
Not sure why folks are downvoting, as it's a perfectly reasonable question. But, as the answers have correctly pointed out, "tail recursion" isn't really that relevant in Haskell. You're more worried about storage space for thunks (which is the big reason foldl is objectively worse than foldl', for instance, despite it being possible to implement both tail recursively in a straightforward way. - Silvio Mayolo
Don't know either why this was downvoted - and I don't think it's really a duplicate of the performance question given. IMHO this question and the answers are good and stand on their own so I'd like to vote to reopen this. Sadly that would instant-reopen it and I don't want to turn this into close/reopen war so what do others think? - Random Dev
@Carsten the answers do seem rather different here. - Will Ness

4 Answers

8
votes

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.
4
votes

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.

3
votes

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'

1
votes

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.