The Issue
Your ShowList
type is called an "existential" type, roughly meaning that given a value of type ShowList
there exists some type a
for its contituents (the list elements, in your case).
The point is that nothing is known about this type a
, except for the fact that it belongs to the type class Show
.
Hence, a function such as head
can not be easily typed
head :: ShowList -> ???
head (x ::: _) = x
Using a non-Haskell syntax, the type would be
head :: ShowList -> (exists a. Show a => a)
head (x ::: _) = x
but this is not allowed in Haskell.
A Possible Solution
The main idea is this: Haskell does not let you return the head since that would be untypeable, but Haskell does let you take the head and use it to build something else (which has to have a valid type). For instance
foo :: ShowList -> String
foo Nil = "Nil"
foo (x ::: _) = show x
is alright: we take the head and we use it to build a value of type String
. We can also put x
back into another existential type
data Showable :: * where
S :: Show a => a -> Showable
foo :: ShowList -> Showable
foo [] = error "unexpected Nil"
foo (x ::: _) = S x
We can also ask the user of foo
to specify which function should be applied to x
.
{-# LANGUAGE RankNTypes #-}
foo :: ShowList -> (forall a. Show a => a -> r) -> r
foo [] _ = error ""unexpected Nil"
foo (x ::: _) f = f x
test :: Int
test = foo (123 ::: ("aa" ::: Nil)) f
where f :: Show a => a -> Int
f = length . show
The type of the f
argument here is sophisticated. It specifies that f
must work on any a
of class Show
. I.e., that the type a
is chosen by function foo
, not by f
: so, f
is required to be polymorphic in a
.
A Final Note
The ShowList
type is nearly equal to [Showable]
. Using [Showable]
allows to use standard list functions such as head
without any issue. The downside is that it requires to box/unbox the data adding/removing constructor S
.