News for hackers. Stuff that matters.
Re:Functional Programming with Bananas, Lenses, Envelopes an... by pwm on Wednesday August 05, 2020 @08:43AM (#24060168)
Let's try to make this a tad less abstract with a (hopefully) more practical teaser:

1. Let's define a simple binary tree and a (recursive) function to process it:

    data Tree a
      = Leaf a
      | Node (Tree a) (Tree a)

    processTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
    processTree processLeaf processNode = walk
      where
        walk (Leaf v) = processLeaf v
        walk (Node l r) = processNode (walk l) (walk r)
processTree takes 2 functions, namely the "how to process a leaf?" and the "how to process a node?" ones as well as a tree and then... processes it :) Now, given a tree of Ints, we can use the above to eg. sum its values, find the biggest one or count the nodes:

    λ> myTree = Node (Node (Leaf 3) (Leaf 9)) (Leaf 7)
    λ> processTree (+ 1) (+) myTree
    22
    λ> processTree id max myTree
    9
    λ> processTree (const 1) (+) myTree
    3
Great. Now, instead of defining the above Tree type as an inductive type, let's factor that part out:

    data TreeShape a rec
      = Leaf a
      | Node rec rec
This type is kinda like the original except we add a new type variable (rec) for the inductive part. Ok, now comes the interesting (crazy?) part: Let's define a weird type called Fix:

    newtype Fix f = Fix {unFix :: f (Fix f)}
Don't get lost in it! Just read on. Let's use this weird Fix type to define our original Tree type as such:

    type Tree a = Fix (TreeShape a)
Also let's rewrite the original processTree function using this new type:

    processTree :: (TreeShape a b -> b) -> Tree a -> b
    processTree process = walk
      where
        walk (Fix (Leaf v)) = process (Leaf v)
        walk (Fix (Node l r)) = process (Node (walk l) (walk r))
Looks kinda like the original except that it now uses the same(!) function (aka. algebra) to process both leaves and nodes. This allows us to write simple (non-recursive) functions:

    sum (Leaf v) = v
    sum (Node l r) = l + r
    max (Leaf a) = a
    max (Node l r) = max l r
    size (Leaf _) = 1
    size (Node l r) = l + r
and recover:

    λ> myTree = Fix $ Node (Fix $ Node (Fix $ Leaf 3) (Fix $ Leaf 9)) (Fix $ Leaf 7)
    λ> processTree sum myTree
    19
    λ> processTree max myTree
    9
    λ> processTree size myTree
    3
At this point you might rightfully ask: Why oh why would we go through all this suffering just to recover the same functionality we had originally? Good question :) To answer it we need to realise that "TreeShape a" (and thus also "Tree a") is a member of a class called Functor, which means it knows how to map functions over itself. The magic incantation to do such mapping is called fmap in Haskell. Let's make TreeShape work with fmap:

    instance Functor (TreeShape a) where
      fmap _ (Leaf v) = Leaf v
      fmap f (Node l r) = Node (f l) (f r)
Now, knowing the above, we can rewrite our processTree function into a _much_ more generic form that works not just on our Tree type but on _any_ Functor:

    processFunctor :: Functor f => (f b -> b) -> Fix f -> b
    processFunctor process = process . fmap (processFunctor process) . unFix
This processFunctor function (aka. catamorphism) has no notion of the shape it processes other than that shape should know how to map a function over itself (ie. it's a Functor). As an added bonus we don't even need to write Functor instances for our types by hand as deriving them is a deterministic and mechanical process and thus the compiler is more than happy to do it for us:

    data TreeShape a rec
      = Leaf a
      | Node rec rec
      deriving stock Functor
To summarise: if we want to process some recursive data structure and that data structure happens to be a Functor then all we need to do is derive it's functor instance, write a simple function to do something with an element of the structure and apply that function to the whole using processFunctor.
Re:Functional Programming with Bananas, Lenses, Envelopes an... by prezjordan on Wednesday August 05, 2020 @12:44PM (#24062819)
This is really great, thanks :)

`fmap _ (Leaf v) = Leaf (f v)` right? (s/v/f v)

I'm also curious about "the compiler is more than happy to do it for us" - is that in the form of `deriving Functor`? I have never seen stock before!

Lastly, does `processFunctor` exist in the standard library? Seems powerful but unsure why I would personally have to write it with each project.

Re:Functional Programming with Bananas, Lenses, Envelopes an... by tominated on Wednesday August 05, 2020 @03:28PM (#24064567)
Not quite - think of the functor as a container for the recursive field, not the values attached to leaves. The leaf is your base recursive case and doesn't have a value to map over. Having your functor instance map over this recursive field is what allows you to write a non-recursive function that expects the field to have the already processed value from it's children!

And yeah, the compiler can derive the functor instance! I don't know the mechanism for how it works but I think it might assume the last type parameter is the 'container' field (think the values in a list or maybe)

It's not in the standard lib, but you can find a few implementations (it's usually called cata for catamorphism) available on hackage. I have used recursion-schemes and it works pretty well.

I learned about this stuff via this excellent blog series: https://blog.sumtypeofway.com/posts/introduction-to-recursio...

Re:Functional Programming with Bananas, Lenses, Envelopes an... by pwm on Wednesday August 05, 2020 @03:49PM (#24064801)
> `fmap _ (Leaf v) = Leaf (f v)` right? (s/v/f v)

Compare the Functor instances of the original inductive Tree type with TreeShape a:

    instance Functor Tree where
      fmap :: (b -> c) -> Tree b -> Tree c
      fmap f (Leaf v) = Leaf (f v)
      fmap f (Node l r) = Node (fmap f l) (fmap f r)

    instance Functor (TreeShape a) where
      fmap :: (rec -> b) -> TreeShape a rec -> TreeShape a b
      fmap _ (Leaf v) = Leaf v
      fmap f (Node l r) = Node (f l) (f r)
You see that in the latter the function we map over acts on the rec type which is the induction we factored out and is only present in the Node case. You can view the Leaf case as the termination case where Fix stops expanding. It's useful to write out the evaluation by hand on a small example to see how it works.

> I'm also curious about "the compiler is more than happy to do it for us" - is that in the form of `deriving Functor`?

It is indeed the deriving Functor. You can even examine what the compiler does by dumping out the instance using the -ddump-deriv flag.

For more background reading as to why this is possible here are a few links:

- https://mail.haskell.org/pipermail/libraries/2011-February/0...

- https://www.schoolofhaskell.com/user/edwardk/snippets/fmap

> I have never seen stock before!

It comes from the DerivingStrategies lang extension which makes it explicit that this derivation is "built in". Everything works the same without it though so we can just ignore it as well.

> Lastly, does `processFunctor` exist in the standard library?

If by standard you mean the Prelude then no, but there are tons of packages, eg.:

- https://hackage.haskell.org/package/data-fix

- https://hackage.haskell.org/package/recursion-schemes

- https://hackage.haskell.org/package/compdata

- https://hackage.haskell.org/package/yaya