DEV Community

Overly Functional C++: The BenFolds Five

Ben Lovy on October 03, 2019

Two-Part Series, Chapter 3 What a plot twist! I made almost no effort to avoid the pun and I'm only a little sorry. Despite being a tr...

Read full post

Kasey Speakman • Oct 4 '19 • Edited

The Brick song. Man that takes me back.

Anyway, just a note that fold does not have to be declared functional-like, and it can still be used for FP. As long as mutations stay local to the function (only mutating your own declared variables), the function is still deterministic overall. For example F# implements List.fold with an imperative loop for perf reasons:

    module List =
        ...

        let fold<'T,'State> folder (state:'State) (list: 'T list) = 
            match list with 
            | [] -> state
            | _ -> 
                let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(folder)
                let mutable acc = state
                for x in list do
                    acc <- f.Invoke(acc, x)
                acc

And even if using a recursive loop, the compiler does something similar for you with TCO. But not optimized for a list since recursive loops can have early exit or indefinite iterations.

For my own code I will probably use a recursive loop, depending on what it is, and avoid mutation. But for core data structures I might opt for performance.

I realize this is for your exploration. I suppose this is more a note for other readers. :)

Ben Lovy • Oct 4 '19 • Edited

Thanks for pointing that out! I think learning FP for the first time via Haskell has had some lingering biases, this is definitely important to note. Implementing the fold here by instead mutating in place outside the body of the function is indeed a ton more efficient, and actually about the same level of effort to implement, but you lose your guarantees.

That's interesting to see in F#...can always count on you for a reminder I really want to keep that in my toolbox!

Michael Lustig - halfjew22@gmail.com • Oct 3 '19

Not interested in c++ whatsoever, but just had to give you a shout for mentioning Ben Folds Five. Takes me back to high school!