标签: catamorphism

我最近发现了如何 以某种迂回的方式在 Java 中模拟高阶类型，如下所示

interface H<F, T> { }

这里H编码一个高阶类型，它采用类型参数，F该类型参数本身采用参数T。

现在这让我想知道，我们可以用它来实现一些更高级的构造吗？例如，Haskell 中的 Fix 等函子的不动点及其相应的变形？

我发明了一种递归方案,这种方法是对同态性的推广.折叠具有catamorphism的数据结构时,您无法访问子项,只能访问折叠的子结果:

{-# LANGUAGE DeriveFunctor #-}
import qualified Data.Map as M

newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f b -> b) -> Fix f -> b
cata phi = self where
    self = phi . fmap (\x -> self x) . unFix

折叠功能phi只能访问self x原始结果,但不能访问原始结果x.所以我添加了一个加入功能:

cataWithSubterm :: Functor f => (Fix f -> c -> b) -> (f b -> c) -> Fix f -> …

我有这个AST

data ExprF r = Const Int | Add   r r
type Expr = Fix ExprF

我想比较一下

x = Fix $ Add (Fix (Const 1)) (Fix (Const 1))
y = Fix $ Add (Fix (Const 1)) (Fix (Const 2))

但是所有递归方案函数似乎只适用于单一结构

显然我可以使用递归

eq (Fix (Const x)) (Fix (Const y)) = x == y
eq (Fix (Add x1 y1)) (Fix (Add x2 y2)) = (eq x1 x2) && (eq y1 y2)
eq _ _ = False

但我希望可以使用某种zipfold功能.

Scalaz提供了一个名为方法fold关于各种ADT的如Boolean,Option[_],Validation[_, _],Either[_, _]等.该方法基本上发生在对应于所有可能的情况该给定ADT的功能.换句话说,模式匹配如下所示:

x match {
  case Case1(a, b, c) => f(a, b, c)
  case Case2(a, b) => g(a, b)
  .
  .
  case CaseN => z
}

相当于:

x.fold(f, g, ..., z)

一些例子:

scala> (9 == 8).fold("foo", "bar")
res0: java.lang.String = bar

scala> 5.some.fold(2 *, 2)
res1: Int = 10

scala> 5.left[String].fold(2 +, "[" +)
res2: Any = 7

scala> 5.fail[String].fold(2 +, "[" +)
res6: Any = 7

同时,对于Traversable[_] …

我有一个递归数据类型,它有一个Functor实例:

data Expr1 a
  = Val1 a
  | Add1 (Expr1 a) (Expr1 a)
  deriving (Eq, Show, Functor)

现在,我有兴趣修改此数据类型以支持一般递归方案,因为本教程和此Hackage包中对它们进行了描述.我设法让catamorphism工作:

newtype Fix f = Fix {unFix :: f (Fix f)}

data ExprF a r
  = Val a
  | Add r r
  deriving (Eq, Show, Functor)

type Expr2 a = Fix (ExprF a)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

eval :: …

最近我终于开始觉得我理解了catamorphisms.我在最近的一个回答中写了一些关于它们的内容,但简单地说,对于递归遍历该类型的值的过程,我会说类型抽象的一个变形,其中该类型的模式匹配在每个类型具有的构造函数中被赋予一个函数. .虽然我欢迎对这一点或上面链接的答案中的较长版本进行任何更正,但我认为我或多或少都有这种情况,这不是这个问题的主题,只是一些背景知识.

一旦我意识到你传递给一个catamorphism的函数完全对应于类型的构造函数,并且这些函数的参数同样对应于那些构造函数的字段的类型,所有这些都突然感觉很机械,我看不到有哪些替代实施的任何摆动空间.

例如,我只是编造了这种愚蠢的类型,没有关于它的结构"意味着什么"的真实概念,并为它导出了一个变形.我没有看到任何其他方式我可以定义这种类型的通用折叠:

data X a b f = A Int b
             | B
             | C (f a) (X a b f)
             | D a

