The list monad in Perl and Python
blog.plover.com
The list monad in Perl and Python
1–10 of 19 posts
Re: The list monad in Perl and Python
#2Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
Re: The list monad in Perl and Python
#3tl;dr
Re: The list monad in Perl and Python
#4Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
> 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))
for x in xs:
yield from f(x)
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 ``), 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
> time python3.4 test_yield.py
python3.4 test_yield.py 0.04s user 0.01s system 84% cpu 0.062 total
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)
Re: The list monad in Perl and Python
#5tl;dr
Gotta love the people downvoting you without thinking twice.
Re: The list monad in Perl and Python
#6Re: The list monad in Perl and Python
#7(The Internet being what this is, this comment is NOT criticism... it's elaboration and explanation.)
So part of what makes this so clean is that this is the "list monad" implementation, and nothing else at all. This is a perfectly fine implementation of the specific "monad", but there's no abstraction between the specific list implementation and the generic monad machinery.
This probably helps more clearly see what's going on with the list monad (arguably the simplest monad implementation that is also non-trivial and slightly hard to follow when you start mixing it with guards and such), but it will get a bit nastier when you factor out the monad machinery and have to invoke it too. Python also gets nastier when you can't fit everything into a lambda because of its restrictions. Plus once you have to put a "def" in the middle, it "pollutes" its way back up the stack, because in order for the closure to work properly it has to be defined inline (inner functions should have access to the outer scope's variables), which means everything above it has to be turned into a full function too.
So, on the one hand it is fair to point out this solution does work and isn't impossibly nasty to look at, but, on the other hand, it isn't generic and it will also tend to break down in practice for Python. Perl's actually comes out slightly nicer since the subroutines are indeed full subroutines so you don't have the lambda limitations to work with, but still impractically complicated if you try to abstract out the "monad" machinery.
Re: The list monad in Perl and Python
#8Re: The list monad in Perl and Python
#9Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
> 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, gen…
Thanks for the thorough analysis--you answered several of the follow-up questions I might have had.
Re: The list monad in Perl and Python
#10Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
> 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, gen…
What is the time to actually run the iterator to the end and extract and print the solutions?