Do people actually use fold_left and fold_right in practice?

Learning
1

In class I was taught about fold_left and fold_right but I think its silly. In a real situation I’d never use them I’d just use my own brain to figure out a recursive algorithm to solve a problem. Is there any use for these function besides academic settings?

List.fold_left
1 Like
2

Let’s do a completely unscientific study and search GitHub :slight_smile:

3 Likes
3

In fact, it is rather the contrary: not using fold_left or fold_right is a code smell in actual code bases.

7 Likes
4

why is that the case?

5

Non tail-recursive function:

let rec list_length = function
  | [] -> 0
  | _::s -> 1 + list_length s

Tail-recursive one without fold_left:

let list_length l =
  let rec list_length acc = function
  | [] -> acc
  | _::s -> list_length (acc + 1) s
  in
  list_length 0 l

Tail-recursive one with fold_left:

let list_length l =
  List.fold_left (fun acc _ -> acc + 1) 0 l

It’s much more quick to write once you’re used to it. Also, when reading code, you understand directly what it’s doing (you’re usually interested in knowing if the function is only itering, mapping or folding on the list).

5 Likes
6

A fold_left (or a fold_right) is a very common case, with a very simple data flow. Using a common function make your intent very clear. Contrarily, if you write your own function by hand, you could implement a much more complex data flow. Consequently, you require more effort from your reader to identify the fact that you are just reimplementing a fold.

14 Likes
7

The keyword here is abstraction, and the idea that programming at a higher level of abstraction is a good thing. It’s the same reason why we use high-level programming languages instead of assembly.

With sufficient programming experience, you’ll find that certain patterns repeat over and over and over again. Fold and map capture two such patterns. Now instead of repeating these patterns (using low level code) every time, we give them a name and factor them into functions that we can reuse. This makes your code shorter, and let’s you focus on the important bits (init and f) instead of the repetitive part. Thus your code is less noisy and there is less potential for bugs.
Importantly, this makes it easier to read and understand your code, because people will see the pattern right away instead of having to recognize it from the low-level code.

Finally, the implementation of fold can be optimized once and for all, and you will get the benefit “for free” everywhere you use it. If you look at the real implementation of fold in JaneStreet’s base, you may he surprised what you’ll find :wink:

EDIT: Let me add that you’re asking a very valid question and that it’s only natural that you would find the manual code easier than the code using fold, given that you’re new to this abstraction. This is basically always the case with new abstractions. They require some initial cost to get used to, but once you understand them and feel very comfortable with them the payoff can be huge.

EDIT2: Let me also add that there are definitely cases in which the abstraction cost is not worth it, and it’s better to program things at a lower level of abstraction. You’ll develop an intuition for this with experience. But for fold and map you will find that the benefit of abstraction is huge.

10 Likes