> 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)
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
It isn't. It could be lazy if `bind` was defined as
or (`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:
Converted to `yield from` and `yield`: 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 eagernb2: 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)