Haskell class 和实例的正确类型

Question

我正在努力描述重写术语和文字（一阶逻辑）的含义。即我想要一个函数 applySubstitution ，它可以在术语和文字上调用。我认为替换可以表示为一个函数。但是，我收到以下代码的刚性类型变量错误。

{-# LANGUAGE UnicodeSyntax #-}

module Miniexample where
import qualified Data.Maybe as M

data Term a = F a [Term a]
            | V a

data Literal a = P a [Term a]
               | E (Term a) (Term a)

class Substitutable b where
  substitute :: b -> (Term a -> Maybe (Term a)) -> b

instance Substitutable (Term a) where
  substitute x@(V _) σ    = M.fromMaybe x (σ x)
  substitute f@(F l xs) σ = M.fromMaybe f' (σ f)
    where f' = F l (map (flip substitute σ) xs)

instance Substitutable (Literal a) where
  substitute (P l xs) σ = P l (map (flip substitute σ) xs)
  substitute (E s t) σ  = E (substitute s σ) (substitute t σ)

class Substitution σ where
  asSub :: σ -> (a -> Maybe a)

applySubstitution σ t = substitute t (asSub σ)

(<|) t σ = applySubstitution σ t

这给出了以下错误：

• Couldn't match type ‘a1’ with ‘a’
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      substitute :: forall a1.
                    Term a -> (Term a1 -> Maybe (Term a1)) -> Term a
    at /.../Miniexample.hs:16:3-12
  ‘a’ is a rigid type variable bound by
    the instance declaration
    at /.../Miniexample.hs:15:10-31
  Expected type: Term a1
    Actual type: Term a
• In the first argument of ‘σ’, namely ‘x’
  In the second argument of ‘M.fromMaybe’, namely ‘(σ x)’
  In the expression: M.fromMaybe x (σ x)
• Relevant bindings include
    σ :: Term a1 -> Maybe (Term a1)
      (bound at /.../Miniexample.hs:16:22)
    x :: Term a
      (bound at /.../Miniexample.hs:16:14)
    substitute :: Term a -> (Term a1 -> Maybe (Term a1)) -> Term a
      (bound at /.../Miniexample.hs:16:3)

在我看来，Substitutable class 中的类型变量 b 应该能够接受（我确定是错误的术语）[=18 的值=].

非常欢迎任何提示。

举一个更具体的例子，下面的工作，但需要明确调用哪个函数applyTermSub或applyLitSub，其次替换映射的实现泄漏到实现中的更一般的程序。

module Miniexample where
import qualified Data.Maybe as M
import qualified Data.List as L

data Term a = F a [Term a]
            | V a deriving (Eq)

data Literal a = P a [Term a]
               | E (Term a) (Term a) deriving (Eq)


termSubstitute :: (Term a -> Maybe (Term a)) -> Term a -> Term a
termSubstitute σ x@(V _)    = M.fromMaybe x (σ x)
termSubstitute σ f@(F l xs) = M.fromMaybe f' (σ f)
    where f' = F l (map (termSubstitute σ) xs)

litSubstitute :: (Term a -> Maybe (Term a)) -> Literal a -> Literal a
litSubstitute σ (P l xs) = P l (map (termSubstitute σ) xs)
litSubstitute σ (E s t)  = E (termSubstitute σ s) (termSubstitute σ t)

applyTermSub :: (Eq a) => Term a -> [(Term a, Term a)] -> Term a
applyTermSub t σ = termSubstitute (flip L.lookup σ) t

applyLitSub :: (Eq a) => Literal a -> [(Term a, Term a)] -> Literal a
applyLitSub l σ = litSubstitute (flip L.lookup σ) l

-- variables
x  = V "x"
y  = V "y"
-- constants
a  = F "a" []
b  = F "b" []
-- functions
fa = F "f" [a]
fx = F "f" [x]

σ = [(x,y), (fx, fa)]

test = (applyLitSub (P "p" [x, b, fx]) σ) == (P "p" [y, b, fa])

理想情况下，我希望有一个替换接口（即可以使用 Data.Map 等），其次我想要一个同时捕获术语和文字的替换函数。

Answer 1

您收到的错误是 instance Substitutable (Term a) 中指定的 Term a 与 σ 接受的 Term a 类型不同的投诉。这是因为 Haskell 在 substitute 函数上量化了 a，但没有在实例定义的其余部分上量化。因此 substitute 的实现必须接受一个 σ 来处理 Term a1 对于一些值 a1，这不能保证是您的实例所定义的特定 a。（是的，您的实例是在所有 a 上定义的...但是从实例定义的范围内来看，就好像选择了特定的 a。）

您可以通过类型构造函数而不只是类型来参数化您的 Substitutable class 并将相同的 a 传递给该类型构造函数来避免这种情况σ类型。

{-# LANGUAGE UnicodeSyntax #-}

import qualified Data.Maybe as M
import qualified Data.List as L

data Term a = F a [Term a]
            | V a deriving (Eq)

data Literal a = P a [Term a]
               | E (Term a) (Term a) deriving (Eq)

class Substitutable f where
  substitute :: f a -> (Term a -> Maybe (Term a)) -> f a

instance Substitutable Term where
  substitute x@(V _) σ    = M.fromMaybe x (σ x)
  substitute f@(F l xs) σ = M.fromMaybe f' (σ f)
    where f' = F l (map (flip substitute σ) xs)

instance Substitutable Literal where
  substitute (P l xs) σ = P l (map (flip substitute σ) xs)
  substitute (E s t) σ  = E (substitute s σ) (substitute t σ)

(<|) t σ = substitute t $ flip L.lookup σ


-- variables
x  = V "x"
y  = V "y"
-- constants
a  = F "a" []
b  = F "b" []
-- functions
fa = F "f" [a]
fx = F "f" [x]

σ = [(x,y), (fx, fa)]


main = print $ show $ (P "p" [x, b, fx] <| σ) == P "p" [y, b, fa]

Haskell class 和实例的正确类型

Haskell correct types for class and instance

haskell

class

instance