How to define polymorphic tagless final lists

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?

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)