Created
April 5, 2012 18:03
-
-
Save maurer/2312891 to your computer and use it in GitHub Desktop.
Embedding first class modules in Haskell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
>{-# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment