1. 13
aphyr.com
1. 2

I’ve made this comment on the post, but it’s not visible (yet), so I’ll include it here, for a different perspective on how this can be handled, if you separate out the code for handling each item from the code which iterates over each item. I haven’t addressed all the examples Aphyr has here, but I believe with what’s below, you can replicate pretty much all of what he’s shown, in (IMO) a clearer and more succinct way.

This reminds me a lot of the Haskell foldl library. The core data type is:

``````data Fold a b = forall s. Fold (a -> s -> s) s (s -> b)
``````

which is three things - a function for combining some input with the current state, the current state, and a function to produce the final result from the state.

For simple folds, the code is trivial:

``````sum :: Num a => Fold a a
sum = Fold (+) 0 id

genericLength :: Num b => Fold x b
genericLength = Fold (\x n -> n + 1) (0::Int) fromIntegral
``````

It’s pretty obvious that a `Fold` is a `Functor`:

``````instance Functor (Fold x) where
fmap f (Fold step st done) = (Fold step st (f . done))
``````

What might be a bit surprising is that it is also an Applicative Functor:

``````instance Applicative (Fold x) where
pure a = Fold (\_ _ -> ()) () (const a)
(Fold stepf str donef) <*> (Fold stepa sta donea) =
Fold
(\x (sf,sa) -> (stepf x sf, stepa x sa))
(stf,sta)
(\(sf,sa) -> donef sf (donea sa))
``````

Because of this, it also means we can give Folds some really useful other instances, like `Num` and `Fractional`:

``````instance Num b => Num (Fold a b) where
fromInteger a = pure (fromInteger a)
(+) = liftA2 (+)
...

instance Fractional b => Fractional (Fold a b) where
(/) = liftA2 (/)
...
``````

This means that we can now write equations using folds - the classic example this is beulding up to is average:

``````average :: Fractional a => Fold a a
average = sum / genericLength
``````

which operates in constant space and tends to produce quite efficient code, as there’s no recursion so each fold can be inlined into the definition of `average`.

We can also map over the input to the fold

``````-- If I have a fold that can accept be's and a function to convert a's into b's
-- I can make a fold which can accept a's.
premap :: (a -> b) -> Fold b r -> Fold a r
premap f (Fold step s done) = Fold (step . f) s done
``````

which allows you to extract values from a larger structure

``````sumAges :: Fold Person Int
sumAges = premap age sum

averageAgeAndYearsAtCompany :: Fold EmployeeRecord (Double,Double)
averageAgeAndYearsAtCompany =
(,) <\$> premap (fromIntegral . age . employee) average
<*> premap (yearsService . employmentHistory) average
``````

How do we use these? using the `fold` function:

``````fold :: Foldable f => Fold a b -> f a -> b
``````

which is ignostic of what sort of container it is operation over, or you can trivially write functions that take a fold and stream data in for any other source; all you need to be able to do is provide elements one at a time.

There are many other useful functions which allow you to deal with more complex inputs, and produce more complex outputs, such as

``````-- Only process a given input if the predicate holds
prefilter :: (a -> Bool) -> Fold a r -> Fold a r
-- Don't process elements until you find a successful item
predropWhile :: (a -> Bool) -> Fold a r -> Fold a r
map :: Ord a => Fold (a, b) (Map a b)
foldByKeyMap :: forall k a b. Ord k => Fold a b -> Fold (k, a) (Map k b)
-- Perform a Fold while grouping the data according to a specified group projection function. Returns the folded result grouped as a map keyed by the group.
groupBy :: Ord g => (a -> g) -> Fold a r -> Fold a (Map g r)
-- generic mapping of the input to zero or more values to be processed using lens-y things:
handles :: Handler a b -> Fold b r -> Fold a r
handles _1       :: Fold a r -> Fold (a, b) r
handles _Left    :: Fold a r -> Fold (Either a b) r
handles traverse :: Traversable t => Fold a r -> Fold (t a) r
handles folded   :: Foldable    t => Fold a r -> Fold (t a) r
``````
1. 2

This is really neat, I haven’t seen this before, thanks for explaining it! The latter part of your post where you talk about changing the input refers to the `profunctor` structure of the `Fold` type, doesn’t it? Does viewing it via the `profunctor` lens make some of the definitions nicer? Is there input-side / contravariant story of the `Applicative` side of things, perhaps based on `Divisible` and `Decidable`?

1. 2

I think it has the wrong kind to be used for Divisible and Decidable, but there’s definitely a corresponding idea via Profunctor as you’ve mentioned and that’s kind of what I was getting at with the averageAgeAndYearsAtCompany example. And being a product or gives you all sorts of other niceties I’ve forgotten about. It’s also pretty trivially a category, which is kinda cool:

``````instance Category Fold where
(Fold stepbc stbc donebc) . (Fold stepab stab doneab) =
Fold
(\a (stl,str) -> let str’ = stepab a str; stl’ = stepbc (doneab str’) stl in (stl’,str’))
(stbc,stab)
(\(stl,_) -> donebc stl)
``````

(I think, i’ve written that on an iPad with no type checking… but if it compiles, it should be correct)