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)