gpt4 book ai didi

haskell - 在 Haskell 中实现类型类时的任意类约束

转载 作者:行者123 更新时间:2023-12-03 14:24:46 25 4
gpt4 key购买 nike

我正在尝试实现一个简单的 Set在 Haskell 中,并且我对如何表达它包含的元素的类约束感到困惑。
Set type 类相当简单:

class Set s where
empty :: s a
isEmpty :: s a -> Bool
insert :: s a -> a -> s a
contains :: s a -> a -> Bool
Set 的简单实现是二叉搜索树:
data BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

但是,在声明正确的类约束时,我有点卡住了:
  • Set至少需要确定两个元素是否相等的能力——它的值需要有一个 Eq 的实例。 .
  • BinarySearchTree要求其元素具有 Ord 的实例,因为每个节点都需要左侧较小的元素和右侧较大的元素。

  • 第一个简单的解决方案是更新 Set的签名要求 a有一个 Eq 的实例:
    class Set s where
    empty :: Eq a => s a
    isEmpty :: Eq a => s a -> Bool
    insert :: Eq a => s a -> a -> s a
    contains :: Eq a => s a -> a -> Bool

    实现 Set 的实例为 BinarySearchTree不是问题: Ord暗示 Eq ,所以我可以“覆盖”类约束。

    但是,如果 BinarySearchTree需要一些奇特的类约束,这些约束与 Eq 完全不兼容。 ?我如何表达这些并让类型检查器满意?

    我能想到的唯一方法是在 BinarySearchTree 上添加类约束, 就像是:
    data Ord a => BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

    不幸的是,这似乎不能满足类型检查器:即使声明保证 BinarySearchTree必须包含带有 Ord 的元素例如,这个约束似乎没有延续到使用 BinarySearchTree 的函数。 - 就好像类约束只应用于数据构造函数,但后来被遗忘了。

    我错过了什么?我正在尝试做的事情是否有一个优雅的解决方案,甚至根本没有解决方案?

    最佳答案

    您正在询问 Haskell 中的一个众所周知的问题:如何定义类型类,以便类型类的实例可以定义类型类操作所需的类型类约束。这个问题经常以问题“为什么 Data.Set 不是 Functor 的实例?”的形式出现在论坛上。然后问题是Data.Set有一个 map 功能,附加 Ord约束:

    Data.Set.map :: Ord b => (a -> b) -> Set a -> Set b 

    而 Functor 的 fmap 方法看起来像
    class Functor f where
    fmap :: (a -> b) -> f a -> f b

    几年以来,问题的解决方案已经存在。一种解决方案将相对较新的扩展 ConstraintKinds 与 TypeFamilies 相结合。对于您的示例,它相当于这样:
    class Set s where
    type SetCt s a :: Constraint
    empty :: s a
    isEmpty :: s a -> Bool
    insert :: Ct a => s a -> a -> s a
    contains :: Ct a => s a -> a -> Bool

    BinarySearchTree 的实例看起来像
    instance Set BinarySearchTree where
    type SetCt BinarySearchTree a = Ord a
    ...

    这是一个 blog post作者 Dominic Orchard 更详细地解释了这些想法。

    关于haskell - 在 Haskell 中实现类型类时的任意类约束,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25422342/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com