On the fly generation of representations of function calls

Quote:

>I am a fair novice with respect to the real world of functional programming

>and I have a question. I don't know whether it is quite FAQ-ish, but here

>it goes.

>[] data ConsList a = Nilc | Cons (a) (ConsList a)

>[] data SnocList a = Nils | Snoc (SnocList a) (a)

>[]

>[] singlec x = Cons (x) (Nilc)

>[] singles x = Snoc (Nils) (x)

>[]

>[] delta (Nilc) x = singlec x

>[] delta (Cons a b) x = Cons (a) (delta b x)

>[]

>[] gamma (Nils) = Nilc

>[] gamma (Snoc l x) = delta (gamma l) x

> ["gamma (Snoc (Snoc (Nils) 6) 5)",

> "delta(gamma (Snoc (Nils) 6)) 5",

> "delta(delta(gamma Nils) 6) 5",

> "delta(delta(Nilc) 6) 5",

> "delta(Cons 6 (Nilc)) 5",

> "Cons (6) (delta Nilc 5)",

> "Cons (6) (Cons (5) (Nilc))"]

This is easy if you've studied functional languages for a while - you just

need to simulate the language's reduction mechanism. I do this with a function

called contract which searches for a redex and contracts it. The main program

(called "doit") applies this to the initial expression repeatedly and prints

the result out. This was written in Gofer:

data DG = Delta DG DG | Gamma DG | Nilc | Nils | Integer Int | Cons DG DG |

Snoc DG DG

instance Eq DG where

(Delta a b) == (Delta c d) = (a == c) && (b == d)

(Gamma a) == (Gamma b) = (a == b)

Nilc == Nilc = True

Nils == Nils = True

(Integer i) == (Integer j) = (i == j)

(Cons a b) == (Cons c d) = (a == c) && (b == d)

(Snoc a b) == (Snoc c d) = (a == c) && (b == d)

x == y = False

instance Text DG where

showsPrec p (Delta a b) s = s++"(delta "++show a++" "++show b++")"

showsPrec p (Gamma a) s = s++"(gamma "++show a++")"

showsPrec p Nilc s = s++"Nilc"

showsPrec p Nils s = s++"Nils"

showsPrec p (Integer i) s = s++(show i)

showsPrec p (Cons a b) s = s++"(Cons "++show a++" "++show b++")"

showsPrec p (Snoc a b) s = s++"(Snoc "++show a++" "++show b++")"

contract :: DG -> DG

contract (Delta Nilc x) = Cons x Nilc

contract (Delta (Cons a b) x) = Cons a (Delta b x)

contract (Delta x y) = Delta (contract x) y

contract (Gamma Nils) = Nilc

contract (Gamma (Snoc l x)) = Delta (Gamma l) x

contract (Gamma x) = Gamma (contract x)

contract (Cons (Integer i) y) = Cons (Integer i) (contract y)

contract (Cons x y) = Cons (contract x) y

contract Nilc = Nilc

contract Nils = Nils

expr :: DG

expr = Gamma (Snoc (Snoc Nils (Integer 6)) (Integer 5))

doit = (layy.(map show).tofix) (iterate contract expr)

tofix :: Eq a => [a] -> [a]

tofix [] = []

tofix [a] = [a]

tofix (a:b:cs) | a == b = [a]

| otherwise = a:(tofix (b:cs))

layy :: [String] -> String

layy [] = ""

layy (x:xs) = x ++ "\n" ++ (lay xs)

Comments on my programming style are welcome.

Output is:

Gofer session for:

standard.prelude

dg

? doit

(gamma (Snoc (Snoc Nils 6) 5))

(delta (gamma (Snoc Nils 6)) 5)

(delta (delta (gamma Nils) 6) 5)

(delta (delta Nilc 6) 5)

(delta (Cons 6 Nilc) 5)

(Cons 6 (delta Nilc 5))

(Cons 6 (Cons 5 Nilc))

(856 reductions, 2391 cells)

John