Ryan Ingram | 16 Oct 10:01 2008
Picon

Re: Rewrite rules

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

Gmane