What is Fokkinga's prepromorphism meant to do?

Question

I've been looking at the recursion-schemes library, and I'm very confused about what prepro is supposed to be used for, or even what it does. The description of it as 'Fokkinga's prepromorphism' isn't very informative, and the signature (prepro :: Corecursive t => (forall b . Base t b -> Base t b) -> (Base t a -> a) -> t -> a) looks very similar to cata (the catamorphism) but with an extra argument, whose intent is unclear. Would someone be able to explain what this function is meant to do?

Hypoderma

The function has a default definition, so in a sense it should be obvious as to what it does and what the role of the 'extra' argument is. If you find the definition too terse to understand, then you should phrase the question to refer to which specific part of the definition you are struggling with. If you're interested in Fokkinga's original description, see “Law and order in algorithmics”. – Prochora

Edward Kmett describes a catamorphism as something that "tears down a structure", and a prepromorphism as something that "tears down a structure after repeatedly applying a natural transformation". It looks like the extra argument is the natural transformation to apply. – Sever

Answer 1

cata f = c where c = f . fmap c . project
{- c = cata f -}
       = f . fmap (cata f) . project

cata collapses a value: it unwraps one layer of the functor (project), collapses the interior values recursively (fmap (cata f)), and then collapses the whole thing.

prepro e f = c where c = f . fmap (c . cata (embed . e)) . project
{- c = prepro e f -}
           = f . fmap (prepro e f . cata (embed . e)) . project

prepro also collapses a value, but it also applies e (a natural transformation Base t ~> Base t) as it does so. Notice that cata embed means id (except it's able to turn e.g. [Int] into Fix (ListF Int)), because it collapses the functor layers by embedding them back into the output value:

cata (embed . e) is rather similar, except it transforms each layer of the functor as it passes down. Because e is a natural transformation, it cannot peer at whatever is inside the layers as they fall; it can only reorganize the structure of the layer (this includes shuffling the inner layers around as long is it doesn't actually look into the inner layers).

So, back to prepro e f. It collapses a value, by first peeling off the outer layer, then "rewriting" the inner layers with e, collapsing the inner values recursively, and then collapsing the whole thing. Note that since the recursion is with prepro itself, the deeper a layer is inside the value, the more times it gets rewritten by e.

---

Demonstration

#!/usr/bin/env stack
-- stack --resolver lts-9.14 script
{-# LANGUAGE TypeFamilies, DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
import Data.Functor.Foldable -- package recursion-schemes
import Data.Tree             -- package containers
-- Tree a = Rose trees of a
-- makeBaseFunctor breaks down on it, so...
data TreeF a r = NodeF { rootLabelF :: a, subForestF :: [r] }
  deriving (Functor, Foldable, Traversable)
type instance Base (Tree a) = TreeF a
instance Recursive (Tree a) where project (Node a ts) = NodeF a ts
instance Corecursive (Tree a) where embed (NodeF a ts) = Node a ts

tree :: Tree Integer
tree = Node 2 [Node 1 [Node 3 []], Node 7 [Node 1 [], Node 5 []]]

main = do -- Original
          drawTree' tree

          -- 0th layer: *1
          -- 1st layer: *2
          -- 2nd layer: *4
          -- ...
          drawTree' $ prepro (\(NodeF x y) -> NodeF (x*2) y) embed tree

          -- Same thing but a different algebra
          -- "sum with deeper values weighted more"
          print $ prepro (\(NodeF x y) -> NodeF (x*2) y) ((+) <$> sum <*> rootLabelF) tree
  where drawTree' = putStr . drawTree . fmap show

Dereliction