[Haskell-cafe] combinators in the syb lib -- or generic
heterogeneous traversals that fold
Carter Schonwald
carter.schonwald at gmail.com
Mon Aug 30 22:54:28 EDT 2010
Hello All,
In the course of some code I've been working on, I found I needed generic
foldl / foldr over heterogeneous data structures, where I can easily pick
whether I want top down left right, botom up left right, and ___ right
left traversals, and to in tandem sensibly approach if a parent node should
be included altogether
What i'm wondering is if i'm somehow overlooking some simpler ways of
writing such or if my attached code for the foldl case (the foldr analogue
is easy to see from the example code).
code with example follows
--- my "foldl" that is abstracted from traversal order
travL :: (b -> a -> b)->
GenericQ (Maybe a) ->
(Maybe a -> b ->(b -> a -> b)->(b->b)-> b) ->
GenericQ (b ->b)
travL f qry merge x nil = merge (qry x) nil f (\nl->
foldl (flip ($)) nl $ gmapQ
(travL f qry merge) x )
--travR could be written as
--- travR f qry merge x nil = foldl (flip f) nil $ travL (flip (:)) qry
merge x []
-- example usage
-- takes the integers in some datastructure, and puts them in a list
-- example:
flipList :: Data a => a -> [Integer]
flipList x = travL (flip (:) ) (mkQ Nothing (Just :: Integer -> Maybe
Integer) ) (\ v nl f k -> maybe (k nl) (\y -> k $! f nl y) v ) x []
I suppose that i could simplify it to
travL :: GenericQ (Maybe a) ->
(Maybe a -> b ->(b->b)-> b) ->
GenericQ (b ->b)
and have the operand *f* of the fold work within the *merge* parameter, but
that doesn't address the important bit in my mind,
namely that while its pretty clear to me that I can write the *synthesize*and
*everything* combinators using my "travL/R" stuff, its not clear to me that
the converse or something close to it is the case.
Anyways, what're everyone's thoughts?
thanks!
-Carter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100830/51cb8151/attachment.html
More information about the Haskell-Cafe
mailing list