xCata :: (Int -> b -> r)
      -> r
      -> (f a -> r -> r)
      -> (a -> r)
      -> X a b f
      -> r
xCata a b c d v = case v of
  A i x -> a i x
  B -> b
  C f x …

我试图围绕变形的概念.

在函数式编程中,anamorphism是对列表展开概念的概括.形式上,anamorphisms是泛型函数,它们可以共同构造某种类型的结果,并通过确定构造的下一个单一步骤的函数进行参数化.

它的双重,同态,在这篇文章中有很好的描述:什么是catamorphism并且可以在C#3.0中实现？.

一个很好的C#中的变形行为的例子是LINQ的Aggregate方法.

变形等价物会是什么？将伪随机数生成器Random视为变形结构或者展开过程是否总是包含如下所示的累加器函数(从Intro到Rx的代码片段)是否正确？

IEnumerable<T> Unfold<T>(T seed, Func<T, T> accumulator)
{
    var nextValue = seed;
    while (true)
    {
        yield return nextValue;
        nextValue = accumulator(nextValue);
    }
}

这个问题的答案表明,Scala中Option的fold方法是一种catamoprhism.从维基百科中,一个catamophism是"从初始代数到其他代数的独特同态.这个概念已经应用于函数式编程作为折叠".所以这似乎是公平的,但引导我将初始代数作为F-代数类别中的初始对象.

因此,如果Option上的折叠实际上是一个catamophism,那么需要有一些仿函数F来创建F代数的类别,其中Option将是初始对象.我无法弄清楚这个仿函数是什么.

对于类型列表,A仿函数F是F[X] = 1 + A * X.这是有道理的,因为List是一个递归数据类型,所以如果X是,List[A]那么上面读取的类型列表A是空列表(1),或(+)a 和a的一对(*).但Option不是递归的.只会(没什么或一个).所以我没看到仿函数在哪里.AList[A]Option[A]1 + AA

只是要清楚,我认识到,期权已经是一个仿函数,因为它需要A给Option[A],但是什么名单做是不同的,A是固定的,仿函数是用来描述如何构建递归的数据类型.

在一个相关的说明中,如果它不是一个catamorphism它可能不应被称为折叠,因为这会导致一些混乱.

我觉得理解一个仿函数的固定点的抽象概念,但是,我仍然在努力弄清楚它的确切实现及其在Haskell中的变形.

例如,如果我定义,如根据"程序员类别理论"一书 - 第359页,下面的代数

-- (Int, LiftF e Int -> Int)

data ListF e a = NilF | ConsF e a

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) -> n + 1
lenAlg NilF = 0

根据catamorphism的定义,可以将以下函数应用于ListF的固定点,即List,以计算其长度.

cata lenAlg :: [e] -> Int
cata lenAlg = lenAlg . fmap (cata lenAlg) . unFix

我有两个困惑.首先,如何Haskell编译知道名单是THE LISTF的固定点？我从概念上知道它是,但是编译器如何知道,即,如果我们定义另一个列表,那就是与List相同的一切,我打赌编译器不会自动推断出List'也是ListF的固定点,或者它？(我会感到惊讶).

其次,由于cata lenAlg的递归性质,它总是试图取消修复数据构造函数的外层以暴露仿函数的内层(我的解释是否正确？).但是,如果我们已经在叶子上,我们怎么能调用这个函数调用呢？

fmap (cata lenAlg) Nil

举个例子,有人可以帮助为下面的函数调用写一个执行跟踪来澄清吗？

cata lenAlg Cons 1 (Cons 2 Nil)

我可能遗漏了一些显而易见的事情,但是我希望这个问题对于其他有类似困惑的人来说仍然有意义.

回答总结

@nm回答了我的第一个问题,指出为了让Haskell编译器弄清楚Functor A是Functor B的一个固定点,我们需要明确.在这种情况下,它是

type …

我最近阅读了关于递归方案的描述，其中将同构同构描述为广义foldr。

是否可以在所有情况下Foldable（通过foldr或foldMap）编写一个实例cata？