A collection of computer, gaming and general nerdy things.

Wednesday, April 29, 2015

I wrote a monad tutorial for some reason...

I swore to myself up and down that I wouldn't write one of these. But then I went and hacked up Pynads. And then I wrote a post on Pynads. And then I posted explainations about Monads on reddit. So what the hell. I already fulfilled my "Write about decorators when I understand them" obligation and ditto for descriptors. So Monads, why not...

It's simple, a monad is like a...

No. Stooooooop. :( Burritos. Bucket brigades. Semicolons. All these analogies just confused me for a long time. And then I "got them" and by "got them" I mean "Even more hopelessly confused but I didn't know that." Like what does "programmable semicolon" even mean? Every language I've used (which isn't many) a semicolon means "This bit of code ends here, kthxbai". The burrito analogy was meant as a critique of this phenomenon -- and I'll likely fall victim of the "Monad Tutorial Curse". And the bucket brigade was a valiant effort by a SO user to explain them.

It's simple, a monad is like a Unix Pipe

Instead of reaching for some non-programming analogy like burritos or bucket brigades, I think Unix Pipes are a pretty good analogy to Haskell-style monads. Let's say I'm in a directory that has a bunch of different types of files -- maybe it's the bottomless bin that is ~/Downloads ): And I want to find all the MP4 files in the top level directory and print them out:

ls -lh ~/Downloads | grep -i "*mp4" | less

Super simple. We take the first command ls feed it some options and a directory to list out. Then | goes "Oh, you have output and I have this thing that needs input, here grep!" And then grep does its business and | steps back in and goes "Oh, you have output and I have this thing that needs input, here less!"

Of course it isn't a perfect analogy. But all analogies break down under scrutiny. But this is essentially what Haskell's >>= does. "Oh, you have output, let me feed it to this function that wants input!" That's it. Monads are about chaining together a series of actions of functions (depending on how you want to look at it) in a way that each action/function returns something that can carry the chain forward somehow.

But the short of monads is that they have nothing to do with I/O, impure values, side effects or anything else. Those are implementation specific to certain monads. Monads in general only deal with how to combine expressions.

But Python doesn't have monads

Eh. It all depends on how you want to look at it. Sure, it doesn't have Haskell style monads. But it doesn't need to. Let's look at something:

In [1]:
x = y = '     Fred\n Thompson '

I have that input. But I need output that looks like this: "JACK THOMPSON". The obvious way is doing it imperatively:

In [2]:
x = x.replace('Fred', 'Jack')
x = x.replace('\n', '')
x = x.strip()
x = x.upper()
print(x)
JACK THOMPSON

And it works. Or I could just chain all those operations together:

In [3]:
print(y.replace('Fred', 'Jack').replace('\n', '').strip().upper())
JACK THOMPSON

Each string method returns a new string that can carry the chain forward. We can add in as many string methods that return a string. But if we place something like split or find then our chain can't be continued as there's a list or a integer now. That's not to say we can't continue the chain, but we likely need to do in a separate expression (which is okay).

Worshipping at the altar of bind

So Haskell style monads are pretty much defined by the presence of >>= and return. return just lifts a value into a monad. And >>= is the sequencing operator. Neither of these are magic, we need to define them ourselves. I like using Maybe as an example because it's simple enough to explain but addresses a real world problem: Null Pointer Exceptions. (:

We usually avoid this sort of thing with this pattern in Python:

In [4]:
def sqrt(x):
    if x is None:
        return None
    return x**.5

print(sqrt(4))
print(sqrt(None))
2.0
None

We can use this to process information from STDIN (for example):

In [5]:
def int_from_stdin():
    x = input()
    return int(x) if x.isdigit() else None
In [6]:
maybe_int = int_from_stdin()
print(sqrt(maybe_int))
a
None
In [7]:
maybe_int = int_from_stdin()
print(sqrt(maybe_int))
4
2.0

We just have to make sure we include the if x is None check everywhere. That's easy. Right. ...right? guise? On top of it being something to remember, it's line noise. Completely in the way of what we're attempting to accomplish. Instead, let's look at Maybe in terms of Haskell and Python:

data Maybe a = Nothing | Just a

instance Monad Maybe where
    return = Just
    (Just x) >>= f = f x
    Nothing  >>= f = Nothing

We have the type constructor Maybe which has two data constructors Just and Nothing. In Python terms, we have an abstract class Maybe and two implementations Just and Nothing. When we have a Just and >>= is used, we get the result of the function with the input of whatever is in Just. If we have Nothing and >>=is used, we get Nothing (Nothing from nothing leaves nothing. You gotta have something, if you wanna be with me). Notice that onus to return a Maybe is on whatever function we bind to. This puts the power in our hands to decide if we have a failure at any given point in the operation.

In Python, a simplified version looks a lot like this:

