Re: [Haskell-cafe] Short circuiting and the Maybe monad
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Sat, May 17, 2008 at 1:24 AM, Kim-Ee Yeoh [EMAIL PROTECTED] 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 [EMAIL PROTECTED]
http://www.eyrie.org/~zednenem/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Fri, May 16, 2008 at 12:03 PM, Andrew Coppin [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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-tp17200772p17288351.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Wed, May 14, 2008 at 1:38 AM, Janis Voigtlaender [EMAIL PROTECTED] 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:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Wed, May 14, 2008 at 12:03 PM, Andrew Coppin [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Wed, 2008-05-14 at 12:42 -0700, Dan Piponi wrote: On Wed, May 14, 2008 at 12:03 PM, Andrew Coppin [EMAIL PROTECTED] 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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 [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
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:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Short circuiting and the Maybe monad
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
