一旦我有了F代数，我可以定义Foldable和Traversable？

本文介绍了一旦我有了F代数，我可以定义Foldable和Traversable？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我已经按照Bartosz Milewski的文章（ F-Algebra rel =noreferrer>一个，两个）： / em> 模块代数其中 数据Expr a =分支[a] | Leaf Int 实例Functor Expr其中 fmap f（分支xs）=分支（fmap f xs） fmap _（Leaf i）= Leaf i newtype修复a =修复{unFix :: a（修复a）} 分支=修复。分支 leaf =修复。叶 - |这是一个例子代数。 evalSum（Branch xs）= sum xs evalSum（Leaf i）= i cata f = f。 fmap（cata f）。 unFix 现在我可以做任何我想做的事情，例如，总结叶子： λcata evalSum $ branch [branch [leaf 1，leaf 2]，leaf 3] 6 这是我特意为这个问题所做的一个人为设计的例子，但我实际上尝试了一些不那么简单的事情（例如使用任意数量的变量评估和简化多项式），它就像一个魅力。一个人可以用一个适当选择的代数折叠和替换结构中的任何部分，就像运行变形一样。所以，我很肯定F代数包含了Foldable，它甚至包含Traversable。现在，我可以定义Foldable / Traversable F代数中的实例？ 在我看来，我不能。 我只能在初始代数上运行一个变形，它是一个空类型的构造函数。我给它的代数有一个类型 a b - > b 而不是 a - > b ，也就是说，in和out类型之间存在函数依赖关系。 看到代数a =>在类型签名的任何位置可以折叠。如果没有这样做，那一定是不可能的。 在我看来，我无法定义 Foldable 就F代数而言，因为 Expr 必须是一个 Functor 在两个变量中：一个用于载体，另一个用于值，然后是第二个 Foldable 。所以，它可能是一个 bifunctor 更合适。我们还可以构造一个带双折射函数的F代数： module Algebra2其中 导入Data.Bifunctor data Expr ai =分支[a] |叶子 实例Bifunctor Expr其中 bimap f _（Branch xs）=分支（fmap f xs） bimap _g（Leaf i）= Leaf（gi） newtype Fix2 ai = Fix2 {unFix2 :: a（Fix2 ai）i} 分支= Fix2。分支 leaf = Fix2。 Leaf evalSum（Branch xs）= sum xs evalSum（Leaf i）= i cata2 f g = f。 bimap（cata2 f g）g。 unFix2 运行方式如下： λcata2 evalSum（+1）$ branch [branch [leaf 1，leaf 2]，leaf 3] 9 但我仍然无法定义可折叠。它会有这样的类型： instance Foldable \i - > Expr（Fix2 Expr i）我在哪里... 不幸的是，我们没有得到lambda抽象类型，并且没有办法将隐式类型变量同时放在两个地方。 我不知道该怎么做。 解决方案 F-algebra定义了一个用于在评估所有子项之后评估单一递归数据结构级别的配方。 Foldable 定义了一种评估（不一定是递归）数据结构的方法，只要您知道如何将存储在其中的值转换为monoid的元素。对于递归数据结构，为了实现 foldMap ，您可以先定义一个代数，其载体是一个幺半群。您将定义如何将叶子转换为monoidal值。然后，假设一个节点的所有子节点都被评估为monoidal值，您可以定义一种在节点中组合它们的方法。一旦你定义了这样一个代数，你可以运行一个变形来评估整棵树的 foldMap 。 所以你的问题的答案是，为定点数据结构做一个 Foldable 实例，你必须定义一个适当的代数，其载体是monoid。 编辑：这是一个Foldable的实现： 数据Expr ea =分支[a] | Leaf e newtype Ex e = Ex {unEx :: Fix（Expr e）} evalM :: Monoid m => （e - > m） - >代数（Expr e）m evalM _（Branch xs）= mconcat xs evalM f（Leaf i）= fi 实例可折叠（Ex）其中 foldMap f = cata（evalM f）。 unEx 树:: Ex Int tree = Ex $ branch [branch [leaf 1，leaf 2]，leaf 3] x = foldMap Sum tree 实现 Traversable 作为变形因为你想要的结果不仅仅是一个总结 - 它必须包含完整的重构数据结构。因此，代数的载体必须是遍历的最终结果的类型，它是（f（Fix（Expr b））） code>，其中 f 是 Applicative 。 tAlg :: Applicative f => （e - > f b） - >代数（Expr e）（f（Fix（Expr b））） 下面是这个代数： p tAlg g（Leaf e）= leaf< $> g e tAlg _（分支xs）=分支< $> sequenceA xs 这就是您如何实现遍历： 实例Traversable Ex其中遍历g = fmap Ex。 cata（tAlg g）。 unEx Traversable 的超类是一个 Functor ，所以你需要证明定点数据结构是一个函子。你可以通过实现一个简单的代数并在其上运行一个变形来实现： fAlg ::（a - > b） - >代数（Expr a）（Fix（Expr b）） falg g（Leaf e）= leaf（ge） fAlg _（Branch es）=分支 实例函子例如 fmap g = Ex。 cata（fAlg g）。 unEx （Michael Sloan帮我写了这段代码。） I have defined an F-Algebra, as per Bartosz Milewski's articles (one, two):(This is not to say my code is an exact embodiment of Bartosz's ideas, it's merely my limited understanding of them, and any faults are mine alone.)module Algebra wheredata Expr a = Branch [a] | Leaf Intinstance Functor Expr where fmap f (Branch xs) = Branch (fmap f xs) fmap _ (Leaf i ) = Leaf inewtype Fix a = Fix { unFix :: a (Fix a) }branch = Fix . Branchleaf = Fix . Leaf-- | This is an example algebra.evalSum (Branch xs) = sum xsevalSum (Leaf i ) = icata f = f . fmap (cata f) . unFixI can now do pretty much anything I want about it, for example, sum the leaves:λ cata evalSum $ branch [branch [leaf 1, leaf 2], leaf 3]6This is a contrived example that I made up specifically for this question, but I actually tried some less trivial things (such as evaluating and simplifying polynomials with any number of variables) and it works like a charm. One may indeed fold and replace any parts of a structure as one runs a catamorphism through, with a suitably chosen algebra. So, I am pretty sure an F-Algebra subsumes a Foldable, and it even appears to subsume Traversable as well.Now, can I define Foldable / Traversable instances in terms of an F-Algebra?It seems to me that I cannot.I can only run a catamorphism on an initial algebra, which is a nullary type constructor. And the algebra I give it has a type a b -> b rather than a -> b, that is to say, there is a functional dependency between the "in" and "out" type.I don't see an Algebra a => Foldable a anywhere in type signatures. If this is not done, it must be impossible.It seems to me that I cannot define Foldable in terms of an F-Algebra for the reason that an Expr must for that be a Functor in two variables: one for carrier, another for values, and then a Foldable in the second. So, it may be that a bifunctor is more suitable. And we can construct an F-Algebra with a bifunctor as well:module Algebra2 whereimport Data.Bifunctordata Expr a i = Branch [a] | Leaf iinstance Bifunctor Expr where bimap f _ (Branch xs) = Branch (fmap f xs) bimap _ g (Leaf i ) = Leaf (g i)newtype Fix2 a i = Fix2 { unFix2 :: a (Fix2 a i) i }branch = Fix2 . Branchleaf = Fix2 . LeafevalSum (Branch xs) = sum xsevalSum (Leaf i ) = icata2 f g = f . bimap (cata2 f g) g . unFix2It runs like this:λ cata2 evalSum (+1) $ branch [branch [leaf 1, leaf 2], leaf 3]9But I still can't define a Foldable. It would have type like this:instance Foldable \i -> Expr (Fix2 Expr i) i where ...Unfortunately, one doesn't get lambda abstractions on types, and there's no way to put an implied type variable in two places at once.I don't know what to do. 解决方案 An F-algebra defines a recipe for evaluating a single level of a recursive data structure, after you have evaluated all the children. Foldable defines a way of evaluating a (not necessarily recursive) data structure, provided you know how to convert values stored in it to elements of a monoid. To implement foldMap for a recursive data structure, you may start by defining an algebra, whose carrier is a monoid. You would define how to convert a leaf to a monoidal value. Then, assuming that all children of a node were evaluated to monoidal values, you'd define a way to combine them within a node. Once you've defined such an algebra, you can run a catamorphism to evaluate foldMap for the whole tree. So the answer to your question is that to make a Foldable instance for a fixed-point data structure, you have to define an appropriate algebra whose carrier is a monoid.Edit: Here's an implementation of Foldable:data Expr e a = Branch [a] | Leaf enewtype Ex e = Ex { unEx :: Fix (Expr e) }evalM :: Monoid m => (e -> m) -> Algebra (Expr e) mevalM _ (Branch xs) = mconcat xsevalM f (Leaf i ) = f iinstance Foldable (Ex) where foldMap f = cata (evalM f) . unExtree :: Ex Inttree = Ex $ branch [branch [leaf 1, leaf 2], leaf 3]x = foldMap Sum treeImplementing Traversable as a catamorphism is a little more involved because you want the result to be not just a summary--it must contain the complete reconstructed data structure. The carrier of the algebra must therefore be the type of the final result of traverse, which is (f (Fix (Expr b))), where f is Applicative. tAlg :: Applicative f => (e -> f b) -> Algebra (Expr e) (f (Fix (Expr b)))Here's this algebra:tAlg g (Leaf e) = leaf <$> g etAlg _ (Branch xs) = branch <$> sequenceA xsAnd this is how you implement traverse:instance Traversable Ex where traverse g = fmap Ex . cata (tAlg g) . unExThe superclass of Traversable is a Functor, so you need to show that the fixed-point data structure is a functor. You can do it by implementing a simple algebra and running a catamorphism over it:fAlg :: (a -> b) -> Algebra (Expr a) (Fix (Expr b))fAlg g (Leaf e) = leaf (g e)fAlg _ (Branch es) = branch esinstance Functor Ex where fmap g = Ex . cata (fAlg g) . unEx(Michael Sloan helped me write this code.) 这篇关于一旦我有了F代数，我可以定义Foldable和Traversable？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！