haskell - F# 中的变质

Question

我正在阅读关于 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# 中完成吗？

Answer 1

如果您正在考虑直接在 F#（或 CLR）类型系统中表达对任意容器类型（a'la recursion scheme ）的真正通用折叠，那么您就不走运了。语言中缺少太多必需的机制——最关键的是高级类型。

但是，可以使用称为defunctionalization的技术在 F# 中对 HKT 进行编码。有一个基于本文概念的 F# 库 - Higher。事实上，它已经实现了fix、cata/ana/hylomorphisms和代数作为概念证明。不过，在性能和易用性方面，我没有很好的衡量标准。

除此之外，您可以手动实现专门用于容器的折叠，从而无需 HKT。到目前为止，这里有一篇关于实现变态的经典博客文章。非常值得一读——除了折叠之外，它还深入到了延续传递风格的编程中。