haskell - 如何使用受约束的元素制作异构列表(又名 HLists)？

Question

我一直在尝试使用类型族来抽象 UI 工具包。当我尝试使用 HLists (http://homepages.cwi.nl/~ralf/HList/) 来改进 API 时，我陷入了困境。

我的 API 最初看起来像这样:

{-# LANGUAGE TypeFamilies #-}

class UITK tk where
  data UI tk :: * -> *

  stringEntry :: (UITK tk) => UI tk String
  intEntry :: (UITK tk) => UI tk Int

  tuple2UI :: (UI tk a,UI tk b) -> (UI tk (a,b))
  tuple3UI :: (UI tk a,UI tk b,UI tk c) -> (UI tk (a,b,c))
  tuple4UI :: (UI tk a,UI tk b,UI tk c,UI tk d) -> (UI tk (a,b,c,d))

ui :: (UITK tk) => (UI tk (String,Int)) 
ui = tuple2UI (stringEntry,intEntry)

这可行，但 UI 组合器适用于元组，因此我需要为每个元组大小设置不同的函数。我以为我可以使用 HLists 之类的东西，但要么是不可能的，要么(或希望)我只是缺少必要的 type-fu。

这是我的尝试:

{-# LANGUAGE TypeFamilies,FlexibleInstances,MultiParamTypeClasses #-}

-- A heterogeneous list type 

data HNil = HNil deriving (Eq,Show,Read)
data HCons e l = HCons e l deriving (Eq,Show,Read) 

-- A list of UI fields, of arbitrary type, but constrained on their
-- tk parameter. The StructV associated type captures the return
-- type of the combined UI

class (UITK tk) => FieldList tk l
  where type StructV tk l

instance (UITK tk) => FieldList tk HNil
  where type StructV tk HNil = HNil

instance (UITK tk, FieldList tk l) => FieldList tk (HCons (UI tk a) l)
  where type StructV tk (HCons (UI tk a) l) = (HCons a (StructV tk l))

fcons :: (UITK tk, FieldList tk l) => UI tk a -> l  -> HCons (UI tk a) l
fcons = HCons

-- Now the abstract ui toolkit definition

class UITK tk where
    data UI tk :: * -> *

    stringEntry :: (UITK tk) => UI tk String
    intEntry :: (UITK tk) => UI tk Int

    structUI :: (FieldList tk l) => l -> (UI tk (StructV tk l))

-- this doesn't work :-(

ui :: (UITK tk) => (UI tk (HCons String (HCons Int HNil)))
ui = structUI (fcons stringEntry
              (fcons intEntry
              HNil ))

最后的定义给了我几个错误，其中第一个是:

Z.hs:38:6:
    Could not deduce (FieldList
                        tk (HCons (UI tk0 String) (HCons (UI tk1 Int) HNil)))
      arising from a use of `structUI'
    from the context (UITK tk)
      bound by the type signature for
                 ui :: UITK tk => UI tk (HCons String (HCons Int HNil))
      at Z.hs:(38,1)-(40,21)
    Possible fix:
      add (FieldList
             tk
             (HCons
                (UI tk0 String) (HCons (UI tk1 Int) HNil))) to the context of
        the type signature for
          ui :: UITK tk => UI tk (HCons String (HCons Int HNil))
      or add an instance declaration for
         (FieldList tk (HCons (UI tk0 String) (HCons (UI tk1 Int) HNil)))
    In the expression:
      structUI (fcons stringEntry (fcons intEntry HNil))
    In an equation for `ui':
        ui = structUI (fcons stringEntry (fcons intEntry HNil))

在没有完全理解这一点的情况下，我想我至少可以看到其中一个问题。我没有成功地通知编译器上面的 3 个 tk 类型参数都是相同的类型(即它指的是 tk、tk0、tk1)。我不明白这一点-我的 fcons 构造函数旨在使构造的 HList 的 UI tk 参数保持一致。

这是我对类型族和多参数类型类的第一次体验，所以我很可能遗漏了一些基本的东西。

是否可以构造具有约束元素的异构列表？我哪里错了？

Answer 1

类型错误来自这个逻辑链:'ui'有'structui'最外层，'structUI::(FieldList tk l) =>'需要'(FieldList tk l)'，其中'tk'和'l'必须匹配您为“ui”编写的类型签名。

在类型变量“tk”中，一切都是单独的多态的。

类型检查器为 structui/fcons 的参数提供了不同的 tk0，并且仅仅因为您有一个匹配 tk 的实例并不意味着我不会出现并创建一个具有不同 tk 的 FieldList 实例。因此类型检查器被卡住了。

以下是我可以为类型检查器解决此问题的方法:

-- Use this instance instead of the one you wrote
instance (UITK tk, FieldList tk l, tk ~ tk') => FieldList tk (HCons (UI tk' a) l)
  where type StructV tk (HCons (UI tk' a) l) = (HCons a (StructV tk l))

-- Now this works :)
ui :: (UITK tk) => (UI tk (HCons String (HCons Int HNil)))
ui = structUI (fcons stringEntry
              (fcons intEntry
              HNil ))

替换实例匹配 tk 和 tk' 的所有可能组合，然后要求它们相同。没有人会出现并编写另一个这样的实例而不重叠。

回复 timbod 的评论:
考虑这段代码，注意 (toEnum 97)::Char 是 'a'

class TwoParam a b where
  combine :: a -> b -> (a,b)
  combine = (,)

instance TwoParam c c

t1 :: (TwoParam Char b) => Char -> b -> (Char,b)
t1 = combine

main = print (t1 'a' (toEnum 97))

这失败并显示以下消息:

No instance for (TwoParam Char b0) arising from a use of `t1'
Possible fix: add an instance declaration for (TwoParam Char b0)
In the first argument of `print', namely `(t1 'a' (toEnum 98))'
In the expression: print (t1 'a' (toEnum 98))
In an equation for `main': main = print (t1 'a' (toEnum 98))
Failed, modules loaded: none.

为什么？类型检查器推断 (toEnum 98) 具有某种 Enum 类型，这可能是 Char，但它不会推断它必须是 Char。类型检查器不会将 (toEnum 97) 与 Char 匹配，即使 (TwoParam Char b) 的唯一可用实例需要将 b 与 Char 匹配。编译器在这里是正确的，因为我以后可以编写另一个实例:

--  instance TwoParam Char Integer

对于第二个(重叠)实例，应该选择哪个实例不再明显。解决方案是使用上面的“技巧”:

-- instance (c ~ d) => TwoParam c d

类型检查器在选择实例时只查看“TwoParam c d”，这匹配所有内容。然后它试图满足约束

Char ~ typeOf (fromEnum 98)

这将成功。使用技巧'main'打印('a'，'a')