[Haskell-cafe] Maybe use advice

[John Lato]

If I'm interpreting your code properly, it's not currently catching that
case anyway.

The problem is that you've got two sets of modifiers that both should be
optimized, explicit Modifier constructors in the Image, and a list contained
in Changes.  Since 'Changes' is just a list of Modifiers, and not an Image,
neither rewrite nor transform will descend on it.  You get around this by
explicitly calling rewrite on the modifiers in 'deBlank', but then the rules
from 'optimize' aren't applied.  You can't really use the biplate functions
either because they only match on a single element at a time.  What you
really want to do is be able to express each rule exactly once, which isn't
possible in the current form of your code.

One solution is to move a lot of the reductions of the form 'Modifier x'
from 'optimize' into 'deBlank'.  Then you would have something like this:

> deBlank :: [Modifier] -> [Modifier]
> deBlank = db
>
> db (Scale 1 1 : l)   = db l
> db (Rotate x : Rotate x' : l) = db (Rotate (x+x') : l)
> db (Scale  x y : Scale x' y' : l) = db (Scale (x*x') (y*y') : l)
> db (Translate x y : Translate x' y' : l) = db (Translate (x+x') (y+y') :
l)
> db xs = xs

I actually don't think uniplate gets you anything in this particular
function.

Now deBlank will produce a list of modifiers which is as reduced as possible
(at least by the rules you've provided), and you can use it within a
two-pass optimize:

> optimize = transform o2 . transform o
>
> o (Modifier _ Blank) = Blank
> o (Modifier (Scale 0 _) _i) = Blank
> -- similar cases omitted
>
> o (Modifier m2 (Modifier m1 i)) = Modifier (m1 `mappend` m2) i
> o i@(Modifier (Changes _c) _i) = i
> o (Modifier m i) = Modifier (Changes [m]) i
> o i = i
>
> o2 (Modifier (Changes c) i) = case deBlank c of
>      [] -> i
>      [x] -> Modifier x i
>      xs -> Modifier (Changes c) i
> o2 i = i

Transformations like "Scale 0 _" have remained in the Image traversal,
however all other modifications are combined into a single Changes list,
which is then reduced by deBlank in the second pass.  Note that in the first
pass, even single modifications are encapsulated in a Changes; this makes
the logic of the second pass much simpler because then all the reductions of
multiple modifiers are located in the 'deBlank' function instead of split
between there and 'o'.

This presumes there's an appropriate Monoid instance for Modifiers, but if
it doesn't exist it can be written easily enough.

On second thought, I think it would be good to break it up even more, and
keep the reductions of the form

> o (Modifier _ Blank) = Blank
> o (Modifier (Scale 0 _) _i) = Blank

as a third pass, because it's possible some of them could get lost in this
form.  Then  the first pass would just combine terms, the second would apply
'deBlank' and reduce, then the third would be as above.

There are two alternatives which may be simpler:

1)  Expand "Changes c" into explicit modifications and do all your
reductions on the resulting Image.

2)   Implement a general matrix transform for Diagrams and rewrite
everything in terms of that.  This would be useful for shear transforms
anyway, which I believe are currently inexpressible in Diagrams.

John Lato

