Python fuctional style iterative algoritm?

Question

In Haskell there is a simple list function available

iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

In python it could be implemented as following:

def iterate(f, init):
  while True:
    yield init
    init = f(init)

I was kinda surprised that something basic like this is not part of the functools/itertools modules. Could it be simply costructed in functional style (i.e. without the loop) using the tools provided in these libraries? (Mostly code golf, trying to learn about functional style in Python.)

Answer 1

You can do it using some of the functions in itertools:

from itertools import accumulate, repeat

def iterate(func, initial):
    return accumulate(repeat(None), func=lambda tot, _: func(tot), initial=initial)

Although it's clearly not very clean. Itertools is missing some fundamental functions for constructing streams, like unfoldr. Most of the itertools functions could be defined in terms of unfoldr, as it happens, but functional programming is a little uncomfortable in Python anyways so that might not be much of a benefit.

Answer 2

There is a 3rd-party "extension" to the itertools module, more-iterools, that includes (among many other things) an iterate function defined exactly like you observed:

# Exact definition, minus the doc string...
def iterate(func, start):
    while True:
        yield start
        start = func(start)

Python lacks the optimization necessary to make a recursive definition like

def iterate(func, start):
    yield from chain([start], iterate(func, func(start))

feasible.

---

If you are curious, Coconut is a superset of Python that does do things like tail-call optimization. Try the following code at https://cs121-team-panda.github.io/coconut-interpreter/:

@recursive_iterator
def iterate(f, s) = (s,) :: iterate(f, f(s))

for x in iterate(x -> x + 1, 0)$[1000:1010]:
    print(x)

(I'm not entirely sure the recursive_iterator decorator is necessary. The iteration slice demonstrates, I think, that this avoids the recursion-depth error similar code in Python would produce.)