Functools: add unfold as dual to reduce

Ideas
1

functools currently has the reduce function, but a dual function like unfoldr in Haskell is missing.

A simple implementation is:

V = TypeVar('V')
S = TypeVar('S')

def unfold(f: Callable[[S], Optional[Tuple[V, S]]], x: S) -> Iterable[V]:
    seed = x
    while (r := f(seed)):
        value, seed = r
        yield value

It can e.g. be used to implement a linspace function:

def linspace(start: float, end: float, num: int) -> Iterable[float]:
    step = (end - start) / num
    yield from unfold(lambda x: (start + step*x, x + 1) if x < num else None, start)

or to quickly generate objects given some criteria:

@dataclass
class A:
    x: int

    def inc(self) -> A:
        return A(self.x + 1)

    def square(self) -> int:
        return self.x ** 2


gen = unfold(lambda x: (x, x.inc()) if x.square() <= 16 else None, A(0))
2

I’ve never needed the unfold function you describe, and it’s pretty easy to write for yourself. What would be the benefit of having it in the stdlib?

As a general point, while Python borrows a lot of ideas from functional programming (list comprehensions being a very obvious one), typical Python code is generally much more imperative than functional. For example, most Python programmers would write unfolds as loops[1], effectively inlining the unfold call.

  1. And there’s a good chance they wouldn’t even know the term “unfold”. ↩︎

3

Hi,

thanks for the fast reply.

From my perspective it would make the story in functools more complete if both reduce and its dual unfold were there. True, unfold is not needed as often as reduce, but I already missed it in some occasions.

For me the function provided to unfold is shorter and easier to write as I only have to think about the current state and what to return next.

When I saw it correctly functools provides native implementations from _functools. So there would be a performance benefit over a manual implementation, I guess?

4

Could you provide an example of unfoldr being in a standard library of languages besides haskell? I have seen it in haskell but not in any other languages that are used in production environments.

From my point of view things like foldr are necessary in haskell due to its purely functional nature but in Python there are many clearer ways of implementing the same functionality.

1 Like
5

Is it clearer than the following iterative function?

def linspace(start: float, end: float, num: int) -> Iterable[float]:
    step = (end - start) / num
    x = start
    while x < num:
        yield start + step*x
        x = x + 1

Do you see a bug in these functions? Where is it easier to catch?

Compare with the correct and more idiomatic implementation:

def linspace(start: float, end: float, num: int) -> Iterable[float]:
    step = (end - start) / num
    for x in range(num + 1):
        yield start + step*x

def gen():
    x = A(0)
    while x.square() <= 16:
        yield x
        x = x.inc()

And it may be convenient to implement a generator for A:

class A:
    ...
    def count(self):
         return map(A. itertools.count(self.x))

gen = itertools.takewhile(lambda x: x.square() <= 16, A(0).count())
2 Likes
6

Other languages that include an unfold are Scala, F# and OCaml.

Good catch and yes in the direct comparison with my iterative version it’s probably easier to see. If you use a separate function instead of a lambda, both are probably comparable since the wrong use of start is closer to the beginning of the line.

The main benefits of unfold are that you can write smaller functions without explicit loops that can be tested separately. The drawbacks are that it’s not as efficient and pythonic.

7

Can you explain in words (not “study the implementation very carefully” or by example) what unfold does? What will the docs for this proposed function say? Assume that you are writing for people who are not familiar with Haskall or expert at functional programming idioms.

In other worlds, “unfold for dummies”, or “explain like I’m 5” if you prefer.

8

Maybe like this:

unfold takes two arguments 1) a function that takes a state and returns either a value together with a new state or None and 2) an initial state.

Initially, unfold applies the function to the initial state. If the function returns a value and a state it yields the value and updates the state. This process is repeated until the function returns None.

Since the function only cares about the current state, the value to return next and the new state it is usually easier to reason about. The iteration is automatically performed by unfold.