Anyone care to explain why this doesn't return a gigantic list of empty arrays and one solution tuple? I don't see where the non-solution []'s are removed from the list.
The list monad in Perl and Python
11–19 of 19 posts
Re: The list monad in Perl and Python
#12Anyone care to explain why this doesn't return a gigantic list of empty arrays and one solution tuple? I don't see where the non-solution []'s are removed from the list.
There's an explanation in the earlier article (http://blog.plover.com/prog/haskell/monad-search.html), but it's because the `bind`/`bd` function takes the solution arrays from its callees, and concatenates the arrays into one big array of solutions, which it then returns to its caller.
In the Python code I think this is built into the behavior of the `+=` operator.
In the Perl code it's part of the way the `map` call works; it combines what would be `concat . map` in Haskell.
Re: The list monad in Perl and Python
#13Earlier quoted context omitted.
> 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?
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
> 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
> 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
Re: The list monad in Perl and Python
#14See also this much more detailed, four-part series on how to do the same in C++:
1. http://bartoszmilewski.com/2015/05/11/using-monads-in-c-to-s...
2. http://bartoszmilewski.com/2015/05/14/using-monads-in-c-to-s...
3. http://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-s...
4. http://bartoszmilewski.com/2015/05/25/using-monads-in-c-to-s...
Re: The list monad in Perl and Python
#15Anyone care to explain why this doesn't return a gigantic list of empty arrays and one solution tuple? I don't see where the non-solution []'s are removed from the list.
There's an explanation in the earlier article ( http://blog.plover.com/prog/haskell/monad-search.html ), but it's because the `bind`/`bd` function takes the solution arrays from its callees, and concatenates the arrays into one big array of solutions, which it then returns to its caller. In the Python code I think this is built into the behavior of the `+=` operator. In the Perl code it's part of the way the `map` ca…
Thanks for explaining and thanks for the post. It was helpful seeing an example of why you might want to use a monad.
Re: The list monad in Perl and Python
#16An alternative using Python's builtin monadic machinery (comprehensions) with a utility function to aid with threading around the remaining alphabet:
def to_number(*digits):
return sum(d * 10 ** n
for n, d in enumerate(reversed(digits)))
def choose1(digits, *exclude):
for digit in digits.difference(exclude):
yield digit, digits - {digit}
all_digits = set(range(10))
print [
(send, more, money)
for s, e, n, d, send, digits in (
(s, e, n, d, to_number(s, e, n, d), digits)
for s, digits in choose1(all_digits, 0)
for e, digits in choose1(digits)
for n, digits in choose1(digits)
for d, digits in choose1(digits))
for m, o, r, more, digits in (
(m, o, r, to_number(m, o, r, e), digits)
for m, digits in choose1(digits, 0)
for o, digits in choose1(digits)
for r, digits in choose1(digits))
for y, money, digits in (
(y, to_number(m, o, n, e, y), digits)
for y, digits in choose1(digits))
if send + more == money]
I find it very useful to remember that comprehensions deeply connected to monads: https://en.wikipedia.org/wiki/Monad_(functional_programming)...
Re: The list monad in Perl and Python
#17Nice work!
In the perl version, perhaps `remove` would be a bit faster to just delete a hash slice.
sub remove {
my ($b, $a) = @_;
my %h = map { $_ => 1 } @$a;
delete $h{@$b};
return [ keys %h ];
}Re: The list monad in Perl and Python
#18An alternative using Python's builtin monadic machinery (comprehensions) with a utility function to aid with threading around the remaining alphabet: def to_number(*digits): return sum(d * 10 ** n for n, d in enumerate(reversed(digits))) def choose1(digits, *exclude): for digit in digits.difference(exclude): yield digit, digits - {digit} all_digits = set(range(10)) print [ (send, more, money) for s, e, n, d, send, di…
Further showing the advantage of the pythonic way, is that the above construction remains about as clear when you refactor it for better pruning:
(
(to_number(s, e, n, d),
to_number(m, o, r, e),
to_number(m, o, n, e, y))
for d, digits in choose1(digits)
for e, digits in choose1(digits)
for y, digits in choose1(digits)
if (d + e) % 10 == y
for n, digits in choose1(digits)
for r, digits in choose1(digits)
if (n + r + (d + e) // 10) % 10 == e
for o, digits in choose1(digits)
if (e + o + (n + r + (d + e) // 10) // 10) % 10 == n
for s, digits in choose1(digits, 0)
for m, digits in choose1(digits, 0)
if (s + m + (e + o + (n + r + (d + e) // 10) // 10) // 10) % 10 == o
if (s + m + (e + o + (n + r + (d + e) // 10) // 10) // 10) // 10 == m)
(
(to_number(s, e, n, d),
to_number(m, o, r, e),
to_number(m, o, n, e, y))
for d, digits in choose1(digits)
for e, digits in choose1(digits)
for y, digits in choose1(digits)
if (d + e) % 10 == y
for n, digits in choose1(digits)
for r, digits in choose1(digits)
if (n + r + (d + e) // 10) % 10 == e
for o, digits in choose1(digits)
if (e + o + (n + r + (d + e) // 10) // 10) % 10 == n
for s, digits in choose1(digits, 0)
for m, digits in choose1(digits, 0)
if (s + m + (e + o + (n + r + (d + e) // 10) // 10) // 10) % 10 == o
if (s + m + (e + o + (n + r + (d + e) // 10) // 10) // 10) // 10 == m)Re: The list monad in Perl and Python
#19(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'…
This topic is amusing - the question of why you would want to do this has never come up, it is truly just art and playfulness.