Yesterday I played with number-parameterized types in Haskell (actually, GHC).
The ultimate goal was to create a type for a process, that when forced, pops out an output and another process, which can be forced again, etc. The environment can later graft inputs at the places in the process that popped outputs (not necessarily in the order of outputs, but keeping correspondence between inputs and outputs). E.g., process can request an input from a file, then from a keyboard, then environment will provide it with input from a keyboard, and then from file. To complicate the issue even more, different choices of outputs have different options for inputs (so types of inputs are indexed by values of outputs).
I started from more modest types to make sure I understand what I am doing.
First I needed a couple of phantom types to build arithmetic on types:
data Z -- 0 inhabitants
data S a = L a -- as much inhabitants as in a
class Sum a b c a b -> c
instance Sum Z a a
instance Sum a (S b) c => Sum (S a) b c
Among other things, this enabled me to build sequences parameterized by their size:
data Seq a s = Seq [a]
deriving Show
nil :: Seq a Z
nil = Seq []
cons :: a -> Seq a m -> Seq a (S m)
cons h (Seq t) = Seq (h:t)
app :: Sum m n s => Seq a m -> Seq a n -> Seq a s
app (Seq m) (Seq n) = Seq (m ++ n)
Note that I use ordinary lists inside Seq, so I can reuse all their operations (e.g., ++).
Next step would be to convert ordinary lists to sequences.
For that, I choose to bundle sequences with their lenght representation in an existential package. First, I define a type for representation of naturals:
data NatRep s = NatRep Int
deriving Show
z :: NatRep Z
z = NatRep 0
s :: NatRep a -> NatRep (S a)
s (NatRep n) = NatRep $ n+1
I could have done the following:
data Nat = Zero | Succ Nat
deriving Show
data NatRep s = NatRep Nat
deriving Show
z :: NatRep Z
z = NatRep Zero
s :: NatRep a -> NatRep (S a)
s (NatRep n) = NatRep $ Succ n
, but decided to keep Peano arithmetic restricted to types.
Now I am equipped with tools to create dynamically typed sequences parameterized by their size (quite a mouthful):
data DynSeq a = forall m . DynSeq (NatRep m) (Seq a m)
instance Show a => Show (DynSeq a) where
show (DynSeq n sq) = "(DynSeq " ++ (show n) ++ " " ++ (show sq) ++ ")"
toDynSeq :: [a] -> DynSeq a
toDynSeq [] = DynSeq z nil
toDynSeq (a:as) = case toDynSeq as of DynSeq n sq -> DynSeq (s n) $ cons a sq
A couple of surprizes notwithstanding (inability to derive Show for DynSeq, or to use pattern with DynSeq in either let or where), it was quite easy (if not optimal, should I have used GADTs?). Also, I suspect that the decision to use lists inside Seq and Int inside DynSeq will bite me more than once. Also, I am not comfortable with the approach of using functions like nil and cons instead of constructors, this may hinder compiler to help me.
Will have to think about ways to reach the ultimate goal now...
See also
http://okmij.org.
PS: I am using the following options:
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances #-}
