F#中的Catamorphism

Question

F#中的Catamorphism

15

我正在阅读维基百科上有关“catamorphisms”（一种函数式编程概念）的文章，目前我已经能够在 F# 中复制 Haskell 的示例，但有一个部分我还没做到：

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

在F#中是否可能做到这一点？

- Mario

6

你可以为特定的数据类型（例如 List.fold）定义它，但不能像你引用的示例一样通用地定义它。 - Benjamin Hodgson

2

这需要更高的种类：大致上，它可以定义 T f = f Bool，其中 f : *->*。你可以在 Haskell 或 Scala 中实现，但我不知道 F# 是否允许这样做。 - chi

2

它并不适用于除了基于去功能化编码之外的其他情况。 - scrwtp

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- scrwtp · Accepted Answer

如果你想要在F#（或CLR）类型系统内直接表达关于任意容器类型的通用递归方案，那就太遗憾了。这种语言缺少太多所需的机制，其中最重要的是高阶类型。

不过，可以使用一种叫做解函数化的技术在F#中编码HKT。基于该论文的概念，已经有一个名为Higher的F#库实现了fix，cata / ana / hylomorphisms和代数的概念验证。我对它在性能和易用性方面的表现没有很好的评估。

除此之外，你可以手动实现专门针对你的容器的折叠，避免使用HKT。这里有一系列经典的博客文章介绍如何实现消解型态，值得一读 - 除了折叠，还深入探讨了以延续传递样式进行编程的方法。