5

我一直在看recursion-schemes图书馆,我很困惑prepro应该用于什么,甚至它的作用。将其描述为“Fokkinga 的预变形”的信息量不是很大,并且签名 ( prepro :: Corecursive t => (forall b . Base t b -> Base t b) -> (Base t a -> a) -> t -> a) 看起来与 (catamorphism) 非常相似,cata但有一个额外的论点,其意图尚不清楚。有人能解释一下这个功能是做什么的吗?

4

1 回答 1

6
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(除了它能够变成 eg [Int]into Fix (ListF Int)),因为它通过将仿函数层嵌入回输出值来折叠它们:

<code>cata嵌入示意图</code>

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
于 2017-11-24T05:38:20.677 回答