Thu Jun 8 10:15:33 EDT 2006

```Christophe Poucet wrote:
> The idea however is that MonoType is going to be used in a recursive
> way. For instance:
>
> newtype FMT = FMT MonoType FMT
>
> instance FMT where...

Er, I'll ignore this part.
>
> And this definition will have to reside on recursive definitions. In the
> style of how HasVars was instantiated:
>
> instance HasVars a => HasVars (MonoType a) where
> freeVars (TyVar x) = [x]
> freeVars (TyConst _ xs) = nub . concatMap freeVars \$ xs
> occurs x (TyVar y) = x == y
> occurs x (TyConst _ xs) = or . map (occurs x) \$ xs
>
> So for Type
>
> instance Type a => Type (MonoType a) where
> ...
>
> That's where it becomes rather troublesome.

Yeah, after a certain point of complexity with type classes, it
starts to look like C++ templates.  How about something like...

{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
import List

type Var = String
type Const = String

data MonoType mt = TyVar Var
| TyConst Const [mt] deriving (Eq, Show)

data PolyType mt = TyPoly [Var] mt deriving (Show)

class Type a b where
toType   ::   b -> a b
fromType :: a b -> b
freeVars :: a b -> [Var]
occurs   :: Var -> a b -> Bool

data Nil = Nil

instance Type MonoType Nil where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = ["???"]

instance (Type a b) => Type MonoType (a b) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars \$ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) \$ xs

main = print \$ freeVars \$
TyConst "foo" [TyConst "bar"  [Nil],
TyConst "baz"  [Nil],
TyVar   "quux"      ]

```