4 ms·

Every developer should know how to write a tail-recursive function and understand why it is equivalent to a loop. That said, tail recursion is rarely needed in

Every developer should know how to write a tail-recursive function and understand why it is equivalent to a loop. That said, tail recursion is rarely needed in modern functional programming. For example, why write out a recursive function when a call to `fold` or `map` will do the same thing?

xdavidliu 1y ago
it's not entirely true that it does the same thing: even if it gives the same result. For many programming languages, fold and map can only act on non-lazy data structures, so require O(N) memory for the data that needs to be folded over, while tail-recursive functions usually only use O(1) memory, even stack memory. Notable exceptions to the above are python3 with generators, which I believe truly use O(1) memory with map and fold. Haskell has lists that are lazy by default, but if you fold or map over them, it still "forces the thunk" for each element and thus you still end up using O(N) memory.
- munchler 1y ago
  I would hope that most standard libraries are optimized to avoid this sort of waste as much as possible. In F#, for example, I know that the standard `map` and `fold` are implemented imperatively for maximum performance.
  - xdavidliu 1y ago
    I don't know F#, but even if that were true, I'm guessing you need a list of the data in memory in the first place in order to fold or map over. That's still a disadvantage, since with tail recursion you don't, and thus it takes O(1) memory total.
    - munchler 1y ago
      I'd be interested to see a concrete example of what you're talking about. Use a language, data structure, and function signature of your choice. My claim is that in most cases, such a function can be implemented efficiently by chaining together standard higher-order functions (i.e. combinators), rather than by writing a custom tail recursive solution from scratch.
- lgas 1y ago
  ...although list fusion often saves you if the thunks were going to be forced eventually anyway.
- mrkeen 1y ago
  * I don't think you meant to compare forcing each element (as opposed to forcing the input or output data structures) * If you did mean it that way, I doubt Python can avoid forcing each element that goes through its generators. (Without, say, thunking up each element manually or using a generator of generators, etc.) Here is Haskell using a fold and a map. It does not force the input, the output, or each element: main = let lazyInput = zip ([1..] :: [Int]) (repeat (error "boom")) lazyOutput = foldr (:) [] lazyInput in print (sum (map fst (take 10_000_000 lazyOutput))) > 50000005000000 > 9 MiB total memory in use > real 0m0.062s
Eji1700 1y ago
> For example, why write out a recursive function when a call to `fold` or `map` will do the same thing? Yeah this was a big help when I started F#. Basically "if you're using the rec keyword, you're probably missing something" and hell that even goes for a lot of uses of fold, from the beginners perspective.
kmicinski 1y ago
I agree with you--that's a topic I will definitely cover in my blog, too. You make a good point: I know some folks who worked at big financial orgs, writing hundreds of thousands of lines of code, and never wrote general-recursive functions (only used simple recursors like foldl).
zelphirkalt 1y ago
I wouldn't say "rarely", unless you have a whole host of other higher order functions at your disposal for more special cases than map and fold. There are many cases, where you don't want to fold or map over the whole data structure and want to exit early with a result already. Writing tail recursive functions is still very common.
- munchler 1y ago
  > I wouldn't say "rarely", unless you have a whole host of other higher order functions at your disposal for more special cases than map and fold That is my point. Modern functional languages do have a host of higher-order functions for exactly this sort of thing. For example, here is F#'s `Seq` module, for working with lazy sequences: https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-seqmodule.html https://fsharp.github.io/fsharp-core-docs/reference/fsharp-c... > There are many cases, where you don't want to fold or map over the whole data structure and want to exit early with a result already. Writing tail recursive functions is still very common. I think this can usually be handled more concisely by combining higher-order functions instead. For example, if you want to fold over a partial data structure, you can use `filter` to select only the elements you want, and then fold over that subset. Or, if you want to exit early from a map, you can use `takeWhile` and only map over what's left. Real-world functional programming is usually about combining these built-in tools effectively, rather than writing new tools from scratch.
  - zelphirkalt 1y ago
    While you are right about being able to combine higher-order functions in the way you describe, I might not find your examples compelling, because they require 2 passes over the data. On the other hand one could argue, that one pass of those is checking some condition (index below some number, or element followed by element that satisfies a predicate, or similar things), and the other pass is then blindly applying some other function, without having to check the condition again. Maybe that is in the end equal in performance.
    - mrkeen 1y ago

