标签: catamorphism

以下函数通过使用递归方案库从列表实现良好的旧过滤器函数.

import Data.Functor.Foldable 

catafilter :: (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    -- alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

它编译和短期测试就像catafilter odd [1,2,3,4]是成功的.但是,如果我取消注释类型签名,alg我会收到以下错误:

src/cata.hs:8:30: error:
    • Couldn't match expected type ‘a’ with actual type ‘a1’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          alg …

我有一个AST,我正在使用它进行注释Cofree:

data ExprF a
  = Const Int
  | Add a
        a
  | Mul a
        a
  deriving (Show, Eq, Functor)

我type Expr = Fix ExprF用来表示未标记的AST,并type AnnExpr a = Cofree ExprF a代表标记的AST .我已经找到了一个函数,通过丢弃所有注释将标记的AST转换为未标记的AST:

forget :: Functor f => Cofree f a -> Fix f
forget = Fix . fmap uncofree . unwrap

这看起来可能是某种类似的catamorphism(我正在使用Kmett的recursion-schemes包中的定义).

cata :: (Base t a -> a) -> t -> a
cata f = c where c = f . fmap …

目前,梦想还在继续,在每个haskell概念中我都知道我更有吸引力.然而,我还没有完全实现这个珍贵的@ luqui对我之前关于catamorphism的问题的回答,我会回来直到它没问题.这是关于维基百科上的这个示例代码,处理BINARY树上的catamorphism.

尽管如此,我曾尝试推行了catamorphism 非二进制树,但我面对一些麻烦:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a ?  r
                                                 , composite :: [r] ?  r }

foldComposition :: CompositionAlgebra a r ?  Composition a ?  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- 最新的一行不会请"g [y]"

maxOfPair :: a ?  a …

典型的学术示例是总结一个列表.是否有现实世界中使用折叠的例子可以阐明其实用性？

Haskell的基本库包含几个函数,它们各自的数据类型的小写版本,例如bool,maybe和either.在Data.Bool.Extra的源代码中,该bool函数清楚地表示为数据类型的catamorphism:

bool = curry cata

现在,使用Recursion Schemes by Example中定义的catamorphism ,看起来上面提到的基本库函数都是它们数据类型的所有catamorphisms,例如对于Maybe:

-- base library definition
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

-- definition with cata
newtype Fix f = Fix {unFix :: f (Fix f)}
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
maybe n f m …

文件夹标识为

foldr (:) []

更一般而言，通过折叠，您可以销毁结构并以汇总值结束，或者以使结构以相同的输出结构结束的方式注入结构。

[Int] -> [Int] 或 [Int] -> Int 或 [Int] -> ?

我想知道unfoldr / l是否具有相似的身份。

我知道如何得到

Int -> [Int]

与展开/安娜。

我正在寻找某种方式

Int -> Int

递归方案。