The last three posts were about providing useful higher order functions that go hand in hand with C++ STL algorithms and ranges. In particular, we were interested in combining several functions together to create concise and efficient traversals.
While documenting on the subject, I went looking at other example in other languages. And I encountered a beautiful Haskell package named Control.Foldl. This package provides a very elegant way to create and combine efficient folds (a.k.a. reduce or accumulate).
In this post, we will quickly introduce this package, before diving in the implementation of one of the core function of the library, fold. I hope to convey to you the same delight I felt reading this short, smart and beautiful function.
Introducing Control.Foldl
The package Control.Foldl is a creation of the very prolific Gabriel Gonzalez. It makes use of the powerful type system and abstractions of Haskell to provide easy to write and efficient reductions over a Foldable.
For those who are not accustomed to the Haskell core type classes, you can consider the Foldable type class as a kind of abstract list.
There are already fold algorithms in the prelude of Haskell. The particularity of Control.Foldl is that it is built for performance, by leveraging (among others) he ability to combine several folds together.
A DSL for reductions
The package provides its efficiency by introducing a type Fold. A Fold a b instance describes a reduction over a collection of a that will produce a result of type b. A Fold is made of three distinct parts:
- A step function. This step function has for particularity that it does not deal with the type b directly, but with an intermediary type x.
- An initial value of the intermediary type x
- An extract function to transform the x into the final result of type b
The intermediary type x allows for a different representation of the data during the reduction. I will gloss over this point: you can have a look at the package to see some examples of how it can be used at your advantage.
The key point for me is that the Fold only describes the reduction. No actual work is done at construction. This is critical.
It allows to elegantly compose these Folds before doing any actual work. Put differently, a Fold is like a DSL for reductions, and the function fold is the evaluation function for this DSL (or an interpreter if you like).
Note: I highly encourage you to look at the implementation of the Applicative instance of the Fold. It is very instructive. Because of Applicative constraints, the way two Folds are combined is indeed slightly different from the way we implemented par_steps in the previous posts. In particular, it does not rely on tuples to combine two folds, but on functions.
Evaluating the DSL
Evaluating the Fold DSL consists in doing the actual work that the Fold describes. This is the task of the fold function, which assembles the different parts of the Fold together, and runs the computation over a Foldable.
In essence, the fold function does the following:
- Start with the initial value of x
- Use the step function to combine each element a with x, to get another x
- Call the extract function on the resulting x to get the final result.
It really looks like a standard fold left function, but with a twist: instead of executing a single step function, we execute a Fold instance, which itself might be a composite of several Fold instances.
The implementation of fold
Now that we are comfortable with what the package does, we can look at the implementation of the fold function (taken from version 1.2.3):
fold :: Foldable f => Fold a b -> f a -> b
fold (Fold step begin done) as = foldr cons done as begin
where
cons a k x = k $! step x a
The key to understand this small piece of code is to notice that:
- Although fold is a fold left, it is implemented by a fold right
- The argument k represents a continuation (a function)
- The cons function is taking 2 arguments and returning a continuation
- Hence the foldr constructs a continuation from smaller continuations
- The fourth argument to the foldr is the argument to the final continuation
So the continuation k at position j takes as left argument the result of the continuation built at postion j-1, and combines it with the element at position j.
Based on these observations, we can deduce that if we unrolled the loop, we would obtain something of that kind:
-- The continuation created by the foldr done . (`step` a[N]) ... (`step` a[1]) . (`step` a[0]) -- The actual computation done (step (step (... (step begin a[0]) ...) a[N-1]) a[N])
We end up with a fold left, implemented as a foldr, using continuation passing style. It took me quite some time to understand what was going on. But when I finally got it, I found it quite beautiful and truly mind blowing.
Resources
I hope you enjoyed this small exploration of code, and did learn something in the process. I highly encourage you to look at the package on hackage at: https://hackage.haskell.org/package/foldl-1.2.3.
You should also have a look at the blog post that introduces this package in the blog of Gabriel Gonzalez.
Deque 
Leave a Reply