Short circuiting and the Maybe monad

older
another Newbie performance question

John Hamilton

12 May 2008 12 May '08

10:09 p.m.

I'm trying to understand how short circuiting works with the Maybe monad. Take the expression n >>= f >>= g >>= h, which can be written as (((n >>= f) >>= g) >>= h) because >>= is left associative. If n is Nothing, this implies that (n >>= f) is Nothing, and so on, each nested sub-expression easily evaluating to Nothing, but without there being a quick way to short circuit at the beginning. Now take the example do x <- xs y <- ys z <- zs return (x, y, z) which I believe desugars like xs >>= (\x -> ys >>= (\y -> zs >>= (\z -> return (x, y, z)))) Here the associativity of >>= no longer matters, and if xs is Nothing the whole expression can quickly be determined to be Nothing, because Nothing

...

...
= _ = Nothing. Am I looking at this correctly?

- John

Show replies by date

Abhay Parvate

13 May 13 May

5:13 a.m.

Yes, I had always desired that the operator >>= should have been right associative for this short cut even when written without the 'do' notation. On Tue, May 13, 2008 at 3:39 AM, John Hamilton wrote:

...

I'm trying to understand how short circuiting works with the Maybe monad. Take the expression n >>= f >>= g >>= h, which can be written as (((n >>= f) >>= g) >>= h) because >>= is left associative. If n is Nothing, this implies that (n >>= f) is Nothing, and so on, each nested sub-expression easily evaluating to Nothing, but without there being a quick way to short circuit at the beginning.

Now take the example

do x <- xs y <- ys z <- zs return (x, y, z)

which I believe desugars like

xs >>= (\x -> ys >>= (\y -> zs >>= (\z -> return (x, y, z))))

Here the associativity of >>= no longer matters, and if xs is Nothing the whole expression can quickly be determined to be Nothing, because Nothing

...
...
= _ = Nothing. Am I looking at this correctly?

- John _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

David Menendez

8:28 p.m.

2008/5/13 Abhay Parvate :

...

Yes, I had always desired that the operator >>= should have been right associative for this short cut even when written without the 'do' notation.

You pretty much always want "a >>= b >>= c" to parse as "(a >>= b) >>= c" and not "a >>= (b >>= c)". In the latter case, the two uses of (>>=) aren't in the same monad. You can get desired effect with the Kleisli composition operator (>=>), which is in recent versions of Control.Monad. Unfortunately, it has the same precedence as (>>=), so you can't use them together without parentheses. Using it, "a >>= b >>= c" can be rewritten "a >>= (b >=> c)" which is short for "a >>= \x -> b x >>= c". -- Dave Menendez http://www.eyrie.org/~zednenem/

Graham Fawcett

3:23 p.m.

On Mon, May 12, 2008 at 6:09 PM, John Hamilton wrote:

...

I'm trying to understand how short circuiting works with the Maybe monad. Take the expression n >>= f >>= g >>= h, which can be written as (((n >>= f) >>= g) >>= h) because >>= is left associative. If n is Nothing, this implies that (n >>= f) is Nothing, and so on, each nested sub-expression easily evaluating to Nothing, but without there being a quick way to short circuit at the beginning.

Yes, but that's still a 'quick' short-circuiting. In your example, if 'n' is Nothing, then the 'f >>= g >>= h' thunks will not be forced (thanks to lazy evaluation), regardless of associativity. Tracing verifies this:

...

import Debug.Trace

...

talk s = Just . (trace s) f = talk "--f" g = talk "--g" h = talk "--h"

...

foo n = n >>= f >>= g >>= h

*Main> foo (Just 3) Just --h --g --f 3 *Main> foo Nothing Nothing I suspect the cost of creating and discarding those unused thunks is negligible, so in effect the associativity of the bind operator is irrelevant here. Graham

Janis Voigtlaender

14 May 14 May

5:38 a.m.

Graham Fawcett wrote:

...

Yes, but that's still a 'quick' short-circuiting. In your example, if 'n' is Nothing, then the 'f >>= g >>= h' thunks will not be forced (thanks to lazy evaluation), regardless of associativity. Tracing verifies this:

No, it doesn't. What your tracing verifies is that the f, g, and h will not be evaluated. It doesn't verify that the 'f >>= g >>= h' part of the expression causes no evaluation overhead. Because that is not true. Consider the following:

...

import Debug.Trace

...

data Maybe' a = Nothing' | Just' a deriving Show

...

instance Monad Maybe' where return = Just' Nothing' >>= _ = trace "match" Nothing' Just' a >>= k = k a

...

talk s = Just' . (trace s) f = talk "--f" g = talk "--g" h = talk "--h"

...

foo n = n >>= f >>= g >>= h

Now: *Main> foo Nothing' match match match Nothing' So you get three pattern-matches on Nothing', where with the associative variant

...

foo' n = n >>= \a -> f a >>= \b -> g b >>= h

you get only one: *Main> foo' Nothing' match Nothing' For a way to obtain such improvements automatically, and without touching the code, you may want to look into http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

