## Wednesday, March 05, 2008

### My current favorite little Haskell function

Here's my pet Haskell combinator du jour:
`infixr 2 |||(|||) :: Maybe a -> Maybe a -> Maybe aNothing ||| x = xx ||| _ = x`
This gives you a concise notation for branching in the Maybe monad, so instead of having to write:
`case x `lookup` env1 of Just v -> Just \$ f1 v Nothing -> case x `lookup` env2 of              Just v -> Just \$ f2 v              Nothing -> Nothing`
you can write:
`do { v <- x `lookup` env1; return \$ f1 v } |||do { v <- x `lookup` env2; return \$ f2 v }`
This gives you the same kind of idiom that Schemers use or for. Come to think of it, I guess you could also write the analog of and:
`infixr 3 &&&(&&&) :: Maybe a -> Maybe a -> Maybe aJust _ &&& r@(Just _) = r_ &&& _ = Nothing`
I haven't used this one yet, but it seems natural.

Dan Licata said...

It's Haskell: you're not allowed to eta-expand the do! =)

infixr 1 |||

(|||) :: Maybe a -> Maybe a -> Maybe a
Nothing ||| x = x
x ||| _ = x

test f1 f2 env1 env2 x =
f1 =<< (x `lookup` env1) |||
f2 =<< (x `lookup` env2)

&&& is a little less canonical, because you have to pick whether you give back the value of the first or second arguments when they're both Just.

Alec said...

As best I can tell, this is what the MonadPlus instance for Maybe does (that is, (|||), not (&&&)).

Dave Herman said...

Hi Dan--

&&& is a little less canonical, because you have to pick whether you give back the value of the first or second arguments when they're both Just.

Well, there's precedent in dynamically typed languages for logical and to evaluate to the last expression's value on success. It's useful to have a convention like that so programmers can set up the conjunction in the right order to get the result they want.

Of course, having order-sensitivity for logical conjunction disrupts the mathematical analogy, but after all, this isn't

data Maybe = T | F

it's

data Maybe a = Just a | Nothing

Dave Herman said...

Alec--

Good point! If I've got this right, (|||) is analogous to the "addition" operation of a group, and (&&&) is like the "multiplication" operation of a ring. Yes?

It's been a long time since I learned group theory, but my first thought is that the order-sensitivity of choosing the last value as the value of the (&&&) expression doesn't ruin the ring-nature, it just ruins Abelian-ness.

Dave Herman said...

Oops, no, it appears a ring must be Abelian.

I guess this is really where the order-sensitivity of (&&&) gets in the way of the algebraic properties. Then again, as a programming construct, it's still more useful than

(&&&) :: Maybe a -> Maybe a -> Bool

Jacob Matthews said...

Actually both &&& and ||| are already lurking in the Maybe monad:

-----------------------------------

infixr 1 &&&
infixr 1 |||

(&&&) :: Maybe a -> Maybe a -> Maybe a
a &&& b = a >> b >>= return

(|||) :: Maybe a -> Maybe a -> Maybe a
(|||) = mplus

-----------------------------------

*Main> Nothing &&& (Just 2)
Nothing
*Main> (Just 1) &&& Nothing
Nothing
*Main> Nothing &&& Nothing
Nothing
*Main> (Just 1) &&& (Just 2)
Just 2
*Main> Nothing ||| (Just 2)
Just 2
*Main> (Just 1) ||| Nothing
Just 1
*Main> Nothing ||| Nothing
Nothing
*Main> (Just 1) ||| (Just 2)
Just 1

Jacob Matthews said...

A better definition for &&&:

(&&&) :: Maybe a -> Maybe a -> Maybe a
(&&&) = (>>)

Dave Herman said...

Jacob--

I should have remembered that from Mitch's work on the backtracking monad (Relating Models of Backtracking).

Dave Herman said...

As another afterthought, even if order-sensitivity is not quite as mathematically well-behaved as commutativity, the fact that conjunction is just bind suggests that, well, it's still got a fairly nice mathematical structure -- it's a monad!

Alec said...

If I've got this right, (|||) is analogous to the "addition" operation of a group

I don't think so. It's close, but I can't figure out what the inverse operation is. That is, presuming that the identity of the algebra is Nothing, I can't think of a value v such that:

Just 4 (|||) v == Nothing

That being said, it's certainly a monoid (that is, a group without inverses), and monoids are the underlying "addition" for semirings, which are rings without abelian addition. So, if I may wave my hands wildly for a bit, the monad laws give us that (>>) is associative, and has an identity. So that makes (>>) a monoid over Maybe as well (in fact, I believe that's the "mon" part of "monad"). If it distributes over (|||), which I believe it does, then you ought to have a semiring on your hands.

I'm not sure what that gets you, of course.

One final note: if you're implementing them yourself,

(&&&) :: Maybe a -> Maybe a -> Maybe a
Just _ &&& r = r
_ &&& _ = Nothing

which has some strictness benefits. Also, in more point-free style:

(&&&) :: Maybe a -> Maybe a -> Maybe a
(&&&) (Just _) = id
(&&&) _ = Nothing

I'm sure there's a way to write this with no points at all, using isJust and some other combinators, but I can't figure it out.

Unknown said...

Hi,

Just to clarify the mathematical terminology:

A semigroup is a set with an associative binary operation.

A monoid is a set with an associative binary operation * and a unit e for that operation, ie a*e = e*a = a for all e.

A commutative monoid is a monoid such that a * b = b * a for all a and b.

A group is a monoid with inverses: that is, for every a there's an a' such that a'*a = a*a' = e.

An abelian group is a group whose operation is commutative.

A semiring (sometimes called a "rig", for "ring without negatives") is a set R with two binary operations + and *, and a distinguished elements 0, such that (R,+,0) is a commutative monoid, (R,*) is a semigroup, and * distributes over +: ie, a*(b+c) = a*b + a*c and (b+c)*a = b*a + b*c for all a, b and c in R.

A ring is a semiring (R,+,*,0) such that (R,+,0) is a group (necessarily abelian).

A ring with unit is a ring with a distinguished element 1 which is a unit for *. Some authors require all their rings (and semirings) to have units.

A commutative ring is a ring such that * is commutative.

So what you've got here is something like a semiring, but not quite :-)

By the way, the "mon" in "monad" does indeed come from "monoid" - you can extend the definition of monoid to consider "monoid objects" in categories other than Set, and then monads are just monoid objects in the appropriate category. The monad laws, when expressed as commutative diagrams, are exactly the same as the usual laws for monoids.

HTH!