In [8]:
class Maybe:
    @staticmethod
    def unit(v):
        return Just(v)
    
    def bind(self, bindee):
        raise NotImplementedError
    
class Just(Maybe):
    
    def __init__(self, v):
        self.v = v
        
    def __repr__(self):
        return 'Just {!r}'.format(self.v)
    
    def bind(self, bindee):
        return bindee(self.v)

class Nothing(Maybe):
    
    def bind(self, bindee):
        return self
    
    def __repr__(self):
        return 'Nothing'

And we can use this to reimplement our int_from_stdin and sqrt functions above:

In [9]:
def int_from_stdin():
    x = input()
    return Just(int(x)) if x.isdigit() else Nothing()

def sqrt(x):
    return Just(x**.5)

And chain them together like this:

In [10]:
int_from_stdin().bind(sqrt)
4
Out[10]:
Just 2.0
In [11]:
int_from_stdin().bind(sqrt)
a
Out[11]:
Nothing

What >>= does isn't just sequence actions together. That's easy to do, we could have accomplished them the same thing before with sqrt(int_from_stdin()). However, the real magic sauce of >>= is abstracting how they're sequenced. In this case, sequencing a Just results in feeding the contained value of Just to a function and getting back a Maybe. And sequencing a Nothing results in Nothing.

The great thing about Maybe is we're allowed to decide at an arbitrary point if we even want to continue with the computation or bail out completely. Let's say we have something against even numbers. Perhaps it's that only one of them is Prime. But we like odds. So if we get an even number from STDIN, we'll just bail out.

In [12]:
def only_odds(x):
    return Just(x) if x&1 else Nothing()

int_from_stdin().bind(only_odds).bind(sqrt)
4
Out[12]:
Nothing
In [13]:
int_from_stdin().bind(only_odds).bind(sqrt)
3
Out[13]:
Just 1.7320508075688772

Other ways to sequence

Obviously bind/>>= isn't the only way to interact with monads if they're just about sequencing functions together. For example, Scala has a suped-up version of Maybe called Option. It's the same basic structure: Some (our successful computation) and None (a failed computation). It also has ways of recovering from a possibly failed computation with its getOrX methods. For example, if we have Some("abc") we can do this to recover when check if d is present:

Some("abc") filter (i => match i indexOf "d" {
                      case -1 => None
                      case _  => Some(i)
                      }
                    }) getOr "d"

Which should return "d" but Scala isn't my mother tongue, so there's probably an error somewhere.

You could argue that SQLAlchemy is monadic as well based on how you build queries in it:

q = session.query(Person).filter(Person.name.startswith('A')).first()

SQLAlchemy queries return query objects that can carry the chain further, allowing us to craft complicated queries in a relatively simple manner.

I found a more clever example in a thread on /r/learnpython about what features would you implement in Python given that chance. Below the "Everything not nailed down in Haskell" comment, there was one about universal function call syntax from D. /u/AMorpork proposed simply creating a monad where __getattr__ is the sequencing operation (reproduced here):

In [14]:
from itertools import islice
import builtins as __builtin__

def take(n, it):
    return islice(it, n)

class UFCS(object):
    def __init__(self, value):
        self.state = value

    def __getattr__(self, item):
        try:
            func = getattr(__builtin__, item)
        except AttributeError:
            func = globals()[item]
        def curried(*args):
            if not args:
                self.state = func(self.state)
            else:
                args = list(args)
                args.append(self.state)
                self.state = func(*args)
            return self

        return curried

    def get(self):
        return self.state
In [15]:
x = ['#3.462289264065068', 
     '4.283990003510465', 
     '#1.7285949138067824', 
     '#2.6009019446392987', 
     '5.089491698891653', 
     '3.854140130424576', 
     '4.118846086899804', 
     '5.110436429053362', 
     '9.044631493138326', 
     '5.503343391187907', 
     '1.4415742971795897', 
     '2.7162342709197618', 
     '9.438995804377226', 
     '1.8698624486908322', 
     '4.008599242523804', 
     '8.914062382096017', 
     '4.120213633898632', 
     '6.9189185117106975',
     # more were included, but removed here
     ]

UFCS(x).filter(lambda s: s and s[0] != "#").map(float).sorted().take(10).list().print()
[1.4415742971795897, 1.8698624486908322, 2.7162342709197618, 3.854140130424576, 4.008599242523804, 4.118846086899804, 4.120213633898632, 4.283990003510465, 5.089491698891653, 5.110436429053362]
Out[15]:
<__main__.UFCS at 0x7fd4c064ee10>

It's simple, a monad is like a...

Hopefully this goes a long way to explaining the idea of Monads in terms of programming. Maybe I fell upon the Monad Tutorial Fallacy. However, in the event that I've hopeless confused someone more, drop me a line and I'll be happy to go into further detail.

No comments:

Post a Comment