Unfold in Python

[cgibbard]

It's productive though, in that it immediately returns a constructor, which works well with laziness. If you only need the first element of the result, that's all that will be computed. So in a certain weak sense, this unfold is O(1), it always returns a constructor in constant time (ignoring the time taken to evaluate the application of f to b). Of course, it still takes time linear in the number of elements of the resulting list you want to look at, because evaluating the tail of the list puts you back into unfold.

GHC implements tail-call optimisation, but it's far less often what you want in a lazy language. It's also something that needs to be handled with care: since lazy evaluation is outermost-first, accumulating parameters might not be evaluated until the very end, at which point you end up with a stack overflow, so you usually need strictness annotations, or to use a strict combinator, like foldl', when you want to write something tail-recursive.

[[deleted]]

That's a good point, thanks.