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)类型系统中的一个递归方案 - 你运气不好.语言中缺少太多必需的机器 - 最重要的是更高级的类型.

然而,HKT可以使用称为defunctionalization的技术在F#中编码.有一个基于本文概念的F#库 - 更高.事实上,它已经实现了fix,cata/ana/hylomorphisms和代数作为概念的证明.虽然在性能和易用性方面都没有很好的衡量标准.

除此之外,您可以手动实现专门为您的容器设置的折叠,从而避免了对HKT的需求.现在有一系列关于在这里实施catamorphisms的博客文章.这是值得一读的 - 除了折叠之外,它还深入到延续传递风格的编程中.