福克京加的先验性意味着什么？

Question

我一直在查看recursion-schemes库，我非常困惑于prepro应该用于什么，甚至是它能做什么。将其描述为“Fokkinga的前变体”并不能提供很好的信息，签名(prepro :: Corecursive t => (forall b . Base t b -> Base t b) -> (Base t a -> a) -> t -> a)看起来非常类似于cata (变形)，但有一个额外的论据，其意图尚不清楚。有人能解释一下这个函数的作用吗？

Answer 1

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

cata折叠一个值:它打开函子的一个层(project)，递归地折叠内部值(fmap (cata f))，然后折叠整个事物。

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也会折叠一个值，但它也会应用e (自然转换Base t ~> Base t)。请注意，cata embed的意思是id (除了能够将[Int]转换为Fix (ListF Int))，因为它通过将函子层嵌入到输出值中来折叠函子层：

​

​

cata (embed . e)非常相似，只不过它在传递函子的每一层时都会对其进行转换。因为e是一种自然的转换，所以它不能在层下降时查看层内的任何内容；它只能重新组织层的结构(这包括对内部层进行调整，只要它不实际查看内部层)。

那么，回到prepro e f。它折叠一个值，首先剥离外层，然后用e“重写”内部层，递归地折叠内部值，然后再折叠整个事物。注意，由于递归是与prepro本身一起进行的，所以该值中的层越深，它被e重写的次数就越多。

游行示威

#!/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