Andrew Coppin

7:03 p.m.

Janis Voigtlaender wrote:

...

http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf

"It is well-known that trees with substitution form a monad." ...OK, I just learned something new. Hanging around Haskell Cafe can be so illuminating! :-) Now, if only I could actually comprehend the rest of the paper... o_O

Dan Piponi

7:42 p.m.

On Wed, May 14, 2008 at 12:03 PM, Andrew Coppin wrote:

...

"It is well-known that trees with substitution form a monad."

Now that's funny. Compare with the first line of this paper: http://citeseer.ist.psu.edu/510658.html Anyway, I worked through an elementary example of this with usable source code here: http://sigfpe.blogspot.com/2006/11/variable-substitution-gives.html -- Dan

Derek Elkins

11:40 p.m.

On Wed, 2008-05-14 at 12:42 -0700, Dan Piponi wrote:

...

On Wed, May 14, 2008 at 12:03 PM, Andrew Coppin wrote:

...
"It is well-known that trees with substitution form a monad."

Now that's funny. Compare with the first line of this paper: http://citeseer.ist.psu.edu/510658.html

Well, it's well-known. Further, not only do they form a monad, but they are a free monad.

Andrew Coppin

16 May 16 May

7:03 p.m.

Andrew Coppin wrote:

...

Janis Voigtlaender wrote:

...
http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf

"It is well-known that trees with substitution form a monad."

...OK, I just learned something new. Hanging around Haskell Cafe can be so illuminating! :-)

Now, if only I could actually comprehend the rest of the paper... o_O

I'll probably regret this for the rest of my life, but... As best as I can tell, a monad is essentially a container of some kind, together with a function that puts stuff into a container, and another function that maps over the container and combines the results in some way. That would rather suggest that *any* container type is potentially a monad of some kind. [Although possibly not a *useful* one...] Since a tree is a kind of container, yes, it should be a monad. [I'm still not really sure whether it's "useful".] Presumably a set monad would work something like the list monad. One could imagine an array monad [although counting the size of the result set before allocating the array would seem rather expensive]. Perhaps a dictionary could be a monad? I'm not precisely sure how that would work. Hmm, what other kinds of random containers could you make a monad out of? [And would you bother?] On the other hand, Maybe is a rather odd kind of container, but a very useful monad...

Dan Piponi

10 p.m.

On Fri, May 16, 2008 at 12:03 PM, Andrew Coppin wrote:

...

Since a tree is a kind of container, yes, it should be a monad. [I'm still not really sure whether it's "useful".]

Not so much containers in general, but 'flattenable' containers. You can flatten a list of lists to a list like this: [[1,2,3],[4,5],[6]] -> [1,2,3,4,5,6] Similarly you can 'flatten' some kinds of trees of trees by grafting the contained trees directly into the containing tree. But consider containers that always contain exactly two elements. It's not immediately obvious how to flatten such a thing because a container of containers will have 4 elements so at the least you'll have to throw two elements away. In fact, you can use the Reader monad as a fixed size container monad.

...

On the other hand, Maybe is a rather odd kind of container, but a very useful monad...

Do you really find it odd? It's like many ordinary household containers: there's room to contain one object, but it might in fact be empty. -- Dan

Kim-Ee Yeoh

17 May 17 May

5:24 a.m.

Dan Piponi-2 wrote:

...

In fact, you can use the Reader monad as a fixed size container monad.

Interesting that you say that. Reader seems to me more as an anti-container monad. -- View this message in context: http://www.nabble.com/Short-circuiting-and-the-Maybe-monad-tp17200772p172883... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

David Menendez

6:38 a.m.

On Sat, May 17, 2008 at 1:24 AM, Kim-Ee Yeoh wrote:

...

Dan Piponi-2 wrote:

...
In fact, you can use the Reader monad as a fixed size container monad.

Interesting that you say that. Reader seems to me more as an anti-container monad.

You just have to think of the environment as an address into an implicit structure. For example, Bool -> a is isomorphic to (a,a). Thus, data Diag a = D { p1 :: a, p2 :: a } to :: Diag a -> (Bool -> a) to (D a b) p = if p then a else b from :: (Bool -> a) -> Diag a from f = D (f True) (f False) Some transformations applied to the monad instance for ((->) Bool) gets you: instance Monad Diag where return x = D x x D a b >>= f = D (p1 (f a), p2 (f b)) This works for any enumeration. Here's a more complex example, data Stream a = a :< Stream a type Nat = Integer -- we'll pretend this can't ever be negative to :: Stream a -> (Nat -> a) to (a :< as) 0 = a to (a :< as) n = to as n from :: (Nat -> a) -> Stream a from f = go 0 where go n = f n :< go (n + 1) shead (a :< as) = a stail (a :< as) = as instance Monad Stream where return x = x :< return x (a :< as) >>= f = shead (f a) :< (as >>= stail . f) Assuming I haven't mistyped anything, to (m >>= f) n = to (f (to m n)) n -- Dave Menendez http://www.eyrie.org/~zednenem/

