Moonbase

DRAFT: This chapter is a work in progress.

Something a Little More Useful

Identity, or Something Better

My, that felt great, didn’t it? Our first monad!

So, okay. Now what?

We’ve seen how it was made, but what do we do with it? Sadly, Identity isn’t really that useful. There’s no particular advantage to writing:

Identity::new( x ).pass { |v|
  f( v )
}.pass { |v|
  g( v )
}.value

over the basically identical:

g( f( x ) )

Let’s make a monad we can do something with. Let’s make it from the finest Ruby classes. Shiny. New. Well-oiled. Yet… familiar.

Let’s make a monad out of Array.

Array the Monad

Down to business. We’ve got our container type. Do you remember the other two pieces we need? wrap (a.k.a. unit or return) and pass (aka bind or >>=).

wrap

wrap, as you may recall, is supposed to wrap a single value in an instance of the relevent container.

For arrays, this is pretty straightforward:

def Array::wrap( value )
  [value]
end

(Probably you saw that coming.)

pass

Okay, now pass is a little more interesting. pass is supposed to give each wrapped value to the block, and for each individual value the block is supposed to return another array.

First try:

class Array
  def pass( &block )
    map( &block )
  end
end

Not bad. That does indeed give each value in the array to the block. Is it that easy? Well, not quite. Law number 2 catches us up short:

[1, 2, 3].pass { |x| Array::wrap( x ) } # => [[1], [2], [3]]

Crumbs. Law 2 is an identity law. If we pass values only to wrap them again, we’re supposed to get the exact same thing out as we put in.

We’ll need to eliminate a level of array nesting somehow … flatten it, even …

Second try:

class Array
  def pass( &block )
    map( &block ).flatten
  end
end

Let’s think about this again:

[1, 2, 3].pass { |x| Array::wrap( x ) } #=> [1, 2, 3]

Great! But … what if the values in the array are also arrays? Won’t Array#flatten also flatten them?

[[1, 2], [3, 4]].pass { |x| Array::wrap( x ) } #=> [1, 2, 3, 4]

Too deep! Too deep!

That’s no good. We’ll need to write a method that only flattens a single level. We’ll call it mjoin—I’ll tell you why in a minute.

class Array
  def mjoin
    combined = []
    each { |arr| result.push *arr }
    combined
  end

Or, if you want to get fancy, you could do it with Array#inject:

class Array
  def mjoin
    inject( [] ) { |combined, arr| combined + arr }
  end

Same deal, though. Just combine all the Arrays into one big array.

[[[1], [2]], [3], [4]].mjoin #=> [[1], [2], 3, 4]

Just right. We only peel off the outer layer. No marring the juicy flesh with our fingernails.

mjoin

Okay, yeah, mjoin. The reason I called it that is because join is another common monad operation. Not one of the core two, but it’s handy and any monad can have it. We’ll just have to call it Array#mjoin because Array#join is taken.

In case you’re curious, the same thing for Identity - Identity#mjoin – would look like this:

class Identity
  def mjoin
    value
  end
end

See, sometimes a monad gets nested in itself, and you want to peel away a layer of nesting. Like, say, when we’re defining Array#pass...

pass Redux

Now that we’ve got a good replacement for Array#flatten, let’s try again:

class Array
  def pass( &block )
    map( &block ).mjoin
  end
end

Play with it a bit. It should do the right thing now:

anyarray.pass { |x| Array::wrap( x ) } == anyarray

Does it check against the other monad laws? It should.

Monad PLUS

Let’s throw in a couple more monad operations. We’ll need them later on. Not every monad can have these two, but Array is up to it.

empty

empty (not to be confused with empty?) is like wrap, except it gives us an empty container rather than one containing a single value. Haskell calls it mzero.

def Array::empty
  []
end

Identity is jealous. It can’t have one because it can’t be truly empty (holding nil doesn’t count).

+

+ combines the contents of two instances of a monad’s container. Haskell calls it mplus. But Ruby already provides this one, ready-made for Array. How cool is that?

[1, 2] + [3, 4] #=> [1, 2, 3, 4]

Identity is, again, left out in the cold. Oh, if only it could hold more than one value at a time like Array can! (wrist to forehead)

Our Feet Touch the Ground

So, okay, let’s do some serious business here. We’ve got a for-real serious monad. A quick recap, then it’s time to put it to work.

Our Array Monad, All in One Piece

class Array
  def Array::wrap( value ) ; [value] ; end
  def Array::empty ; [] ; end
  def mjoin ; inject( [] ) { |combined, arr| combined + arr } ; end
  def pass( &block ) ; map( &block ).mjoin ; end
end

Go for it. Yeah.

Musing on Monad Mottos

Here’s a secret: every monad, depending on the container you build on and how you define pass, embodies a particular computational strategy. A “motto of computation,” if you will.

The motto of the Identity monad? Well… it doesn’t really have one. Bit of a blank slate. Just repeats what it hears, does what it is told.

But there are many other monads with many other mottos. The motto of our monad made from Array?

“Try every possibility.”

The Maze Problem

How about a maze solver? Okay. Everyone should write a maze solver sometime.

Let’s not make this too easy for ourselves, though.

How about multiple exits? Trapdoors in the floor or something. Blindfolded. Air-dropped at a random place in the maze. The maze has loops in it, so no “right hand rule” either. Yeah. Hardcore.

So here’s the API. For every square in the maze, we’ve got a Node. We’re blindfolded, but we can still feel around, and do one of four things:

1. Node#exit_here?—can we feel an exit trapdoor here?
2. Node#drop_breadcrumb—drop a breadcrumb (infinite supply)
3. Node#breadcrumb_here?—is there a breadcrumb here?
4. Node#neighbors—an array; where can we go from here?

A Maze Solution

We’ll write a function that takes a node and returns an array of exit nodes. If you must, in Haskell-ish parlance that’s Node -> [Node] (though [] means list rather than array in Haskell).

def solve( start )
  # been this way? then no more exits to find
  return Array::empty if start.breadcrumb_here?

  start.drop_breadcrumb # remember that we've been here

  # look, pass combines the results for us:
  other_exits = start.neighbors.pass do |direction|
    solve( direction )
  end

  if start.exit_here? # is there an exit here also?
    # include this node among the exits
    other_exits + Array::wrap( start )
  else
    other_exits
  end
end

Next: “Maybe a Monad”