用于列表< - >元组转换的类型类

Question

我有一组函数可以在元组和列表之间进行转换:

pack2 :: [a] -> (a, a)
pack2 (a:b:_) = (a, b)

unpack2 :: (a, a) -> [a]
unpack2 (a, b) = [a, b]

pack3 :: [a] -> (a, a, a)
pack3 (a:b:c:_) = (a, b, c)

unpack3 :: (a, a, a) -> [a]
unpack3 (a, b, c) = [a, b, c]

-- and so on

我想稍微概括一下,以便以下可能:

packN [1, 2, 3, 4] :: (Int, Int) -- => (1, 2)

unpackN (1, 2, 3) -- => [1, 2, 3]

我试图像这样解决它:

class Pack a b where
  packN :: a -> b
  unpackN :: b -> a

instance Pack [a] (a, a) where
  packN = pack2
  unpackN = unpack2

instance Pack [a] (a, a, a) where
  packN = pack3
  unpackN = unpack3

它确实编译时没有任何错误(MultiParamTypeClasses, FlexibleInstances已启用),但是,在尝试使用时,它会失败:

> unpackN (1, 2)

<interactive>:84:1:
    Could not deduce (Pack a (t0, t1))
      arising from the ambiguity check for ‘it’
    from the context (Pack a (t, t2), Num t2, Num t)
      bound by the inferred type for ‘it’:
                 (Pack a (t, t2), Num t2, Num t) => a
      at <interactive>:84:1-14
    The type variables ‘t0’, ‘t1’ are ambiguous
    When checking that ‘it’
      has the inferred type ‘forall a t t1.
                             (Pack a (t, t1), Num t1, Num t) =>
                             a’
    Probable cause: the inferred type is ambiguous

我怎样才能使它工作？

Answer 1

unpack我必须以某种方式推断输入类型的返回类型,所以让我们看看如何做到这一点(pack总是[a]作为输入,所以我们不可能从中推断出任何东西).

首先,我们可以声明一个功能依赖:

class Unpack tup a | tup -> a where
    unpack :: tup -> [a]

在这里,我们承诺,我们只能Unpack以一种a始终明确无法推断的方式编写实例tup.因此,当我们写作时unpack (a, b),返回类型将从类型中明显(a, b),并且一切都会很好.

instance Unpack (a, a) a where
   unpack (a, b) = [a, b]

其次,我们只能通过元组类型对类进行参数化,并使用类型族显式计算它的元素类型:

class Unpack tup where
    type Elem tup
    unpack :: tup -> [Elem tup]

instance Unpack (a, a) where
    type Elem (a, a) = a
    unpack (a, b) = [a, b]

但是,还有一件事需要解决.目前,如果元素类型是多态的,unpack在没有类型注释的情况下不起作用:

unpack (1, 2) -- type error 

这是因为数字有类型Num a => a,也(1, 2)可能有类型(Int, Float),这不是我们在实例中指定的类型.我们的instance Unpack (a, a)比赛,只有当它是明显的,我们有相同的混凝土,单态类型的元组.

通常,仅根据实例头的形式选择实例(这里实例头是tup类型instance Unpack tup),并且仅在此之后GHC检查实例约束是否成立.我们可以使用它来获得我们的优势:即使对于元组中的类型不同的情况,我们也可以确保我们有一个实例,然后使用实例约束来强制类型相同:

-- I assume we use the functional dependencies version here
instance a ~ b => Unpack (a, b) a where
    unpack (a, b) = [a, b]

现在unpack总是没有注释.

写出大元组的所有类型相等约束可能有点麻烦:

instance (a ~ b, b ~ c, c ~ d) => Unpack (a, b, c, d) a where
    unpack (a, b, c, d) = [a, b, c, d]

幸运的是,我们可以使用ConstraintKinds和键入族来写出等式的简写:

{-# LANGUAGE 
    ConstraintKinds, DataKinds, TypeOperators, TypeFamilies,
    MultiParamTypeClasses, FunctionalDependencies, UndecidableInstances #-}

import GHC.Exts

type family AllSame (xs :: [*]) :: Constraint where
    AllSame '[]  = ()
    AllSame '[a] = ()
    AllSame (a ': b ': xs) = (a ~ b, AllSame (b ': xs))

...

instance AllSame [a, b, c, d] => Unpack (a, b, c, d) a where
    unpack (a, b, c, d) = [a, b, c, d]

这里要知道的是,ConstraintKinds通过将元组类型视为约束的连接以及()始终满足的空约束来工作.AllSame只是一个类型级别的函数,扩展到一个等同于我们之前手写的约束.