Ideas of a polymorphic Tree in Haskell
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
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
On Thu, 13/May/2010 at 18:57 +0100, Maciej Piechotka wrote:
Hmm. What GDAT/existential do you use (for lazy people who do not want to read paper)?
The GADT that I refered was from my faileds attempts.
How is it programmed in Lisp?
The paper don't give much details, but by what I undertood, if a random generated program don't compile it's discarted.
[...]
Both compiles but I'm not sure if they are what you want.
What I want is to can create trees like: U (a -> b) (U (c -> a) V) Or: B (a -> b -> c) (U (c -> a) V) (U (c -> b) V) And convert this to a function c -> b. I think I have achieved this now, but really don't understand exactly how it works. Look at this: data Tree a b c where B :: (a -> d -> b) -> Tree e a c -> Tree g d c -> Tree a b c U :: (a -> b) -> Tree d a c -> Tree a b c V :: (c -> d) -> Tree c d c treeToFunc :: Tree a b c -> c -> b treeToFunc (B f l r) = f <$> (treeToFunc l) <*> (treeToFunc r) treeToFunc (U f u) = f.(treeToFunc u) treeToFunc (V f) = f The only problem is that I need to create (V id) in the last leaf everytime: *Main> let r = B (\x y -> (fromInteger x) + y) (U floor (V id)) (U (**2) (V id)) *Main> (treeToFunc r) 3 12.0 Do you see any way to simplify this solution? Thanks, Edgar
Regards
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Thu, May 13, 2010 at 3:01 PM, Edgar Z. Alvarenga
On Thu, 13/May/2010 at 18:57 +0100, Maciej Piechotka wrote:
Hmm. What GDAT/existential do you use (for lazy people who do not want to read paper)?
The GADT that I refered was from my faileds attempts.
How is it programmed in Lisp?
The paper don't give much details, but by what I undertood, if a random generated program don't compile it's discarted.
The impression I had from your first email is that your GADT approach worked but you didn't want to use it here. Have you seen the research on higher-order abstract syntax (HOAS)? What you're doing looks fairly similar to my naive eyes. I didn't speak up because I thought you had already been down that road. I was just trying to find a paper on the subject (I think there was an ICFP paper that explained them in GADTs), and I found this: http://www.haskell.org/pipermail/haskell/2007-January/019012.html I think this is the paper I had in mind: http://adam.chlipala.net/papers/PhoasICFP08/ I hope you find those resources helpful! Jason
participants (3)
-
Edgar Z. Alvarenga -
Jason Dagit -
Maciej Piechotka