Here's my pet Haskell combinator du jour:

infixr 2 |||

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

Nothing ||| x = x

x ||| _ = 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 a

Just _ &&& r@(Just _) = r

_ &&& _ = Nothing

I haven't used this one yet, but it seems natural.

## 12 comments:

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

import Control.Monad

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.

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

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

andto 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

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.

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

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

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

import Control.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

A better definition for &&&:

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

(&&&) = (>>)

Jacob--

Duh! <slaps forehead>

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

As another afterthought, even if order-sensitivity is not quite as mathematically well-behaved as commutativity, the fact that conjunction is just

bindsuggests that, well, it's still got a fairly nice mathematical structure -- it's a monad!If I've got this right, (|||) is analogous to the "addition" operation of a groupI 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.

Hi,

Just to clarify the mathematical terminology:

A

semigroupis a set with an associative binary operation.A

monoidis 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 monoidis a monoid such that a * b = b * a for all a and b.A

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

abelian groupis 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

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

ring with unitis 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 ringis 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!

Post a Comment