Bad performance of _Reader created by 'then' method

[jakublabenski]

I do not know if this is a bug or correct behaviour. This is what I observed:

from pymonad.reader import Compose

def inc(x: int) -> int:
    print("inc:", x)
    return x + 1

def dec(x: int) -> int:
    print("dec:", x)
    return x - 1

iid = Compose(inc).then(inc).then(dec)
print(iid(0)) 

The result of execution is:

inc: 0
inc: 1
inc: 0
inc: 1
dec: 2
inc: 0
inc: 1
inc: 0
inc: 1
dec: 2
1 

I expected to see this:

inc: 0
inc: 1
dec: 2
1 

Implementation of _bind_or_map is responsible for this:

@pymonad.tools.curry(3)
def _bind_or_map(function_f, function_g, read_only):
    try:
        return _bind(function_f, function_g, read_only)
    except TypeError:
        return _map(function_f, function_g, read_only)

First _bind is used to compute the result. Bind do mapping and fails on actual binding.
Then everything is computed again by _map. This has exponential complexity.

I believe fix could do 'map' then try to 'bind':

@pymonad.tools.curry(3)
def _bind_or_map(function_f, function_g, read_only):
    ret = _map(function_f, function_g, read_only)
    try:
        return ret(read_only)
    except TypeError:
        return ret

[jasondelaat]

Hey, thanks for bringing this to my attention. Especially since it's something I should have noticed myself ages ago. Safe to say that exponential complexity is definitely not the intended behaviour.

So I've had a quick look at this and, unfortunately, won't have time to really dig into it until at least the weekend. But the good news is your solution appears to work for Reader. The bad news is other monad have similar constructions and therefore suffer the same complexity problem. And a similar solution doesn't appear to work for those. State in particular has even bigger problems which I'll need to figure out. Hopefully I can find a general solution to fix the problem across the board.

I'll keep you posted. In the meantime, using map and bind directly instead of deferring to then should avoid performance problems in most cases.

[jasondelaat]

So, I've fixed the exponential complexity problem in every monad where it was a problem and also fixed Promise which, it turns out, was really broken.
I haven't pushed the code yet because I need to test it thoroughly and clean it up some first which at this point will happen some time tomorrow afternoon my time (EST). New version should be on PyPi around the same time.

Thanks again for bringing this to my attention.

[jasondelaat]

Alright, all fixed. New version is 2.3.5 available here and on PyPi.