CODEWITHSUNDEEP
haskellfunctional-programmingiterationlazy-evaluationfold
Enlico
Enlico

Reputation: 28490

Can iterate be written with a fold?

Foreword

I was experimenting with the idea of repeatedly applying a function f to a given argument z, over and over, thus getting an infinite list.

Basically I want the list [z, f z, f (f z), f (f (f z)), ...], which I could feed to take n, takeWhile whatever, or something else.

Initially I thought that since the list I'm gonna deal with is infinite (I was thinking of repeat f), I should use foldr, but in reality that's not possible, because when foldring an infinite list the accumulator is usually set to undefined because unused, so in something like foldr (\f (x:xs) -> f x:x:xs) undefined (repeat f) I wouldn't have where to put z.

The question

So I started writing this question, and, thanks to the automatic suggestions that pop up, I discovered that iterate exists already, and its implementation is,

{-# NOINLINE [1] iterate #-}
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

so my question changed: is it possible to write iterate as a fold? If so, how? If not, why?

Upvotes: 4

Views: 525

Answers (2)

chi
chi

Reputation: 116174

To me using repeat f as you suggest amounts to "cheating", since you hide an infinite recursion in that infinite list. The proper way is to use anamorphisms (unfoldr) as Silvio Mayolo already explained.

That being said, if that's allowed then we can implement iterate as a fold. Here's an example where we obtain iterate ('b':) "X" in GHCi:

> take 9 $ foldr (\ x xs k -> k : xs (x k) ) (\_ -> []) (repeat ('b':)) "X"
["X","bX","bbX","bbbX","bbbbX","bbbbbX","bbbbbbX","bbbbbbbX","bbbbbbbbX"]

This uses the (in-)famous trick "calling foldr with four arguments". The idea is to make it so that the fold returns a function, which we eventually feed with the initial value of iterate, namely "X". This allows us to modify that fourth argument in each "recursive call": when we write xs (x k) we are essentially calling xs, the function computed by the fold on the rest of the list, with x k which is actually 'b':k, effectively passing the next value in the iteration list.

One of the reasons I don't like this approach is that we don't even need repeat f. Indeed, repeat () would be enough to drive the fold.

> take 9 $ foldr (\ _ xs k -> k : xs ('b':k) ) (\_ -> []) (repeat ()) "X"
["X","bX","bbX","bbbX","bbbbX","bbbbbX","bbbbbbX","bbbbbbbX","bbbbbbbbX"]

Even worse: if we have access to repeat () we can write out a fixed point combinator (for function types):

> myFix f = foldr (\ _ xs -> f . xs) id (repeat ()) id
> :t myFix
myFix :: ((a -> a) -> a -> a) -> a -> a

Here's the factorial computed using the fixed point operator:

> myFix (\g n -> if n==0 then 1 else n * g (n-1)) 5
120

Upvotes: 4

Silvio Mayolo
Silvio Mayolo

Reputation: 70357

No, or at least not in any idiomatic way. But that's because foldr is the wrong tool for the job. foldr is a fold, or catamorphism. That's a fancy mathematical way of saying it takes aggregate data (in this case, a list) and produces a single result (a scalar, such as a number). This is why operations like sum are straightforward to write in terms of foldr, because sum fundamentally takes aggregate data and produces a singular result.

What you want is an anamorphism, or a way to take a single point of data (z in your example) and produce aggregate data from that. In Haskell, this is appropriately named unfoldr.

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr starts with ab initial value b and calls the function it's given. Each time it calls the function, if it produces a Just (a, b'), then we use a as the first element of the list and continue with b' as the state value. If the function returns Nothing, then we stop iterating.

In your case, you want to produce an infinite list, so we'll always return a Just value. You can write iterate in terms of unfoldr as follows.

import Data.List(unfoldr)

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfoldr (\z -> Just (z, f z))

Upvotes: 12

Related Questions