如何根据 Haskell 中的类约束更改函数的行为？

Question

我有一个数据类型，表示一组与概率配对的值。起初，实现只是使用好的旧列表，但正如您想象的那样，这可能效率低下（例如，我使用树而不是列表来存储有序值）

经过一番研究，我想到了使用 GADTs

data Tree a b = Leaf | Node {left::Tree a b, val :: (a, b), right :: Tree a b}

data Prob a where
  POrd   ::Ord a => Tree a Rational -> Prob a
  PEq    ::Eq a => [(a, Rational)] -> Prob a
  PPlain ::[(a, Rational)] -> Prob a

到现在为止还挺好。我现在坚持尝试为我的新数据类型创建一个智能构造函数，它需要[(a,Rational)]并根据 的约束为a选择正确的构造函数Prob。基本上：

prob :: [(a, Rational)] -> Prob a
-- chooses the "best" constructor based on the constraints of a

这是可能吗？如果没有，我应该如何设计更好的东西？我错过了什么吗？

谢谢！

Answer 1

无法执行“T类中的类型是否C？”形式的检查。在哈斯克尔。这里的问题是，很难对这样的问题做出否定的回答并允许单独编译：T可能在C一个模块的范围内，但不在另一个模块的范围内，从而导致相当脆弱的语义。

为了确保一致性，Haskell 只允许require约束，否则会引发编译时错误。

据我所知，您能做的最好的事情就是使用另一个自定义类型类，它会告诉您哪种情况是最好的。例如

{-# LANGUAGE AllowAmbiguousTypes, TypeApplications, ScopedTypeVariables #-}

data BestConstraint a where
   BCOrd  :: Ord a => BestConstraint a
   BCEq   :: Eq a => BestConstraint a
   BCNone :: BestConstraint a

class BC a where
   bestC :: BestConstraint a

instance BC Int where bestC = BCOrd
-- ... etc.
instance BC a => BC [a] where
   bestC = case bestC @a of
       BCOrd  -> BCOrd
       BCEq   -> BCEq
       BCNone -> BCNone

prob :: forall a . BestConstraint a => [(a, Rational)] -> Prob a
prob xs = case bestC @a of
    BCOrd  -> POrd ....  -- build the tree
    BCEq   -> PEq xs
    BCNone -> PPlain xs

不过，您必须为您想要使用的任何类型提供一个实例。