What is Focking prefomorphism?

Question

I looked at the recursion-schemes library and I am very confused about what prepro supposed to be used or even what it does. The description of it as "Focking factoring" is not very informative, and the signature ( prepro :: Corecursive t => (forall b . Base tb -> Base tb) -> (Base ta -> a) -> t -> a ) is very similar on cata (catamorphism), but with an additional argument, whose intent is unclear. Can anyone explain what this function is for?

Answer 1

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

cata collapses the value: it expands one layer of the functor ( project ), recursively collapses the internal values ​​( fmap (cata f) ), and then destroys it all.

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

prepro also collapses the value, but it also applies e (the natural Base t ~> Base t transformation), as it does. Note that cata embed means id (except that it can include, for example, [Int] in Fix (ListF Int) ), since it collapses the functor levels, inserting them back into the output value:

cata (embed . e) pretty similar, except that it transforms each functor layer as it passes. Since e is a natural transformation, it cannot look into everything inside the layers when they fall; he can only reorganize the structure of the layer (this includes shuffling the inner layers around for so long if he is not actually looking at the inner layers).

So back to prepro ef . It collapses the value, first tearing off the outer layer, then “rewriting” the inner layers with e , recursively collapsing the inner values, and then collapsing it all. Note that since prepro itself has recursion, the deeper the layer is inside the value, the more it overwrites 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 ar = 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 xy) -> NodeF (x*2) y) embed tree -- Same thing but a different algebra -- "sum with deeper values weighted more" print $ prepro (\(NodeF xy) -> NodeF (x*2) y) ((+) <$> sum <*> rootLabelF) tree where drawTree' = putStr . drawTree . fmap show