GitLab

Motivation

Consider the following inefficient variant of fib:

{-# OPTIONS_GHC -O2 -fforce-recomp #-}

module Test (fib) where

data Tree = I Tree Tree | L !Int

fibTree :: Int -> Tree
fibTree 0 = L 0
fibTree 1 = L 1
fibTree n = I (fibTree (n-1)) (fibTree (n-2))

sumTree :: Tree -> Int
sumTree (L n) = n
sumTree (I l r) = sumTree l + sumTree r

fib :: Int -> Int
fib = sumTree . fibTree

We get the following optimised Core for fib:

fib
  = \ x_a1nd ->
      case x_a1nd of { I# ww1_s1oJ ->
      case $wsumTree ($wfibTree ww1_s1oJ) of ww2_s1oE { __DEFAULT ->
      I# ww2_s1oE
      }
      }

E.g. we first build up the Tree in fibTree and then consume it in sumTree.

What a waste! For lists, we have elobarate fusion rules, but that doesn't help for user-defined data structures. I want to get rid of the intermediate tree, so that fib above is equivalent to the hand-written fib', e.g.

$wfib'
  = \ ww_s1pX ->
      case ww_s1pX of ds_X1nA {
        __DEFAULT ->
          case $wfib' (-# ds_X1nA 1#) of ww1_s1q1 { __DEFAULT ->
          case $wfib' (-# ds_X1nA 2#) of ww2_X1r3 { __DEFAULT ->
          +# ww1_s1q1 ww2_X1r3
          }
          };
        0# -> 0#;
        1# -> 1#
      }

I think this is very relevant in practice; in GHC we have the non-recursive viewCore function and offload the recursion to call sites, so that viewCore can be inlined into its call sites.

Proposal

In terms of the pretty well established literature on recursion schemes, fibTree is an "anamorphism", a function that builds up a recursive data structure, and sumTree is a "catamorphism", a function that consumes/folds over a recursive data structure.

I imagine that whether or not some function is an anamorphism or catamorphism can be identified pretty easily. For example, the recursive invocations of fibTree are exactly in the places where T expects a Tree, e.g. there is no normalisation function in between. Likewise for sumTree, we can see that it recurses into its arguments l and r without any function in-between. In both cases, those are the only recursive invocations. That makes for a pretty simple analysis.

As for the transformation: We can apply it whenever an anamorphism is followed by a catamorphism, like sumTree . fibTree. The fusion of both functions is called a "hylomorphism", hence the title of this issue.

For the example above, I'd transform:

fibTree 0 = L 0
fibTree 1 = L 1
fibTree n = I (fibTree (n-1)) (fibTree (n-2))

sumTree (L n) = n
sumTree (I l r) = sumTree l + sumTree r

fib = sumTree . fibTree

==> { make recursion explicit }

fibTree = fibTree' fibTree
fibTree' :: (Int -> Tree) -> Int -> Tree
fibTree' fibTree 0 = L 0
fibTree' fibTree 1 = L 1
fibTree' fibTree n = I (fibTree (n-1)) (fibTree (n-2))

sumTree = sumTree' sumTree
sumTree' :: (Tree -> Int) -> Tree -> Int
sumTree' sumTree (L n) = n
sumTree' sumTree (I l r) = sumTree l + sumTree r

fib = sumTree . fibTree

==> { Replace Tree with church-encoded signature functor Tree C }

-- | You can derive TreeC by replacing all occurrences of `Tree` in data constructors
-- with `r` and taking the curch encoding.
type TreeC r = forall a. (Int -> a) -> (r -> r -> a) -> a

fibTree = fibTree' fibTree L I
fibTree' :: (Int -> r) -> Int -> TreeC r
fibTree' fibTree 0 l i = l 0
fibTree' fibTree 1 l i = l 1
fibTree' fibTree n l i = i (fibTree (n-1)) (fibTree (n-2))

sumTree = sumTree' sumTree
sumTree' :: (r-> Int) -> TreeC r -> Int
sumTree' sumTree t = t (\n -> n) (\l r -> sumTree l + sumTree r)

fib = sumTree . fibTree

==> { Interlock recursions }

-- sumTree', fibTree' as before

fib = sumTree' id (fibTree' fib n)

==> { Simplification }

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Test it! fib = sumTree' id (fibTree' fib n) generates optimal code. Why id in the argument to sumTree'? Frankly, I've no idea yet, but the literature on recursion-schemes should answer that question. And of course I tested that it generates the correct code.

This transformation would also generalise a lot of foldr/build fusion, as this is a strictly more general framework. I think by also recognising "metamorphisms", e.g. a catamorphism followed by an anamorphism, we can fuse entire list pipelines.

I think nothing here is new, except for the idea of how to exploit it in a compiler optimisation. In particular, I think this is all due to "Deforestation: transforming programs to eliminate trees" by Phil Wadler. And reviewing that paper, I'm not even so certain that anything about this is novel at all, just unexploited.