[Haskell-cafe] Rewrite rules

George Pollard porges at porg.es
Wed Oct 15 19:48:11 EDT 2008

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:

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20081016/a34fa0e6/attachment.bin

More information about the Haskell-Cafe mailing list