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 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
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 bind suggests 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 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.
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!
Post a Comment