Eric Stansifer

18 May 18 May

1:11 p.m.

...

Since a tree is a kind of container, yes, it should be a monad. [I'm still not really sure whether it's "useful".]

I have a use for the tree monad -- well, I have a use for the monadic `join' operation (but I don't use any of the monadic operations other than `return'). My program is making a file. It stores the lines in the file (I need the individual lines, for operations like "indent all lines by four spaces"): *> type File = [Line] And each line is a ordered collection of String s, waiting to be concatenated: *> type Line = [String] At the end of the day I need one long string: *> finish :: File -> String *> finish file = concat (concat file) (I'm eliding dealing with endlines, etc.) But elsewhere in my program, I would like to have an O(1) (++) operation, i.e., I would like to be able to do "line1 ++ line2" and "file1 ++ file2" in O(1) time. So I use a "Tree a" instead of "[a]":

...

type File = Tree Line type Line = Tree String finish file = concat (tree_to_list (tree_flatten file))

Admittedly, I'm not really doing anything actually "monadic" here -- I just happen to be using the `join' operation. I am sure others can come up with better examples. While we're at it, an example use for the ((->) a) monad. For any set S and ring R, the abelian group of functions f :: S -> R is a free module (in the mathematical sense of the word "module") over the ring R. The group and module operations are easily defined in terms of the monadic operations:

...

data FreeModule s r = FreeModule (s -> r) instance Functor (FreeModule s) where ... instance Monad (FreeModule s) where ... instance Ring r => Group (FreeModule s r) where (+) m1 m2 = liftM2 (+) m1 m2 negative m = fmap negative m zero = return zero

instance Ring r => Module r (FreeModule s r) where r *> m = fmap (r *) m

(Here I write `r *> m' to mean the module element `m' left-multiplied by the ring element `r'.) I have another implementation of FreeModule which specializes S to the natural numbers: but the set of functions f :: \mathbb{N} -> R are isomorphic with f :: [R] (provided we only permit infinite lists), in the same way that Dave Menendez describes how f :: Bool -> a is isomorphic to f :: Diag a. Under this isomorphism, we translate the monadic operations from ((->) \mathbb{N}) to monadic operations on lists -- but the resulting monad is different from the usual list monad (where join = concat is the "structure flattening" operation). After all, the `concat' operation is pretty boring if you only permit infinite lists (for then `concat' is the same as `head'). Eric

Eric Stansifer

1:17 p.m.

...

I have another implementation of FreeModule which specializes S to the natural numbers: but the set of functions f :: \mathbb{N} -> R are isomorphic with f :: [R] (provided we only permit infinite lists), in the same way that Dave Menendez describes how f :: Bool -> a is isomorphic to f :: Diag a.

This is what I get for reading only the first half of Dave Menendez's email... I saw the words "Here's a more complex example" and skipped the rest. Read his explanation -- it's a lot more coherent than mine. Eric

Graham Fawcett

15 May 15 May

1:27 p.m.

On Wed, May 14, 2008 at 1:38 AM, Janis Voigtlaender wrote:

...

Graham Fawcett wrote:

...
Yes, but that's still a 'quick' short-circuiting. In your example, if 'n' is Nothing, then the 'f >>= g >>= h' thunks will not be forced (thanks to lazy evaluation), regardless of associativity. Tracing verifies this:

No, it doesn't. What your tracing verifies is that the f, g, and h will not be evaluated. It doesn't verify that the 'f >>= g >>= h' part of the expression causes no evaluation overhead. Because that is not true.

I didn't mean to suggest that. I confess to using 'the f >>= g >>= h thunks' as a shorthand for the thunks for f, g and h, and not for the binding expressions. I did write later in my message that there would be evaluation overhead, but that I suspected it would be negligible (an imprecise and hand-waving statement, to be sure).

...

Consider the following:

...
import Debug.Trace

...
data Maybe' a = Nothing' | Just' a deriving Show

...
instance Monad Maybe' where return = Just' Nothing' >>= _ = trace "match" Nothing' Just' a >>= k = k a

Neat, I've never seen a bind operator used in a pattern. Thanks for this example.

...

...
talk s = Just' . (trace s) f = talk "--f" g = talk "--g" h = talk "--h"

...
foo n = n >>= f >>= g >>= h

Now:

*Main> foo Nothing' match match match Nothing'

So you get three pattern-matches on Nothing', where with the associative variant

...
foo' n = n >>= \a -> f a >>= \b -> g b >>= h

you get only one:

*Main> foo' Nothing' match Nothing'

For a way to obtain such improvements automatically, and without touching the code, you may want to look into

http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf

Much appreciated, Janis, I look forward to reading the paper. Graham

...

Ciao, Janis.

-- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

6260

Age (days ago)

6266

Last active (days ago)

List overview

Download

14 comments

10 participants

participants (10)

Abhay Parvate
Andrew Coppin
Dan Piponi
David Menendez
Derek Elkins
Eric Stansifer
Graham Fawcett
Janis Voigtlaender
John Hamilton
Kim-Ee Yeoh