haskell - GHC:无法推断幻像类型参数

Question

所以我试图为可变长度元组创建一种类型，基本上作为 Either a (Either (a,b) (Either (a,b,c) ...)) 的更漂亮版本 和要么 (要么(要么... (x,y,z)) (y,z)) z。

{-# LANGUAGE TypeOperators, TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-}
module Temp where

-- type level addition
data Unit
data Succ n

class Summable n m where
  type Sum n m :: *

instance Summable Unit m where
  type Sum Unit m = Succ m

instance Summable n m => Summable (Succ n) m where
  type Sum (Succ n) m = Succ (Sum n m)

-- variable length tuple, left-to-right
data a :+ b = a :+ Maybe b
infixr 5 :+

class Prependable t r s where
  type Prepend t r s :: *
  prepend :: r -> Maybe s -> Prepend t r s

instance Prependable Unit x y where
  type Prepend Unit x y = x :+ y
  prepend = (:+)

instance Prependable n x y => Prependable (Succ n) (w :+ x) y where
  type Prepend (Succ n) (w :+ x) y = w :+ Prepend n x y
  prepend (w :+ Nothing) _ = w :+ Nothing
  prepend (w :+ Just x) y = w :+ Just (prepend x y)

-- variable length tuple, right-to-left
data a :- b = Maybe a :- b
infixl 5 :-

class Appendable t r s where
  type Append t r s :: *
  append :: Maybe r -> s -> Append t r s

instance Appendable Unit x y where
  type Append Unit x y = x :- y
  append = (:-)

instance Appendable n x y => Appendable (Succ n) x (y :- z) where
  type Append (Succ n) x (y :- z) = Append n x y :- z
  append _ (Nothing :- z) = Nothing :- z
  append x (Just y :- z) = Just (append x y) :- z

但是，在递归情况下，编译器似乎无法推断出 prepend 或 append 的幻像类型参数:

Temp.hs:32:40:
    Could not deduce (Prepend t1 x y ~ Prepend n x y)
    from the context (Prependable n x y)
      bound by the instance declaration at Temp.hs:29:10-61
    NB: `Prepend' is a type function, and may not be injective
    In the return type of a call of `prepend'
    In the first argument of `Just', namely `(prepend x y)'
    In the second argument of `(:+)', namely `Just (prepend x y)'

Temp.hs:49:34:
    Could not deduce (Append t0 x y ~ Append n x y)
    from the context (Appendable n x y)
      bound by the instance declaration at Temp.hs:46:10-59
    NB: `Append' is a type function, and may not be injective
    In the return type of a call of `append'
    In the first argument of `Just', namely `(append x y)'
    In the first argument of `(:-)', namely `Just (append x y)'

我可以做些什么来帮助编译器做出这个推断吗？

Answer 1

此处错误消息的重要部分是:

NB: `Prepend' is a type function, and may not be injective

这是什么意思？这意味着可能有多个 instance Prependable ，它们的 type Prepend ... = a，因此，如果您推断某些 Prepend 为a，你不一定知道它属于哪个实例。

您可以使用 data types in type families 来解决此问题，它的优点是您不处理类型函数，它们是满射的，但可能是单射的，而是处理类型“关系”，它们是双射的(因此每个 Prepend 类型只能属于一个类型族，并且每个类型族都有一个不同的 Prepend 类型)。

(如果您希望我展示类型系列中数据类型的解决方案，请发表评论!基本上，只需使用 data Prepend 而不是 type Prepend)