[Haskell-cafe] Re: Ideas of a polymorphic Tree in Haskell

Maciej Piechotka uzytkownik2 at gmail.com
Thu May 13 13:57:31 EDT 2010


On Thu, 2010-05-13 at 10:06 -0300, Edgar Z. Alvarenga wrote:
> Hi,
> 
> I created a small Genetic Algorithm program, replicating this 
> work ("Statistical mechanics of program systems" - JP Neirotti, N.
> Caticha, Journal of Physics A  Math and Gen) made in Lisp. When a
> restricted the problem just for one type, the Haskell program worked
> perfectly with much less lines and a lot faster than the Lisp program.
> The problem was when I tried to generalize to polymorphic types. 
> 
> I'm using this datatype to represent a program:
> 
> data Tree a = Bin (String, (a -> a -> a)) (Tree a) (Tree a)
>             | Un (String, (a -> a)) (Tree a)
>             | V
> 
> And can convert a Tree to a function with:
> 
> treeToFunc :: Tree a -> a -> a
> treeToFunc (Bin f l r) =  (snd f) <$> treeToFunc l <*> treeToFunc r
> treeToFunc (Un f u) = (snd f).(treeToFunc u)
> treeToFunc V = id
> 
> I already create another datatype to represent a polymorphic program
> (using GADT or existentials), but doesn't see a way to convert this kind
> of tree to a function. 
> 
> Anyone has any idea?
> 
> Thanks,
> Edgar

Hmm. What GDAT/existential do you use (for lazy people who do not want
to read paper)? How is it programmed in Lisp?

data Tree a where
    Bin :: String -> (c -> (a, b)) -> (a -> b -> c) -> Tree a -> Tree b
        -> Tree c
    Un :: String -> (a -> a) -> Tree a
    V :: Tree a

treeToFunc :: Tree a -> a -> a
treeToFunc (Bin _ f g l r) v = let ~(x, y) = f v
                               in g (treeToFunc l x) (treeToFunc r y)
treeToFunc (Un _ f)        v = f v
treeToFunc V               v = v

Or

data Tree a where
    Bin :: String -> Tree a -> Tree b -> Tree (a, b)
    Un :: String -> (a -> a) -> Tree a
    V :: Tree a

treeToFunc :: Tree a -> a -> a
treeToFunc (Bin _ l r) (a, b) = (treeToFunc l a, treeToFunc r b)
treeToFunc (Un _ f)    v      = f v
treeToFunc V           v      = v

Both compiles but I'm not sure if they are what you want.

Regards
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100513/80581090/attachment.bin


More information about the Haskell-Cafe mailing list