foldr

[Tomasz Zielonka]

On Fri, Jan 02, 2004 at 02:54:11AM +0000, James Ealing wrote:
> Hi all,
>
> If I have a function:
>
> it f [a0, a1, a2, ...] = [a0, f a1, f (f a2), ...]
>
> Is there any way of expressing
>
> it f
>
> as an instance of foldr?

You can write it as

    it1 f l = foldr (\x xs -> x : map f xs) [] l

but it's quite ineffective (the list is rewritten many times). One more
effective (and quite tricky) version is

    it2 f l = foldr (\x g h -> h x : g (f . h)) (const []) l id

But it seems more natural and effective to not use foldr at all:

    it3 f l = zipWith ($) (iterate (f .) id) l

Best regards,
Tom

--
.signature: Too many levels of symbolic links