如何使用受约束的元素创建异构列表(也称为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这样的东西,但要么是不可能的,(或希望)我只是缺乏必要的类型.

这是我的尝试:

{-# 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构造函数旨在使UI tk参数与构造的HList保持一致.

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

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

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)有一些枚举类型,这可能是Char,但它不会推断它必须是Char.类型检查器将不匹配(toEnum 97)到Char,即使(TwoParam Char b)的唯一可用实例需要与Char匹配b.编译器在这里是正确的,因为我以后可以写另一个实例:

--  instance TwoParam Char Integer

在第二个(重叠)实例中,不再明显应该选择哪个实例.解决方案是使用上面的'技巧':

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

类型检查器在选择实例时只查看'TwoParam cd',这匹配所有内容.然后它试图满足约束

Char~typeOf(fromEnum 98)

哪个会成功的.使用"主要"打印技巧('a','a')