On Tue, Jun 7, 2011 at 10:12 AM, Lyndon Maydwell <maydwell at gmail.com> wrote:
>
> The fixpoint nature of rewrite catches some cases that transform might
> not if I'm interpreting it correctly.
>
> (Changes [Translate 1 1, Scale 1 1, Translate 1 1]) could be rewritten
> as (Translate 2 2), but I'm not sure that it could be translated as
> such if it matches against (Changes [Translate _ _, Translate _ _])
> first.
>
> I have the code on github at
>
https://github.com/sordina/Diagrams-AST/blob/master/src/Graphics/Rendering/Diagrams/AST/Optimize.hs
> if you're interested.
>
> At the moment I'm not worrying about speed as I really just wrote this
> optimisation function as a demo of why an AST interface to Diagrams
> might be useful.
>
> On Tue, Jun 7, 2011 at 5:06 PM, John Lato <jwlato at gmail.com> wrote:
> > Is it necessary (helpful) to use 'rewrite'?  Nearly every time I've
tried
> > it, in the end 'transform' has been a better choice.  Then you wouldn't
need
> > the 'Just's at all, and it should work fine.
> > John
> >
> >>
> >> From: Lyndon Maydwell <maydwell at gmail.com>
> >>
> >> (missed including cafe)
> >>
> >> f :: [Modification] -> Maybe [Modification]
> >> and
> >> f _ = Just $ f ...
> >> are incompatible
> >>
> >> I managed to get the behaviour I'm after with the use of Either, but
> >> this really is messy:
> >>
> >>
> >> -- Sets of changes
> >> o (Modifier (Changes [])  i) = Just $ i
> >> o (Modifier (Changes [c]) i) = Just $ Modifier c i
> >> o (Modifier (Changes l)   i) = g (f (Left l))
> >>  where
> >>    g (Right l) = Just $ Modifier (Changes l) i
> >>    g (Left  l) = Nothing
> >>
> >>    f (Left  (Scale     x y : Scale     x' y' : l)) =
> >>        f $ Right $ Scale     (x*x') (y*y') : h (f $ Left l)
> >>    f (Left  (Translate x y : Translate x' y' : l)) =
> >>        f $ Right $ Translate (x+x') (y+y') : h (f $ Left l)
> >>    f (Left  (Rotate    x   : Rotate    x'    : l)) =
> >>        f $ Right $ Rotate    (x+x')        : h (f $ Left l)
> >>    f x = x
> >>
> >>    h (Left  l) = l
> >>    h (Right l) = l
> >>
> >>
> >> On Tue, Jun 7, 2011 at 3:11 AM, Maciej Marcin Piechotka
> >> <uzytkownik2 at gmail.com> wrote:
> >> > On Mon, 2011-06-06 at 23:38 +0800, Lyndon Maydwell wrote:
> >> >> I'm writing an optimisation routine using Uniplate. Unfortunately, a
> >> >> sub-function I'm writing is getting caught in an infinite loop
because
> >> >> it doesn't return Nothing when there are no optimisations left.
> >> >>
> >> >> I'd like a way to move the last Just into f, but this makes
recursion
> >> >> very messy. I was wondering if there was a nice way to use something
> >> >> like the Monad or Applicative instance to help here.
> >> >>
> >> >> -- Sets of changes
> >> >> o (Modifier (Changes []) ?i) = Just $ i
> >> >> o (Modifier (Changes [c]) i) = Just $ Modifier c i
> >> >> o (Modifier (Changes l) ? i) = Just $ Modifier (Changes (f l)) i
> >> >> ? where
> >> >> ? ? f (Scale ? ? x y : Scale ? ? x' y' : l) = f $ Scale ? ? (x*x')
> >> >> (y*y') : f l
> >> >> ? ? f (Translate x y : Translate x' y' : l) = f $ Translate (x+x')
> >> >> (y+y') : f l
> >> >> ? ? f (Rotate ? ?x ? : Rotate ? ?x' ? ?: l) = f $ Rotate ? ?(x+x') ?
?
> >> >> ? ?: f l
> >> >> ? ? f l = l
> >> >>
> >> >>
> >> >> Any ideas?
> >> >
> >> > Something like:
> >> >
> >> > ...
> >> > f (Rotate ? ?x ? : Rotate ? ?x' ? ?: l)
> >> > ? ?= Just $ f (Rotate (x+x') : fromMaybe l (f l))
> >> > f l = Nothing -- As far as I understend
> >> >
> >> > Regards
> >> >
> >> > _______________________________________________
> >
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110607/b7fba799/attachment.htm>