使受约束的函数成为类型类实例

Question

我对Haskell还比较陌生，所以如果我没有完全正确地理解术语，我很抱歉。

我正试图使用Haskell编写一个线性时态逻辑的实现，其中可以构造一个表达式，然后将其应用于元素列表，以使用具有以下签名的函数生成布尔结果：

evaluate :: Expression a -> [a] -> Bool

Expression a是一种代数数据类型，定义如下：

data Expression a = Conjunction (Expression a) (Expression a)
| Disjunction (Expression a) (Expression a)
| Next (Expression a)
| Always (Expression a)
| Eventually (Expression a)
| Until (Expression a) (Expression a)
| Predicate (a -> Bool)
-- etc. etc.

这一切都很好，但我想通过定义智能构造函数来让构建表达式变得更优雅一点，理想情况下，它可以像这样使用：

numExpr :: Num a => Expression a
numExpr = eventually (== 10) `or` eventually (== 5)

到目前为止，我实现这一目标的尝试包括以下内容：

eventually :: Expressable e => e a -> Expression a
eventually = Eventually . expresss
or :: (Expressable e, Expressable f) => e a -> f a -> Expression a
or x y = Or (express x) (express y)
-- and so on
class Expressable e where
express :: e a -> Expression a
instance Expressable Expression where
express = id
-- This is what I'd like to do:
type Pred a = a -> Bool
instance Expressable Pred where
express = Predicate

然而，后者不起作用。我尝试过使用各种GHC扩展(自由类型同义词，类型同义词实例(，但似乎都不起作用。这种事情有可能吗，甚至是个好主意吗？类型系统不允许这种事情发生有充分的理由吗？有没有更好的方法来构建这种结构？

我知道我可以使用一个简短的函数名和p :: (a -> Bool) -> Expression a这样的签名，但这仍然感觉有点不雅。

Answer 1

在您的方法中，您需要将作为Pred参数的a链接到express签名中的a。这些必须是相同的，但在类/实例中不能要求这样做。

然而，你可以尝试这样的东西，上面有一堆扩展：

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
data Expression a = Conjunction (Expression a) (Expression a)
| Disjunction (Expression a) (Expression a)
| Next (Expression a)
| Always (Expression a)
| Eventually (Expression a)
| Until (Expression a) (Expression a)
| Predicate (a -> Bool)
class Expressable e a where
express :: e -> Expression a

instance Expressable (Expression a) a where
express = id
type Pred a = a -> Bool
instance Expressable (Pred a) a where
express = Predicate
eventually :: Expressable e a => e -> Expression a
eventually = Eventually . express
or :: (Expressable e a, Expressable f a) => e -> f -> Expression a
or x y = Disjunction (express x) (express y)

我不太相信使用这样的机制只是为了避免在原子公式上写Predicate是个好主意，但你可以试一下，看看它在实践中是否足够好。

Answer 2

newtype而不是type将起作用：

newtype Pred a = Pred (a -> Bool)
instance Expressable Pred where
express (Pred p) = Predicate p

在您的案例中，instance Expressable Pred where中的Pred是一个部分应用的类型同义词，这些基本上是不允许的(请参阅LiberalTypeSynonyms了解例外(。