如何定义多态的标签终结列表

huangapple go评论64阅读模式
英文:

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 pconses 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)

huangapple
  • 本文由 发表于 2023年4月7日 04:21:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/75953461.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定