1. 13
  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) = 
              (\x (sf,sa) -> (stepf x sf, stepa x sa)) 
              (\(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) = 
                (\a (stl,str) -> let str’ = stepab a str; stl’ = stepbc (doneab str’) stl in (stl’,str’))
                (\(stl,_) -> donebc stl)

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