[From nobody Thu Aug 3 07:47:13 2006
Message-ID: <44D1E30D.3050200@cs.nott.ac.uk>
Date: Thu, 03 Aug 2006 12:50:37 +0100
From: Conor McBride <ctm@cs.nott.ac.uk>
User-Agent: Thunderbird 1.5.0.5 (Macintosh/20060719)
MIME-Version: 1.0
To: Klaus Ostermann <ostermann@informatik.tu-darmstadt.de>
Subject: Re: [Haskell-cafe] Variants of a recursive data structure
References: <024e01c6b6ea$b5a0e1e0$63a55382@rachmaninoff>
In-Reply-To: <024e01c6b6ea$b5a0e1e0$63a55382@rachmaninoff>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Hi Klaus
Deep breath!
Klaus Ostermann wrote:
> Hi all,
>
> I have a problem which is probably not a problem at all for Haskell experts,
> but I am struggling with it nevertheless.
>
> I want to model the following situation. I have ASTs for a language in two
> variatns: A "simple" form and a "labelled" form, e.g.
>
> data SimpleExp = Num Int | Add SimpleExp SimpleExp
>
> data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String
>
> I wonder what would be the best way to model this situation without
> repeating the structure of the AST.
>
A trick we use all the time in the implementation of Epigram, for pretty
much the purpose you suggest, is to abstract over a type constructor
which packs recursive nodes. Thus
> type Node exp node = node (exp node)
> -- Node :: ((* -> *) -> *) -> (* -> *) -> *
> data Exp node = Num Int | Add (Node Exp node) (Node Exp node)
> -- Exp :: (* -> *) -> *
So now, with
> data Id x = An x
you get
> type SimpleExp = Node Exp Id
> type LabelledExp = Node Exp ((,) String)
Being incremental programmers, us Epigram folk also like syntax with holes
> type UnfinishedExp = Node Exp Maybe
Now we can make a node reshaping gadget like this
> renode :: ((Exp m -> Exp n) -> Node Exp m -> Node Exp n) ->
> Node Exp m -> Node Exp n
> renode transform me = transform inside me where
> inside (Num i) = Num i
> inside (Add me1 me2) = Add (renode transform me1) (renode
transform me2)
> unlabel :: LabelledExp -> SimpleExp
> unlabel = renode (\f (_,x) -> An (f x))
Of course, to see what's going on, you might want something like {-
needs -fglasgow-exts -}
> instance Show SimpleExp where
> show (An (Num i)) = "(Num " ++ show i ++ ")"
> show (An (Add x y)) = "(Add " ++ show x ++ " " ++ show y ++ ")"
So you get {- genuine output -}
*Nodes> unlabel ("fred", Add ("jim", Num 1) ("sheila", Num 2))
(Add (Num 1) (Num 2))
Of course, you can also play the same sort of game, making Node
explicitly a fixpoint operator and removingthe recursion from Exp, like
this:
newtype Node exp node = Node (node (exp (Node exp node)))
data Exp exp = Num Int | Add exp exp
but we don't, because it makes mutually defined syntactic categories get
way out of hand.
Third order programming. It's a whole other order.
Enjoy
Conor
]