如果您将数据类型视为函子的固定点,那么您可以看到您的定义是列表情况的合理概括。
module Unfold where
这里我们从定义函子的不动点开始f
: 这是一层f
接下来是一些更多的修复点:
newtype Fix f = InFix { outFix :: f (Fix f) }
为了让事情更清楚一些,这里是与列表和树相对应的函子的定义。它们的形状与数据类型基本相同,只是我们用额外的参数替换了递归调用。换句话说,他们描述了什么一层列表/树看起来像并且在可能的子结构上是通用的r
.
data ListF a r = LNil | LCons a r
data TreeF a r = TNil | TLeaf a | TBranch r r
列表和树分别是 ListF 和 TreeF 的固定点:
type List a = Fix (ListF a)
type Tree a = Fix (TreeF a)
无论如何,希望您现在对这个固定点业务有更好的直觉,我们可以看到有一种定义固定点的通用方法unfold
对于这些功能。
给定一个原始种子以及一个获取种子和构建的函数一层 of f
当递归结构是新的种子时,我们可以构建一个完整的结构:
unfoldFix :: Functor f => (s -> f s) -> s -> Fix f
unfoldFix node = go
where go = InFix . fmap go . node
这个定义专门针对通常的unfold
在列表或您对树的定义中。换句话说:你的定义确实是正确的。