Maybe? Definitely.
Here is a use of Scheme’s findf operator.
> (findf number? '(1 #f 2 dog))
1
Findf takes a predicate and a list, and returns the first element of the list for which that predicate holds true, returning #f in the case that the predicate holds for no member of the list.
So if we change 1 to one, then we will now get a different answer.
> (findf number? '(one #f 2 dog))
2
And if we change 2 to two, we get #f, as now no elements of the list are numbers.
> (findf number? '(one #f two dog))
#f
Lets instead ask a different question of this list: boolean?
> (findf boolean? '(one #f two dog))
#f
Whoa ho ho. What’ve we got /here/?
findf returns the first element of the list for which that predicate holds. #f is a boolean, so that’s what’s returned. Lo, the confusion that can result.
> (findf boolean? '(one two dog))
#f
Let’s look at the issue a bit more abstractly. The meat of the problem is that the value we’re using to denote an “error” (“failure”, “exception”, what have you) is /in/ the set of things that we could possibly return as /actual/ answers. Some languages use -1 as an error condition instead. Obviously, that’s no good as an error value here, either.
There’s not a safe value we can pick, because for whatever value we pick, it might be someone wants to hunt for precisely that value in their list. For instance, we might try to patch the problem above, saying to ourselves “Well, #f is useful. Comes up all the time. I’ll write my own findf, and pick a different thing.” Heck, we’ll choose this-obscure-symbol-means-failure-Qx29t7.
And that works great until some dingbat comes along and does the following
> (my-findf (lambda (y) (eqv? 'this-obscure-symbol-means-failure-Qx29t7 y))
'(a b c this-obscure-symbol-means-failure-Qx29t7))
this-obscure-symbol-means-failure-Qx29t7
But as it turns out, that might not be such a dingbat thing to do, after all. All the time, we write code that generates code. Someone who’s generating Scheme code might very well have reason to hunt for that symbol in a list.
Anyhow. What’s clear is that the above suggestion is just sort of a patch. These sorts of things come up all the time. We report #f, -1, Error 404, etc., etc. It seems like there ought to be a unified approach to handling this sort of problem, and one in which we don’t have to kludge together some sort of an error code for each distinct case.
The maybe monad gives us the power to do both of those. It provides a generic way to handle and propogate failure, and, by virtue of being general, it means there’s no ad-hoc solution to the value that denotes an error.
We’ve got return and maybe, those new relatives of eta and * that we introduced. And we’ve also got fail, which is our way of signaling a failure.
(define return-maybe
(lambda (a) `(Just ,a)))
(define bind-maybe
(lambda (ma f)
(cond
[(eq? (car ma) 'Just) (f (cadr ma))]
[(eq? (car ma) 'Nothing) '(Nothing)])))
(define fail
(lambda ()
'(Nothing)))
return is just another name for eta (or unit). More on that in a sec, but a quick reminder.
There’s lots of monads, and they all have the same type signatures for the return and bind, and they all have to obey those monadic laws. We’re gonna walk though, at a type level, what return and bind /are/, how those things relate to eta and *, why their essence and behavior makes sense, and then look at how the actual implementations of return-maybe and bind-maybe make sense.
Whew. That’s a tall order. Well, let’s get to it.
As we were. return is just another name for eta.
return : alpha -> Malpha
The job of return/eta is to take a “pure” value – that is, a value from the regular land of computation, and wrap it up in the monad (burrito) (or like Just above.)
For our maybe monad, there are two classes of things that are monadic values.
1 : (Just
This second one is the value provided by invoking fail. Notice that because all the pure values are wrapped up in a list with Just at the front, then this (Nothing) doesn’t have the same problem as we had before with -1 or #f.
If I want to return #f out of my findf-maybe (which we’ll write in a second), it’ll come out as (Just #f). If I want to signal something’s not in there, it’ll come out as (Nothing). (Of course, that could be #f).
And now, let’s consider that same dingbat from before, trying to be cute again.
> (findf-maybe (lambda (v) (equal v `(Nothing))) '(-1 #f (Nothing) 404))
(Just (Nothing))
Ah-HA! Lookie there. Unlike before with Scheme’s findf, now we can tell when the failure value is exactly that thing looked up in the list, vs. when it’s actually returned as a failure value. We’ve got the problem licked. Well, as soon as we figure out bind, relate it to *, explain why bind-maybe makes sense as a bind, and use this to implement findf-maybe.
-
was typed as follows.
-
: (alpha -> Mbeta) -> (Malpha -> Mbeta)
That is, it takes a function and returns a function. A few months ago that in and of itself might’ve been mind-blowing, but it’s pretty old-hat now. BTW, if you need a mundane example, integral is the sort of thing that takes a function and returns a function.
In the biz, we always associate curried functions to the left. If I have something that looks like
f : int -> (bool -> (string -> (bool -> (string -> int))))
those parens start to get a bit annoying there.
So we instead write it as
f : int -> bool -> string -> bool -> string -> int
but we all know what that means. So you’ll more likely see * typed like
- : (alpha -> Mbeta) -> Malpha -> Mbeta
That is, it’s gonna be a function that takes an f, then it takes an ma.
(define *
(lambda (f)
(lambda (ma) ...)))
And does … well, who knows what the /particular/ implementation does at this point, but it does something like calling the function on that argument.
A quick digression, seemingly apropos of nothing. Let’s define an operator curried-app.
(define curried-app
(lambda (f)
(lambda (a)
(f a))))
Nothing terribly fancy here.
BUT–imagine a world in which that’s the only way you apply functions. You don’t get to call them directly on their arguments. Instead, when you wanna apply a function, you pass it to curried-app, to which you then pass the argument upon which you wanna call that function.
There’s not much use to doing such a thing when we do our regular run-of-the-mill Scheme programming. But when we’re working with monads, it’s a necessity. By the way, did you notice the type of curried-app?
curried-app : (alpha -> beta) -> alpha -> beta
Remarkably, strikingly, /suspiciously/ similar to the type of *. * does what curried-app does, except it works over monads. When using monads, we’ve given up the necessity of doing our own function applications to arguments. It’s passe. Well, not really that, so much as we’re modeling effects, and we want to make sure the effects happen the right way. * (well, really it’ll be bind) is going to make sure that happens, ‘cause it and it alone is allowed to /do/ the application of functions to monadic arguments. So if * (bind) is right, then the whole process is right. We’ve deputized * (bind) as the function-apper. And because * (bind) has to obey the Monadic Laws if it’s to be a genuine, bonified, monad. Since we’re using pre-certified monads, we’re certain that they’re up to snuff, so if we just use’em correctly * (bind) will make all the applications work properly.
Alright, I’m done writing bind in parens. Let’s describe bind, so that we can just get to using it. A couple of things.
- Writing code with nested calls to * starts to get uuuugly.
((* (lambda (x)
((* (lambda (y)
((* (lambda (z) ...))
arg3)))
arg2)))
arg1)
The flow of control is going to the right. Programs written this way end up building these giant rightward dagger shapes.
- By doing all of our monadic code with calls to a function-apper mechanism, it makes sense to think of that part of the program as doing work in units of function-apping. “Do a *, which then demands another *, which …”. Why bother to curry *? Nothing’s gonna happen until we give it both parts, and it’s not really of use to do’em one at a time.
It’d be nice if my code read linearly, down the page, rather than having to follow it out in that triangle pattern, and if I treated these applications of function to argument as the real unit of work.
Bind does both of those.
The type of bind is
bind : (Malpha x (alpha -> Mbeta)) -> Mbeta
That is, it takes two arguments at once, the argument and the function, and it takes’em in that order. Notice, now, if we have some stuff that’s nested, then the work that we do next, that’s part of the function body, will be underneath the stuff above. We can read what’s going to happen in order down the page.
(define bind-maybe
(lambda (ma f)
(cond
[(eq? (car ma) 'Just) (f (cadr ma))]
[(eq? (car ma) 'Nothing) '(Nothing)])))
So here’s our definition of bind-maybe, again. We can see it’s doing
at least part of what we wanted it to do. It takes two arguments, in
the right order. We know that ma is one of the things in my maybe
monad. Which means it’s either a (Just
If instead we had a (Just
f, the function we pass in, the one we’re gonna build, needs to be of alpha -> Mbeta. That way, the thing we hand back is still safely nestled in the monad. That’s the reason behind the “monads are space-suits” metaphor. You can’t open a space-suit willy-nilly. You’ve got to do it nestled safely inside a space-capsule. If you do it outside, or go outside not wearing one, you’ll die in the cold, cold, blackness of space. Alone. That’s what happens to you if you try to get at the pure inside the monad when you aren’t supposed to.
A word about those alphas and betas there. They don’t /have/ to be distinct types. They can be. But they don’t have to be. I’m gonna put some !s around the parts that you really wanna pay attention to about the type of bind.
bind : (!Malpha! x (!alpha! -> Mbeta)) -> Mbeta
The point is that the thing f takes as an argument is exacty the same type as the first argument to bind, except the first argument to bind has it all wrapped up in the monad (burrito).
So that’s the gist of what maybe is. Let’s real quick write findf-maybe and, ‘cause findf-maybe doesn’t show off everything we’re gonna wanna do, we’ll write a somewhat contrived example that’ll show off bind-maybe, too.
(define findf-maybe
(lambda (p ls)
(cond
((null? ls) (fail))
...)))
So far, so good, this makes sense. We’ve been promising that we’ll return (Nothing) when we can’t findf the thing. Whelp, that’ll do it.
(define findf-maybe
(lambda (p ls)
(cond
((null? ls) (fail))
(else (let ((a (car ls)))
(cond
((p a) ...)
(else ...)))))))
So here, we’re just setting up and being a bit fancy. I happen to know for a fact that we’re going to need a couple of times, potentially, so I’m let-binding it above. There’s the remaining two cases: either (p a), or not. We’ll handle’em one at a time.
(define findf-maybe
(lambda (p ls)
(cond
((null? ls) (fail))
(else (let ((a (car ls)))
(cond
((p a) (return-maybe a))
(else ...)))))))
We wrap the thing up in the monad. findf-maybe is written to have return-type Mbeta. Which makes sense, according to our spec. We wanted it to return the stuff wrapped up, again, so we could tell the difference. That’s why we put it through return. Final case, the recursive call. Well, findf-maybe spits back something of Mbeta, which is what we’re after, so nothing special to do here, just the plain-ol’ regular recursion.
(define findf-maybe
(lambda (p ls)
(cond
((null? ls) (fail))
(else (let ((a (car ls)))
(cond
((p a) (return-maybe a))
(else (findf-maybe p (cdr ls)))))))))
Voilà. Go forth and findf to your heart’s content. I promised another example, this time with bind-maybe. We’re gonna try to write an operator that’ll take a list of numbers and return the product of their reciprocals. Why? You caught me, no good reason. But let’s do it anyway, for sport. Or something.
Now, the thing about reciprocals is that zero doesn’t have one. Division by zero is undefined. So when we try to do this, we’re gonna have to be on the lookout for a zero, and if we hit one, we come back out with (Nothing).
(define prod-recip-maybe
(lambda (ls)
...))
We’re just gonna blast right through to the new and interesting bit.
(define prod-recip-maybe
(lambda (ls)
(cond
((null? ls) (return-maybe 1))
(else
(let ((a (car ls)))
(cond
((zero? a) (fail))
(else ...)))))))
So we’ve got a non-zero number in the car. Let’s do the recursion, get that value, and then use it to return the value we’re really after. I’m doing the recursion, which means I’m coming back with a value in the monad. And then I wanna do something with the value of that recursive call, to get the value of the whole expression. This is a job for bind-maybe. If this was being done non-monadically, and we were using curried-app, again, it’d look like
((curried-app (lambda (rec) (* a rec)))
(prod-recip-maybe (cdr ls)))
But we’re not, we’re 1. in the monad, and 2. really /done/ with that curried-app thing. Since we’re in the monad, bind-maybe’s gonna do the job of pulling the pure out of the monadic value. And we’re gonna make sure that that function returns a monadic value, ‘cause the next fella up the line is expecting a value in the monad.
(define prod-recip-maybe
(lambda (ls)
(cond
((null? ls) (return-maybe 1))
(else
(let ((a (car ls)))
(cond
((zero? a) (fail))
(else
(bind-maybe
(prod-recip-maybe (cdr ls))
(lambda (rec)
(return-maybe (* (/ 1 a) rec)))))))))))
Well done. Buut, that is looking a little long, and is slightly obscuring. That do syntax we introduced would certainly clean some of this up.
(define-syntax do
(syntax-rules (<-)
((_ bind e) e)
((_ bind (v <- e) e* e** ...)
(bind e (lambda (v) (do bind e* e** ...))))
((_ bind e e* e** ...)
(bind e (lambda (_) (do bind e* e** ...))))))
It’s your standard, run-of-the-mill syntax-rules macro. We take which bind function it is, and a whole bunch of expressions, and expand out into nested calls to that bind in the right fashion. For our case, this yields
(define prod-recip-maybe
(lambda (ls)
(cond
((null? ls) (return-maybe 1))
(else
(let ((a (car ls)))
(cond
((zero? a) (fail))
(else
(do bind-maybe
(rec <- (prod-recip-maybe (cdr ls)))
(return-maybe (* (/ 1 a) rec))))))))))
And /there/ we go.
Now, Go Eat A Burrito! Maybe While Wearing A Space-Suit!