5

所以我正在尝试为可变长度元组创建一个类型，基本上是作为Either a (Either (a,b) (Either (a,b,c) ...))and的更漂亮的版本Either (Either (Either ... (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)'

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

4

2 回答 2

7

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

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

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

您可以通过使用类型族中的数据类型来解决这个问题，它的优点是您不处理类型函数，它们是满射但可能是单射的，而是使用类型“关系”，它是双射的（所以每个Prepend类型都可以只属于一个类型族，每个类型族都有不同的Prepend类型）。

（如果您希望我展示类型族中数据类型的解决方案，请发表评论！基本上，只需使用 adata Prepend而不是type Prepend）

于 2012-01-16T22:19:12.357 回答
1

我想出的解决方案是在 tieprepend和appendphantom 参数中添加一个虚拟参数：

-- as above, except...

unsucc :: Succ n -> n
unsucc _ = undefined

class Prependable t r s where
  type Prepend t r s :: *
  prepend :: t -> 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 t (w :+ Just x) y = w :+ Just (prepend (unsucc t) x y)

class Appendable t r s where
  type Append t r s :: *
  append :: t -> 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 t x (Just y :- z) = Just (append (unsucc t) x y) :- z
于 2012-01-16T23:38:42.093 回答