[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?
-------------- 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