16 Oct 10:01 2008

## Re: Rewrite rules

Ryan Ingram <ryani.spam <at> gmail.com>

2008-10-16 08:01:28 GMT

2008-10-16 08:01:28 GMT

Isn't this an unsound rewrite? > cycle [(0 :: Integer)..] !! 100 => 100 > [(0 :: Integer) ..] !! (100 `mod` length [(0::Integer)..]) => _|_ Anyways, the reason for inlining not being done if an expression is used more than once is that it duplicates work that you explicitly specified should only be done once (by placing it in a let). If you want these declarations to get inlined so rules can fire, you should be able to do something like this: > let rlist = cycle list > {-# INLINE rlist #-} > print ... -- ryan 2008/10/16 George Pollard <porges <at> porg.es>: > Section 8.13.2 of the GHC manual[1] states: > >> GHC keeps trying to apply the rules as it optimises the program. For >> example, consider: >> >> let s = map f >> t = map g >> in >> s (t xs) >> >> The expression s (t xs) does not match the rule "map/map", but GHC >> will substitute for s and t, giving an expression which does match. If >> s or t was (a) used more than once, and (b) large or a redex, then it >> would not be substituted, and the rule would not fire. >> > The part I'm interested in here is (a); if an expression is used more > than one then it cannot be substituted for. Is there any way to work > around this or force it? > > The reason I ask is that as a bit of fun (and inspired by Joachim > Breitner's blog post [2]) I was going to try writing a rewrite rule for > the first time. What I had in mind was this: > > {-# RULES > "index cycled list" forall list n. cycle list !! n = > list !! (n `mod` length list) > #-} > > However, in the case he has written about this won't fire, since the LHS > cannot be substituted as `cycle list` is used more than once: > >> let rlist = cycle list >> print ( rlist !! (10^9), rlist !! 0 ) > > I can get it to fire again if I write it like this: > >> {-# RULES >> "!!/cycle" forall list. (!!) (cycle list) = (\n -> list !! (n `mod` length list)) >> #-} >> >> ... >> >> let rlist = (!!) (cycle list) >> print (rlist (10^9), rlist 0) > > But this is non-obvious and I'd rather have it fire in the first case > (i.e. when used naïvely). So, back to my question; is there a workaround > or force for this... or does it break too many things if done? > > [1] > http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#id414792 > > [2] > http://www.joachim-breitner.de/blog/archives/308-guid.html > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe <at> haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >