Proposal: Add strict iterate' (and a discussion of possible new RULES)

[David Feuer]

I'm pushing hard to get unfoldr fixed ASAP, and looking to take
advantage of that. Specifically, I like the idea of using the fusion
that (I dearly hope) will come with unfoldr to make a variety of other
things fuse that currently need their own special rules. I also want
to extend fusion by one or two general rules. One that looks very good
is similar to the rejected foldr/cons rule, but seems somewhat less
likely to cause problems while still enhancing fusion in general:

{-# RULES
"cons/build"  forall x (g::forall b . (a->b->b)->b->b) . x : build g =
build (\c n -> x `c` g c n)
 #-}

This will allow foldr/build fusion to look past conses. So for example,

foldr f q (x : build g)

will be rewritten (cons/build) to

foldr f q (build (\c n -> x `c` g c n))

and then (fold/build) to

(\c n -> x `c` g c n) f q

This reduces to

f x (g f q)


A discussion about  foldr k z (x1:x2:x3:...:x2000:build g), a possible
way to fix it, and why I don't think it's important anyway.

This means the same thing as

foldr k z ([x1,x2,x3,...,x2000] ++ build g)

The current ++ rule rewrites this to

foldr k z (augment (\c n -> foldr c n [x1,...,x2000]) (build g))

Then foldr/augment:

(\c n -> foldr c n [x1,..,x2000]) k (foldr k z (build g))

Then foldr/build:

(\c n -> foldr c n [x1,...,x2000]) k (g k z)

Then beta reduction:

foldr k (g k z) [x1,...,x2000]

So to take the example from earlier,


foldr f q (x : build g)

is currently bad, but

foldr f q ([x] ++ build g)

will end up

foldr f (g f q) [x]

and then in this case the foldr/single rule will give

f x (g f q)

but if more than one element were in the list, we'd end up with a fold
over the literal list (not bad in general).

This suggests a fix, but one that may be difficult to implement within
GHCs stage framework as is (I'm not quite sure; someone who knows more
about the system may see a way to do this, but I think it wants to
happen before the ++ rule, which I think happens at the beginning of
time):

Translate   x1:x2:x3:...:build g   to   [x1,x2,x3,...] ++ build g

Then let everything else happen as usual.

I think, however, that this is probably overkill. Just implement
cons/build and tell users that if they want x1:x2:x3:....:x2000:foo
not to expand under foldr then they need to write
[x1,x2,x3,...,x2000]++foo  instead.