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.

Coom

What you're trying to do here does make sense, but it's not well-supported by Haskell, and is usually a symptom of a non-idiomatic design. If you're curious about how to do it, @hammar gives you a starting point. If you encounter this situation in real code, you'll probably be better off rethinking your approach. – Expropriate

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.

Tameka

Note that the type you've defined is different from the type in the question: ∀ x. C x => [x] is distinct from [∀ x. C x => x]. – Expropriate

@camccann: Are you sure you're reading my code correctly? SomeWrapper is forall x. C x => x, and I use [SomeWrapper]. – Tameka

@hammar: Yes, and the question has it the other way. Compare the definitions of SomeGroup. – Expropriate

@camccann: Ah, right. Though, I'm not sure that is what the OP intended judging by the rest of his question. – Tameka

Thanks, @hammar, your approach works well (it's listed in article linked in question). So if I understand correctly compiler cannot statically dispatch some call because it doesn't know values of what types are exactly will be present in specific SomeGroup value? – Coom

@hammar: Agreed, your version is probably what was intended, which is why I chose to highlight the distinction. :) For some reason the placement of the quantifier seems to trip people up a lot. – Expropriate

@andreypopp: Yes, so there has to be some additional information present to resolve it at run time. In (GHC) Haskell this is the type class dictionary. It can be compared to the vtable pointer in object-oriented languages. – Tameka

I don't understand this comment: "there needs to be a data type wrapping the existential in order for there to be a place to store the type class dictionary". GHC, unlike C++ passes the type class dictionaries as separate arguments to functions, which was listed by SPJ as an improvement over OO-languages. The advantage was among other things that you do not need an create an actual object to call "virtual" functions, so for example you can have "C++ constructors" (functions that create an object) passed along in the type class dictionary. Could you explain or clarify your answer? – Weatherford

@user239558: Yes, normally the dictionaries are passed separately, but this changes when you have existential types. Let's say you have a data type data Foo = forall a. Num a => a, and a function f (Foo x) = Foo (x + fromInteger 1). How does f know which instance to use? It can't be determined statically, as the only place where we know the actual type is when we constructed the Foo value. The answer is that the type class dictionary has to be added as an extra hidden field of Foo, which is made available when we pattern match . – Tameka

@user239558: (Continued) However, once we have the dictionary, we can still use it to call functions like fromInteger where the dictionary is passed separately. – Tameka

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.

Spectrograph