Embedding first class modules in Haskell

Modules.lhs

>{-# LANGUAGE TypeFamilies, ScopedTypeVariables #-}
>module Modules where

Since all modules under this translation must ascribe to some signature,
we by providing a signature for a module which provides equality over
some type.

>class EQ mod where
>  type EQV mod :: *
>  eq :: mod -> EQV mod -> EQV mod -> Bool

Now, we write a module matching this signature. First, we give it a name

>data IntEq

Now, we add the corresponding implementations.

>instance EQ IntEq where
>  type EQV IntEq = Int
>  eq _ n n' = n == n'

Now, we write the result signature for a simple first order functor, SET

>class SET mod where
>  data Set mod :: *
>  type Val mod :: *
>  insert       :: mod -> Val mod -> Set mod -> Set mod
>  mem          :: mod -> Val mod -> Set mod -> Bool

We implement the functor. 

>data SetF a
>instance (EQ a) => SET (SetF a) where
>  data Set (SetF a) = SI [Val (SetF a)]
>  type Val (SetF a) = EQV a
>  insert m v s@(SI ls) = if mem m v s then s else SI (v : ls)
>  mem m v (SI (l : ls)) | eq (undefined :: a) v l = True
>                        | otherwise = (mem m v (SI ls))
>  mem _ _ _ = False

Note that it does not require flexible instances or multiparameter type
classes, and that a single type is assigned to the result of applying a
functor. This is important as it means we can have a way to refer to the
module resulting from functor application by a single name, e.g.

>type IntSet = SetF IntEq

I think this system can actually support arbitrarily recursive modules,
but I haven't written out how to do arbitrary depth recursion with this
model. More to come when I get a good example.

This above is with some inspiration from "ML Modules and Typeclasses",
located at http://tinyurl.com/6m4vjw8