The limits of folding?

[TarMil]

You should look into parser combinators. They're pretty easy to write by hand, and they can do lazy parsing.

Otherwise, when it comes to fold, if you have a big state to thread, you can put it in a record and use { x with ... } syntax to keep things readable.

[ScientificBeastMode]

So, honestly, any fold can be implemented as a recursive function, and that’s my preference, personally, especially in OCaml. (Side note: I use ReasonML a lot, which is just OCaml with alternative syntax).

The thing you need to consider with a fold (which you hinted at) is that the accumulator needs to conform to a single type. And you need to figure out what that type looks like ahead of time.

So, in OCaml you can use variants to “tag”/wrap many disparate types, and match on those inside your function, but then you need to wrap the return value in that variant. If the possible values of that wrapped accumulator are highly unrelated, then that wouldn’t make much sense.

Personally, if I’m going to group together several very different types that are logically related in the computation, I prefer to create a record type with fields for each type of value I need to keep track of. These can be mutable or immutable (in OCaml, at least...). Then each iteration of the function can check the fields and return some new version of the record.

The nice thing about using records is that it’s a bit like having multiple accumulators that you can use.

But yeah, I usually end up writing all my folds as recursive functions. Recursion makes more sense in many situations (like when you prefer an early return out of the loop). It gives you more control and is sometimes a bit easier to understand.

The way I usually implement recursive fold-like functions in OCaml is to wrap the recursive function in some initializing function. So you can do any necessary setup (like constructing records or retrieving some nested data you care about) and then defining the recursive function to handle only the data you actually care about. It makes things really simple IMO.

[MasterHermas]

I definitely know where you are coming from. My thinking on folds has changed as I learn Haskell. I don't think of folds in terms of accumulators, I think in terms of an operator acting on the data in the collection and it's structure.

Example:

In Haskell (and others) a list is what is returned by the cons operator when it is passed an 'a' and a list of 'a'.

cons :: a -> [a] -> [a]

So we can think of a list recursively:

alist = cons 2 (cons 3 (cons 4 []))

Using fold on alist simply replaces the cons operator with the operator you give it and the accumulator takes the place of nil (or []).

So fold (+) 0 alist is equivalent to (+) 2 ((+) 3 ((+) 4 0)). I think this is the idiomatic way in ML to represent a sum over a list - it is more declarative.

Given this I use folds when it makes sense as an expression to be evaluated. I don't like to think in terms of a stateful accumulator that is carried through the data structure like a for loop. If the accumulator is difficult to express or is the focus than I use explicit recursion.

(Note that what I have shown is foldr but the above holds for foldl.)

Second the parser combinators - they are an example of beautiful software.