Andrew J Bromage ajb@spamcop.net
Wed, 21 Aug 2002 13:19:13 +1000

```G'day all.

On Tue, Aug 20, 2002 at 10:57:36AM -0700, Hal Daume III wrote:

> Lists with arbitrary
> elements are possible, but not very useful.  After all, what could you do
> with them?

It's often useful to have containers of arbitrary _constrained_ types,
because then you can do something with them.  For example, given the
class of partial mappings on orderable keys:

class (Ord k) => Map m k v | m -> k v where
lookupM :: m -> k -> Maybe v

instance (Ord k) => Map (FiniteMap k v) k v where
lookupM = lookupFM

instance (Ord k) => Map [(k,v)] k v where
lookupM m k = case [ v | (k',v) <- m, k == k' ] of
[]    -> Nothing
(v:_) -> Just v

instance (Ord k) => Map (k -> Maybe v) k v where
lookupM       = id

You can make a list of elements, which can be any type so long as
they are a member of that class:

data MAP k v = forall m. (Map m k v) => MAP m

type ListOfMap k v = [MAP k v]

Then you can do things with it:

lookupLom :: (Ord k) => ListOfMap k v -> k -> [ Maybe v ]
lookupLom xs k = [ lookupM a k | MAP a <- xs ]

test :: [Maybe Int]
test
= lookupLom maps 1
where
maps = [ MAP finiteMap, MAP assocListMap, MAP functionMap ]
finiteMap = listToFM [(1,2)]
assocListMap = [(1,3)]
functionMap = \k -> if k == 1 then Just 4 else Nothing

It's a little unfortunate that you have to introduce the MAP type here.
You can in fact construct a list of this type:

type ListOfMap k v = [ forall m. (Map m k v) => m ]

But then you can't use the elements in the list because the Haskell
type checker can't find the (Map m k v) constraint.

Cheers,
Andrew Bromage

```