Haskell 多重函子
我正在 Haskell 中实现斐波那契堆，但我不确定具体的干净方法是什么。
例如，我想订购节点。所以我可以做类似的事情：
instance Ord (FibNode e) where
f1 `compare` f2 = (key f1) `compare` (key f2)
如果我将 FibNode 设为 monad，这会更容易完成。但其他时候我想折叠节点的兄弟节点，或者折叠它们的子节点等。因此定义一个函子，其中 fx = f $ key x 并不总是有效。
除了定义我自己的fmapKey、fmapSibs、fmapKids...还有其他方法可以做到这一点吗？
I'm making a fibonacci heap implementation in Haskell, and I'm not sure exactly what the clean way to do it.
For example, I want to order the nodes. So I can do something like:
instance Ord (FibNode e) where
f1 `compare` f2 = (key f1) `compare` (key f2)
This would be more easily done if I made FibNode a monad. But other times I want to fold across the node's siblings, or fold across their children etc. So defining a functor where f x = f $ key x won't work all the time.
Apart from defining my own fmapKey, fmapSibs, fmapKids... is there a way to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您不能以多种方式使类型构造函数成为 Functor 的实例。
但是您可以围绕您的类型创建各种新类型包装器，每个包装器都有自己的 Functor 实例。但这并不比定义自己的 fmap 函数更方便。
You can't make a type constructor an instance of Functor in more than one way.
But you can make various newtype wrappers around your type that each has its own Functor instance. But that's not really any more convenient than defining your own fmap functions.
（斐波那契）堆本质上是一种不纯的、破坏性更新的数据结构，具有针对各种操作的特定渐近运行时保证就在上面。如果您可以通过直接翻译为纯版本来维持这些保证，我会感到惊讶。我的建议是使用 ST 或 IO 数组等使其成为不纯数据结构。这将使经典算法的实现更加直接。
The (Fibonacci) heap is an inherently impure, destructively-updated data structure with specific asymptotic runtime guarantees for various operations on it. I would be surprised if you can maintain these guarantees with a straightforward translation to a pure version. My suggestion would be to to make it an impure data structure using something like the ST or IO arrays. This would make for a much more direct implementation of the classic algorithms.