[masklinn]

> Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.

It isn't. It could be lazy if `bind` was defined as

    return itertools.chain.from_iterable(map(f, xs))

or

    for x in xs:
        yield from f(x)

(`unit` could also be defined as `yield x` but that wouldn't make much of a difference)

The provided program returns a `list` of all solutions though, not any sort of iterator, generator or otherwise.

This is confirmed by the runtime being anything other than instantaneous, a lazy version would just print the repr of the lazy iterator (say `<generator object bind>`), not the actual result (unless the iterator defined an __repr__/__str__ but very very few do, and those that do have little to nothing to compute e.g. dict views)

Original program:

    > time python3.4 test_list.py
    [(9567, 1085, 10652)]
    python3.4 test_list.py  6.43s user 0.02s system 99% cpu 6.480 total

Converted to `yield from` and `yield`:

    > time python3.4 test_yield.py
    <generator object bind at 0x1066ba7e0>
    python3.4 test_yield.py  0.04s user 0.01s system 84% cpu 0.062 total

nb: this comment assumes Python 3 is being used given the print function, Python 2 doesn't have `yield from` and you'd need `itertools.imap` as the builtin `map` is eager

nb2: on my machine, reifying the lazy version has roughly the same runtime as the eager version in CPython (2.7.10 and 3.4.3), in PyPy (2.6.0 ~ CPython 2.7.9) the reified lazy version (using chain.from_iterable) runs in half the time (~3s) as CPython and the eager version runs in 1/6ths the time (~1s)

[wging]

Thanks for the thorough analysis--you answered several of the follow-up questions I might have had.

[mjd]

What is the time to actually run the iterator to the end and extract and print the solutions?

[masklinn]

As indicated in the second note, in CPython (2.7 or 3.4) it's roughly the same as the eager version. In pypy the lazy version is about 3 times slower than the eager version.

Version from your post:

    > time python2.7 test_eager.py                           
    [(9567, 1085, 10652)]
    python2.7 test_eager.py  6.41s user 0.02s system 99% cpu 6.451 total
    > time python3.4 test_eager.py                           
    [(9567, 1085, 10652)]
    python3.4 test_eager.py  6.28s user 0.03s system 99% cpu 6.372 total
    > time pypy test_eager.py                                
    [(9567, 1085, 10652)]
    pypy test_eager.py  0.95s user 0.06s system 98% cpu 1.022 total

Using `yield from` (3.4-only) and wrapping the solutions() call in a `list()`:

    > time python3.4 test_yield.py                    
    [(9567, 1085, 10652)]
    python3.4 test_yield.py  6.28s user 0.02s system 99% cpu 6.313 total

Using chain.from_iterable + imap (or map in 3.4) and wrapping the solutions() call in a `list()`:

    > time python2.7 test_imap.py                    
    [(9567, 1085, 10652)]
    python2.7 test_imap.py  6.52s user 0.02s system 99% cpu 6.558 total
    > time python3.4 test_imap.py                    
    [(9567, 1085, 10652)]
    python3.4 test_imap.py  6.26s user 0.02s system 99% cpu 6.292 total
    > time pypy test_imap.py                    
    [(9567, 1085, 10652)]
    pypy test_imap.py  2.87s user 0.06s system 99% cpu 2.943 total

Versions used: Python 2.7.10, Python 3.4.3, PyPy 2.6.0 with GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57); all from macports