xdavidliu 1y ago

it's not entirely true that it does the same thing: even if it gives the same result. For many programming languages, fold and map can only act on non-lazy data structures, so require O(N) memory for the data that needs to be folded over, while tail-recursive functions usually only use O(1) memory, even stack memory. Notable exceptions to the above are python3 with generators, which I believe truly use O(1) memory with map and fold. Haskell has lists that are lazy by default, but if you fold or map over them, it still "forces the thunk" for each element and thus you still end up using O(N) memory.

munchler 1y ago
I would hope that most standard libraries are optimized to avoid this sort of waste as much as possible. In F#, for example, I know that the standard `map` and `fold` are implemented imperatively for maximum performance.
- xdavidliu 1y ago
  I don't know F#, but even if that were true, I'm guessing you need a list of the data in memory in the first place in order to fold or map over. That's still a disadvantage, since with tail recursion you don't, and thus it takes O(1) memory total.
  - munchler 1y ago
    I'd be interested to see a concrete example of what you're talking about. Use a language, data structure, and function signature of your choice. My claim is that in most cases, such a function can be implemented efficiently by chaining together standard higher-order functions (i.e. combinators), rather than by writing a custom tail recursive solution from scratch.
lgas 1y ago
...although list fusion often saves you if the thunks were going to be forced eventually anyway.
mrkeen 1y ago
* I don't think you meant to compare forcing each element (as opposed to forcing the input or output data structures) * If you did mean it that way, I doubt Python can avoid forcing each element that goes through its generators. (Without, say, thunking up each element manually or using a generator of generators, etc.) Here is Haskell using a fold and a map. It does not force the input, the output, or each element: main = let lazyInput = zip ([1..] :: [Int]) (repeat (error "boom")) lazyOutput = foldr (:) [] lazyInput in print (sum (map fst (take 10_000_000 lazyOutput))) > 50000005000000 > 9 MiB total memory in use > real 0m0.062s

Eji1700 1y ago

> For example, why write out a recursive function when a call to `fold` or `map` will do the same thing? Yeah this was a big help when I started F#. Basically "if you're using the rec keyword, you're probably missing something" and hell that even goes for a lot of uses of fold, from the beginners perspective.

kmicinski 1y ago

I agree with you--that's a topic I will definitely cover in my blog, too. You make a good point: I know some folks who worked at big financial orgs, writing hundreds of thousands of lines of code, and never wrote general-recursive functions (only used simple recursors like foldl).

zelphirkalt 1y ago

I wouldn't say "rarely", unless you have a whole host of other higher order functions at your disposal for more special cases than map and fold. There are many cases, where you don't want to fold or map over the whole data structure and want to exit early with a result already. Writing tail recursive functions is still very common.

munchler 1y ago
> I wouldn't say "rarely", unless you have a whole host of other higher order functions at your disposal for more special cases than map and fold That is my point. Modern functional languages do have a host of higher-order functions for exactly this sort of thing. For example, here is F#'s `Seq` module, for working with lazy sequences: https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-seqmodule.html https://fsharp.github.io/fsharp-core-docs/reference/fsharp-c... > There are many cases, where you don't want to fold or map over the whole data structure and want to exit early with a result already. Writing tail recursive functions is still very common. I think this can usually be handled more concisely by combining higher-order functions instead. For example, if you want to fold over a partial data structure, you can use `filter` to select only the elements you want, and then fold over that subset. Or, if you want to exit early from a map, you can use `takeWhile` and only map over what's left. Real-world functional programming is usually about combining these built-in tools effectively, rather than writing new tools from scratch.
- zelphirkalt 1y ago
  While you are right about being able to combine higher-order functions in the way you describe, I might not find your examples compelling, because they require 2 passes over the data. On the other hand one could argue, that one pass of those is checking some condition (index below some number, or element followed by element that satisfies a predicate, or similar things), and the other pass is then blindly applying some other function, without having to check the condition again. Maybe that is in the end equal in performance.
  - mrkeen 1y ago