List of items of types restricted by typeclass

Question

I'm trying to encode a list of items which have types restricted to be instances of some type class:

{-# LANGUAGE RankNTypes, TypeSynonymInstances, LiberalTypeSynonyms #-}
module Test where

class Someable a where
  some :: a -> String

data Some = Some String

type SomeGroup = forall a. Someable a => [a]

instance Someable Some where
  some (Some v) = v

instance Someable SomeGroup where
  some (x:xs) = (some x) ++ ", " ++ (some xs)

main = do
  putStrLn $ show.some [Some "A", [Some "B", Some "C"]]

But compilation fails with error:

Test.hs:14:10:
    Illegal polymorphic or qualified type: SomeGroup
    In the instance declaration for `Someable SomeGroup'

It seems I even failed to define instance for type synonymous...

I'm aware of heterogenous collections wiki article, but want to know why exactly my approach doesn't work — it seems natural to me to define type by restricting collection only to contain items with types which is instance of some type class.

Answer 1

If I understand things correctly, there needs to be a data type wrapping the existential in order for there to be a place to store the type class dictionary along with each element.

Adding some wrappers makes it work:

{-# LANGUAGE ExistentialQuantification, TypeSynonymInstances #-}

module Test where

class Someable a where
  some :: a -> String

data Some = Some String

data SomeWrapper = forall a. Someable a => SomeWrapper a

type SomeGroup = [SomeWrapper]

instance Someable Some where
  some (Some v) = v

instance Someable SomeWrapper where
  some (SomeWrapper v) = some v

instance Someable SomeGroup where
  some (x:xs) = (some x) ++ ", " ++ (some xs)

main = do
  putStrLn $ some [SomeWrapper (Some "A"), SomeWrapper [SomeWrapper (Some "B"), SomeWrapper (Some "C")]]

Of course, this is a bit ugly. I'm not aware of any better way, unfortunately.

Answer 2

You can also cook something up using GADTs. That may be slightly shorter in some cases, and it makes explicit which type dictionaries are available after pattern matching.

Here's a slight variant of your example:

{-# LANGUAGE GADTs #-} 
class Someable a where
  some :: a -> String

instance Someable Int where
  some n = show n

data SomeString = SomeString String
instance Someable SomeString where
  some (SomeString s) = s

data SomeGroup where 
    Nil :: SomeGroup
    Cons :: Someable a => a -> SomeGroup -> SomeGroup

instance Someable SomeGroup where
    some Nil = ""
    some (Cons x Nil) = some x
    some (Cons x xs) = some x ++ ", " ++ some xs

list = Cons (3::Int) (Cons (SomeString "abc") (Cons (42::Int) Nil))
main = print . some $ list

A couple of minor notes:

• You forgot the base case for the recursion :)
• putStrLn . show is the same as print.
• You have to state the type of the numbers explicitly as Int because integer literals are treated specially, that is 42 is translated to fromInteger 42 of type Num a => a. A bit clunky when constructing the list directly, but most of the time it'll work more smoothly.
• You can of course define your own syntacting sugar for Cons-ing elements onto a list, but the syntax will never look as nice as Haskell's built-in syntax!

And a major point is that you lose the use of all the standard list functions. I usually use this kind of solution when my list processing needs are extremely limited; on the other hand, a fold is written quickly enough... Your mileage will vary though, I don't know what you actually want to use this list for.