Feature request: More transformations

[lspitzner]

e.g. a top-down version of transform, plus a "Maybe" variant.

All the above are transformations, so transform is rather vague. Maybe just suffix:

-- aka `transform`
transformUp  :: Uniplate on => (on -> on) -> (on -> on)
transformUp f = g where g = f . descend g
transformDown :: Uniplate on => (on -> on) -> (on -> on)
transformDown f = g where g = descend g . f
transformDownMay  :: Uniplate on => (on -> Maybe on) -> (on -> on)
transformDownMay f = g where g x = maybe x (descend g) $ f x

(And while we are refactoring, descend sounds like it does something recursively. Which got me confused for longer than i want to admit.)

[ndmitchell]

The Uniplate paper (http://ndmitchell.com/downloads/paper-uniform_boilerplate_and_list_processing-30_sep_2007.pdf) covers why transformDown is often a bad idea - see section 2.4. The idea for no suffix was that if you give people a choice, and one is almost always wrong, you push people towards the wrong behaviour unnecessarily.

As with all things, the choice of names is mostly historic, and I only really understood the operators relationships sometime after I renamed them. If doing it again I may well call it transform1 instead of descend.

[lspitzner]

I see. One could also provide

transformDownRec  :: Uniplate.Uniplate on => (on -> Maybe on) -> (on -> on)
transformDownRec f = g where g x = maybe (Uniplate.descend g x) g $ f x

which removes the first issue.

In my use-case, i need to float-down a number of single-child constructors. Because there are a lot of those and i aim for performance, i have now implemented this as a bottom-up transformation that, whenever encountering any relevant node, performs a transformDownMay. A full rewrite gives me a much worse performance, at least according to some profiling. (I don't completely trust the profiler - it always seems to report the most work to be done by the first rewrite that i do in the series of transformations on my tree..)

So one might argue in the other direction: You will immediately notice by running some tests if you introduced a non-terminating transformation/rewrite. But bad (asymptotic) performance is silent. Giving users multiple options will at least implicitly point out that performance may vary, and make them think.

I'd vote for giving users full power, and making recommendations in the documentation.

[lspitzner]

relevant code

[flip111]

@lspitzner relevant code gives 404 you can fix this by pointing to a specific commit. I looked up the last version of 30 july and it's this one https://github.com/lspitzner/brittany/blob/beaf121b6660245d7f153a3208dcad1bcfae02e6/src/Language/Haskell/Brittany/BriLayouter.hs#L802-L809