This is one of the problem Syntactic aims to solve, but it requires you
to use a different representation of expressions (for good or bad). If
you want to keep your existing representation, then you have to use a
generic programming library that supports GADTs. I know at least the
Spine approach supports GADTs, but the library on Hackage seems too
incomplete to be useful:
http://hackage.haskell.org/package/spine
I don't know if there are other libraries that support GADTs.
You can also have a look at CompData:
http://hackage.haskell.org/package/compdata
It is similar to Syntactic (i.e. requires a different representation),
but it has a richer library of generic traversals.
/ Emil
2012-11-21 04:20, Alexander Solla skrev:
Have you read "Data types a la carte"? The 'syntactic' package
implements the ideas, but it was a little dense for my purposes when I
looked (I just wanted data types, a la carte; it focuses on manipulating
ASTs defined a la carte). It might be what you need, or you can roll
your own based on the paper.
On Tue, Nov 20, 2012 at 3:21 PM, Steve Severance
<ssevera...@alphaheavy.com <mailto:ssevera...@alphaheavy.com>> wrote:
Hi Everyone,
I am trying to build a function to rewrite and AST. I have and AST
which is designed to represent a computation graph. I will present a
simplified version here designed to illustrate the problem. I have
tried numerous ways of rewriting it including uniplate, recursion
and Edward Kmett's implementation of plate in his lens package.
My AST is defined using GADTs as follows:
class (ReflectDescriptor a, Typeable a, Wire a) => ProtoBuf a
data Expression a b where
OpenTable :: (ProtoBuf b) => Int -> Table -> Expression () b
OpenFile :: (ProtoBuf b) => Int -> String -> Expression () b
WriteFile :: (Typeable a, ProtoBuf b) => Int -> String ->
Expression a b -> Expression b ()
WriteTable :: (Typeable a, ProtoBuf b) => Int -> Table ->
Expression a b -> Expression b ()
Map :: (ProtoBuf a, ProtoBuf b, ProtoBuf c) => Int -> (a -> b) ->
Expression c a -> Expression a b
LocalMerge :: (ProtoBuf a) => Int -> [Expression c a] ->
Expression c a
The user can create code inside a Monad Transformer like so:
q <- query $ do
table <- openTable myTable
transform <- map someFunc table
writeTable otherTable transform
As part of this language the compiler I am building would need to
for instance transform OpenTable into a series OpenFile nodes with a
LocalMerge to merge the results together.
So uniplate cannot work over GADTs if I recall correctly.
I exchanged emails with Edward and he explained that for the lens
case I would need something like an indexed lens family from his
indexed package which is not implemented yet but which may be in the
future.
The issue with recursion is that as you recurse through the AST the
a b on the Expression change and GHC cannot compile it because it
wants the a b to be the same on each recursive call.
My question to the Haskell community is how might one develop AST
rewriting functionality. One possible solution is stripping the
types away from GHC and doing all the type checking myself. That
doesn't seem very good.
Another possibility that I have looked at was using hoopl. It seems
very compatible given that it is built for describing and optimizing
data flow which I am doing however the learning curve looks quite
steep. I have been reluctant so far to invest the time in it.
Has anyone developed something similar? What recommendations do you
have?
Thanks.
Steve
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org <mailto:Haskell-Cafe@haskell.org>
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe