How to define polymorphic tagless final lists

Question

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?

Answer 1

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)