Monad tutorial

Zl1PP3

You know what they say: You can't become proficient in Lua without understanding monads.

I guess I think of a monad as some structure for slapping onto another type. If the another type is a type of number, then we can have monady things like list of numbers or maybe a number.

Some of the typical ones are pretty data structurey, but I think that in general it's more like some spacetime structure? Like lists and maybes are pretty spacey, but we can also have something like a promise of a number, which is like sure, there's data structure, but it's also like "maybe a number later" which uh has to do with time.

Whatever. We need a way to turn a value of the type we're slapping the monad onto into a value of the monad type. Like:

Something that takes a thing and gives us a list containing only that thing
Something that takes a thing and gives us a maybe-value with that thing present
Something that takes a thing and gives us a promise where the promised thing is like there right now and also it is that very thing

And we need the bindy flatmappy thing:

Something that takes a list of numbers and a function from a number to a list of numbers, and gives us a list of numbers
And so on

Blah blah. I'm most certainly not doing any promise stuff, but the others are fine:

function p(o)
  print(show(o))
end

List = {}
function List.unit(x) return { x } end
function List.bind(list, f)
  local res = {}
  for _, old in ipairs(list) do
    for _, new in ipairs(f(old)) do
      table.insert(res, new)
    end
  end
  return res
end

Maybe = {}
function Maybe.unit(x) return { value = x } end
function Maybe.bind(maybe, f)
  return maybe.value and f(maybe.value) or {}
end

If we had only the "monad interface" operations, lists and options would both just be containers that always had one element. Very uninteresting and not much fun:

local l = List.unit(2)
p(l)
local l2 = List.bind(l, function(n) return List.unit(n + n) end)
p(l2)

local m = Maybe.unit(3)
p(m)
local m2 = Maybe.bind(m, function(n) return Maybe.unit(n * n) end)
p(m2)

Something like: The "monad interface" stuff is some stuff that e.g. lists and maybes in some sense have in common and it's also stuff that is incredibly useless on its own. The different types better have other stuff we can do with them that is not part of the "monad interface" as well. Stuff like:

Making empty lists and longer lists and stuff
Making a maybe with no value
Whatever something or other with a promise I guess?

function List.of(...) return { ... } end

Maybe.nope = {}
function Maybe.orelse(m, v) return m.value or v end

So now things are more okay:

local function div(a, b)
  return b == 0 and Maybe.nope or Maybe.unit(a // b)
end

p(Maybe.orelse(div(7, 3), "nope"))
p(Maybe.orelse(div(7, 0), "nope"))

local function f(n) return List.of(n, n + n) end
p(List.bind(List.of(), f))
p(List.bind(List.of(1, 3, 5, 8), f))

OKAY VERY GOOD. GREAT.

And like then I guess we can write some stuff in terms of the "monad interface" and have it work with whichever:

local function foo(monad, m)
  return monad.bind(m, function(n) return monad.unit(n + n) end)
end

p(foo(Maybe, Maybe.nope))
p(foo(Maybe, Maybe.unit(5)))
p(foo(List, List.of(1, 2, 3)))

And be like ooh, foo worked on both lists and maybes! It's not very impressive so we might have to say ooh several times.

Or like:

local function map(monad, m, f)
  return monad.bind(
    m,
    function(x) return monad.unit(f(x)) end)
end
local function f(n) return n + n end

p(map(Maybe, Maybe.nope, f))
p(map(Maybe, Maybe.unit(5), f))
p(map(List, List.of(1, 2, 3), f))

Oh well.

The IO monad

Okay so in Haskell, if we wanna make an application, we don't normally "write a program," but instead write a plugin for the Haskell framework. The Haskell framework uses the plugin to set up callbacks into our code and stuff. I imagine this is familiar stuff for people who know Angular and Spring and such. Plugins are values of the IO type. Here's an IO:

IO = {}
function IO.unit(x) return { io = "value", value = x } end
function IO.putstr(str) return { io = "putstr", str = str } end
function IO.getline(code) return { io = "getline", code = code } end
function IO.bind(m, f) return { io = "bound", first = m, f = f } end

Again: The unit thing is probably the least interesting. Bind is okay. But like an important thing is that there are these other ways to get IO values as well. In this case putstr and getline.

Here's a framework:

function framework(plugin)
  if plugin.io == "value" then
    return plugin.value
  elseif plugin.io == "putstr" then
    print(plugin.str)
    return nil
  elseif plugin.io == "getline" then
    return web.read()
  elseif plugin.io == "bound" then
    local first = framework(plugin.first)
    return framework(plugin.f(first))
  end
end

Let's pretend that people have two names and write a plugin for asking about someone's names and then greeting them:

plugin = IO.bind(
  IO.putstr("What is your first name?"),
  function()
    return IO.bind(
      IO.getline("first"),
      function(first)
        return IO.bind(
          IO.putstr("What is your last name?"),
          function()
            return IO.bind(
              IO.getline("last"),
              function(last)
                return IO.putstr("Hi, " .. first .. " " .. last .. " :)")
              end)
          end)
      end)
  end)

And then plug it into the framework:

framework(plugin)

So convenient :) No idea why anyone would want to syntactically sugar any of that, but some people do.

Interpretation

Our plugin code never actually called the side-effecting things, print and web.read, itself. It just returned values that described what it needed done, along with callbacks, and let the framework deal with that side of things. That's not really "a monad thing" or anything, it's just a thing that's fun to do. Like it's cool that we can do the monad bind stuff on the values or whatever, but "returning values instead of performing side effects" is a fun and valuable idea on its own.

So the framework looks at the IO value it has and decides what to do with it. It goes like:

Oh, it just holds a value: I'll return that value.
Or oh, it's a putstr with a string: I'll show the string to the user.
Or oh, it's a getline: I'll go get a string from the user and return that.
Or oh, oh! It's an IO value bound to a function: I'll handle the IO value, pass the result to the function, and then handle the IO value I get back from the function.

Anyway. A thing we can do is to make a different version of the framework, e.g. for automated testing or something. Then we might not want to wait for user input, but maybe just automatically try different strings when "interpreting" a getline IO value.

We'll make another framework:

function testhalp(plugin, inputs)
  if plugin.io == "value" then
    return { { value = plugin.value, out = "" } }
  elseif plugin.io == "putstr" then
    return { { value = nil, out = "  " .. plugin.str .. "\n" } }
  elseif plugin.io == "getline" then
    local res = {}
    for _, s in ipairs(inputs[plugin.code]) do
      table.insert(res, { value = s, out = "  > " .. s .. "\n" })
    end
    return res
  elseif plugin.io == "bound" then
    local first = testhalp(plugin.first, inputs, i)
    local res = {}
    for _, fres in ipairs(first) do
      for _, lres in ipairs(testhalp(plugin.f(fres.value), inputs)) do
        table.insert(res, { value = lres.value, out = fres.out .. lres.out })
      end
    end
    return res
  end
end

function testframework(plugin, inputs)
  for i, res in ipairs(testhalp(plugin, inputs)) do
    io.write(i .. ":\n")
    io.write(res.out)
    io.write("\n")
  end
end

We'll run it, configured with our plugin and some strings to use for the getline stuff:

local inputs = {
  first = { "Mary", "James", "Blip", "Blop" },
  last = { "Smith", "Mlep", "Mlap" }
}

testframework(plugin, inputs)

Blep.