如何定义多态无标签最终列表

Question

读完优秀有趣的论文后打字无标签最终解释:入门课程我试图将正常的Haskell列表转换为无标签的Final列表，但失败了:

正在运行:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module TList
where
class TList repr  where
tnil :: repr
tcons :: Int -> repr -> repr
tlist0 :: TList repr => repr
tlist0 = tnil
tlist1 :: TList repr => repr
tlist1 = tcons 1 $ tcons 2 $ tcons 3 tnil
instance TList String where
tnil = "tnil"
tcons hd tail = "tcons " ++ show hd ++ " $ " ++ tail
view :: String -> String
view = id

在GHCi中执行view tlist1得到tcons 1 $ tcons 2 $ tcons 3 $ tnil

通过上面的定义，列表元素的类型被限制为Int!我想有多态列表和尝试:

class PList repr a where
pnil :: repr a
pcons :: a -> repr a -> repr a
plist0 :: forall (repr :: * -> *) a. PList repr a => repr a
plist0 = pnil
plist1 :: PList repr Int => repr Int
plist1 = pcons 1 $ pcons 2 $ pcons 3 pnil

可以编译，但是我无法为解释器定义实例:

instance PList String where
pnil = "pnil"
pcons hd tail = "pcons " ++ show hd ++ " $ " ++ tail

这给出了错误:

[1 of 1] Compiling TList            ( List/List.hs, interpreted ) [Source file changed]
List/List.hs:30:10: error:
• Expecting one more argument to ‘PList String’
Expected a constraint,
but ‘PList String’ has kind ‘* -> Constraint’
• In the instance declaration for ‘PList String’
|
30 | instance PList String where
|          ^^^^^^^^^^^^
List/List.hs:30:16: error:
• Expected kind ‘* -> *’, but ‘String’ has kind ‘*’
• In the first argument of ‘PList’, namely ‘String’
In the instance declaration for ‘PList String’
|
30 | instance PList String where
|                ^^^^^^

所以PList应该有2个类型参数!更改为instance PList String Int where给出:

List/List.hs:30:16: error:
• Expected kind ‘* -> *’, but ‘String’ has kind ‘*’
• In the first argument of ‘PList’, namely ‘String’
In the instance declaration for ‘PList String Int’
|
30 | instance PList String Int where
|                ^^^^^^

我应该有一个类似于Functor的(* -> *)类型，但是我没有。如何修复?

Answer 1

这取决于您是否想要保留"被包含"的类型信息。元素。你当然可以保留它，通过虚参

newtype TypyString a = TypyString { stringyString :: String }

，它有一个适合当前类的类型。

但我认为更符合原著的精神是而不是携带这些信息。那么repr a出现在签名中就没有意义了。它不需要，你可以在那里有一个普通的repr。GHC可能会因为你有模棱两可的类型而拒绝你，但这不再是一个问题，有了正确的扩展名:

{-# LANGUAGE AllowAmbiguousTypes #-}
class PList repr a where
pnil :: repr
pcons :: a -> repr -> repr

然后可以定义

instance PList String Int where
pnil = "pnil"
pcons hd tail = "pcons " ++ show hd ++ " $ " ++ tail

…或者更一般地，

instance Show a => PList String a where
...

然而，这些示例需要注意歧义:

{-# LANGUAGE ScopedTypeVariables, TypeApplications, UnicodeSyntax #-}
plist0 :: ∀ repr a . PList repr a => repr
plist0 = pnil @repr @a
plist1 :: ∀ repr . PList repr Int => repr
plist1 = pcons @repr @Int 1
. pcons @repr @Int 2
. pcons @repr @Int 3
$ pnil @repr @Int

这是相当尴尬的，也是不必要的，因为repr参数实际上是不模糊的，而a参数是。交换类型参数会更好:

class PList a repr where
pnil :: repr
pcons :: a -> repr -> repr
instance PList Int String where
...
plist0 :: ∀ a . PList a => repr
plist0 = pnil @a
plist1 :: PList repr Int => repr
plist1 = pcons @Int 1 . pcons @Int 2 . pcons @Int 3 $ pnil @Int

如果数字文字是明确的，你甚至不需要@Int应用程序的pconses，它们在Haskell中没有，但可以这样做:

plist1 :: PList Int repr => repr
plist1 = pcons n1 . pcons n2 . pcons n3 $ pnil @Int
where n1,n2,n3 :: Int
(n1,n2,n3) = (1,2,3)