Question about sets

[Andrew J Bromage]

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