英文:
How to define polymorphic tagless final lists
问题
以下是代码部分的翻译:
这段代码中,作者试图将普通的 Haskell 列表转换为 Tagless Final 列表,但在定义多态列表时遇到了问题。作者首先定义了一个类型类 TList
,它表示 Tagless Final 列表,然后定义了一些实例和函数来操作这些列表。然后作者尝试定义多态列表,但遇到了问题,因为 PList
需要两个类型参数,但在尝试定义实例时出现了错误。
作者的问题是如何修复这个错误。
英文:
After reading the excellent and interesting paper
Typed Tagless-Final Interpretations: Introductory Course
from Oleg Kiselyov I tried to convert normal Haskell lists to Tagless Final lists and failed:
This is working:
{-# 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
Executing view tlist1
in GHCi gives tcons 1 $ tcons 2 $ tcons 3 $ tnil
With the definition above the type of the elements of the list is restricted to Int
! I would like to have polymorphic lists and tried:
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
This compiles, but I'm unable to define the instance for the interpreter:
instance PList String where
pnil = "pnil"
pcons hd tail = "pcons " ++ show hd ++ " $ " ++ tail
This gives the error:
[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
| ^^^^^^
So PList
should have 2 type arguments! Changing to instance PList String Int where
gives:
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
| ^^^^^^
So I should have a type with kind (* -> *)
like Functor or so, but I don't have it. How to fix?
答案1
得分: 2
这是您要翻译的内容:
取决于您是否希望保留表示中“包含”的元素的类型信息。您当然可以通过一个虚拟参数来保留它
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` 应用于 `pcons`,虽然在 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)
希望这能帮助您理解代码的内容。
英文:
It depends on whether or not you want to retain the type information of the "contained" element in the representation. You could certainly keep it, through a phantom argument
newtype TypyString a = TypyString { stringyString :: String }
which has a suitable kind for the current class.
But I think it's more in the spirit of the original to not carry that information around. Then it doesn't make sense for repr a
to appear in the signatures. It doesn't need to, you can just have a plain repr
there. GHC may balk at you for having ambiguous types, but that's not a problem any longer with the right extension:
{-# LANGUAGE AllowAmbiguousTypes #-}
class PList repr a where
pnil :: repr
pcons :: a -> repr -> repr
and then you can define
instance PList String Int where
pnil = "pnil"
pcons hd tail = "pcons " ++ show hd ++ " $ " ++ tail
...or more generally,
instance Show a => PList String a where
...
The examples will however need to take care of the ambiguity:
{-# 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
This is quite awkward, and also unnecessary because the repr
argument isn't actually ambiguous, rather the a
one is. It's nicer when the type arguments are swapped:
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
You wouldn't even need the @Int
applications for the pcons
es if the number-literals where unambiguous, which they aren't in Haskell but could be made to be:
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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论