haskell - 如何使用递归方案更新结构?
问题描述
在递归方案中,我怎样才能用类型定义来构造一些东西,比如(Recursive t, CoRecursive t) -> t -> ? -> t
我尝试使用递归方案来更新节点。以列表为例,我可以想出两种方法:
update :: [a] -> Natural -> a -> [a]
update = para palg where
palg Nil _ _ = []
palg (Cons a (u, _)) 0 b = b : u
palg (Cons a (u, f)) n b = a : f (n-1) b
update' :: [a] -> Natural -> a -> [a]
update' = c2 (apo acoalg) where
c2 f a b c = f (a,b,c)
acoalg ([], _, _) = Nil
acoalg (_:as , 0, b) = Cons b $ Left as
acoalg (a:as , n, b) = Cons a $ Right (as, n-1, b)
但是,这两种实现都很好。在这两个实现中, 和 的构造函数ListF
出现[]
在等式的两边。而且这个定义似乎不是唯一的。有没有更好的方法来使用递归方案执行列表更新?
解决方案
递归方案是灵活的方法。您还可以实现自己的变体。
(重用cata
)
zipo :: (Recursive g, Recursive h) => (Base g (h -> c) -> Base h h -> c) -> g -> h -> c
zipo alg = cata zalg
where
zalg x = alg x <<< project
update :: forall a. [a] -> Natural -> a -> [a]
update xs n a = zipo alg n xs
where
alg :: Maybe ([a] -> [a]) -> ListF a [a] -> [a]
alg _ Nil = []
alg Nothing (Cons y ys) = a:ys
alg (Just n') (Cons y ys) = y:(n' ys)
你也可以实现一些并行版本,比如
zipCata :: (Recursive g, Recursive h) => ((g -> h -> r) -> Base g g -> Base h h -> r) -> g -> h -> r
zipCata phi x y = phi (zipCata phi) (project x) (project y)
update' :: forall a. [a] -> Natural -> a -> [a]
update' xs n a = zipCata alg n xs
where
alg :: (Natural -> [a] -> [a]) -> Maybe Natural -> ListF a [a] -> [a]
alg _ _ Nil = []
alg _ Nothing (Cons _ ys) = a:ys
alg f (Just n) (Cons y ys) = y:(f n ys)
两种变体(也作为您的)将得到相同的结果
PS。我讨厌 SO 上的代码示例方法
推荐阅读
- ruby-on-rails - 如何防止工作每小时发送邮件超过一次?
- reactjs - Webpack:跨 html 页面的捆绑拆分与跨客户端路由的代码拆分
- php - 如何在作曲家中丢弃缓存中的负载
- eclipse - Eclipse 4.4 在 MacOS 上意外退出 - 从终端运行时有效
- xml - 在 XML 中,如何/为什么在定义名称空间之前使用它?
- ios - 在IOS中使用NSPredicate通过数组的一个元素过滤数组的NSArray
- python - 如何使用变量字符串数据在python中动态创建列表字典
- javascript - npm 从下拉列表中输入用户选择的选项
- html - 在两个地方有相同的单选按钮
- facebook - 启用 facebook 连接的最受限制的内容安全策略是什么