headers
Benjamin Franksen | 1 Sep 2006 01:13
Picon

Re: A free monad theorem?

Tomasz Zielonka wrote:
> On Thu, Aug 31, 2006 at 07:23:55PM +0200, Benjamin Franksen wrote:
>> I'd like to know if the following reasoning can be made more precise:
>> 
>> As we all know, the monadic bind operation has type:
>> 
>>         bind :: Monad m => m a -> (a -> m b) -> m b
>> 
>> My intuition says that in order to apply the second argument to some
>> non-trivial (i.e. non-bottom) value of type a, the bind operator needs to
>> be able to somehow 'extract' a value (of type a) from the first argument
>> (of type m a).
> 
> The bind operator doesn't have to neccesarily apply the second argument
> to anything. What if m is Maybe, and the first arguments is Nothing?

True, however if the instance for Maybe would have been defined
without /ever/ applying the second argument to anything, then wouldn't this
necessarily be a trivial monad (however one would need to define 'trivial'
here)?

> And if the bind operator "wants" to apply the second argument to
> something, it doesn't have to do it only once - consider the [] monad.

Yes, I should have said: Any non-trivial definition of bind has to apply its
second argument at least in _some_ cases and _at least_ once to something
non-bottom.

> Other examples:
>
(Continue reading)

Permalink | Reply | 18 comments |
headers
Robert Dockins | 1 Sep 2006 02:02

Re: Re: A free monad theorem?

> So getting the value out of the monad is not a pure function (extract ::
> Monad m => m a -> a). I think I stated that, already, in my previous post.
> I'd even say that the monadic values alone can be completely meaningless.
> They often have a meaning only relative to some environment, thus are
> (usually) _effectful_ computations. But we already knew that, didn't we?

It may help to remember that, in the mathematical context where monads where 
born (AKA category theory), a monad is generally defined as a functor with a 
join and a unit (satisfying some laws that I would have to look up).  The 
unit should be familiar (it's spelled 'return' in haskell), but join may not 
be.  Its type is

join :: Monad m => m (m a) -> m a

which is a lot like extract, except with one more "monad layer" wrapped around 
it.  IIRC the relevant identity here is:

x >>= f === join (fmap f x)

and with f specialzed to id:

join (fmap id x) === x >>= id
join x           === x >>= id

I'm not sure why (>>=) is taken as basic in Haskell.  At any rate, my point is 
that I think your questions might be better framed in terms of the behavior 
of 'fmap'.

> The real question (the one that bugs me, anyway) is if one can give a
> precise meaning to the informal argument that if the definition of bind is
(Continue reading)

Permalink | Reply | 0 comments |
headers
Albert Lai | 1 Sep 2006 04:22
Favicon

Re: HaXml question

Tim Newsham <newsham <at> lava.net> writes:

> I thought this one would be easy but I'm starting to think its not.
> I am playing with HaXml and I want to transform an XML tree into
> another tree.  The transforms are simple enough, but the kicker
> is that I want them to be "stateful."  In this example, the state
> is a random number generator.  So the transformation depends on
> the current node and the random number generator state.  I want
> to transform every node in the tree.

Indeed, the HaXml functions are pure, and in particular foldXml does
not thread a state through.

To introduce state, you provide your own state monad (fortunately
there is always Control.Monad.State).  To traverse the whole tree in
this monad, you write your own recursion and deconstruct the nodes
yourself (because foldXml is too specific to be re-usable).

Here is my example.  It replaces attribute values by random integers
between 0 and 99, so it is a similar task but slightly different from
yours.  Some names are inspired by yours, but I have simplified their
nature: The state I thread through is not a stream of generators, but
rather a stream of numbers; as long as this stream comes from
Random.randomRs, I'm good.

import Text.XML.HaXml
import Control.Monad.State
import Random

newtweak :: [Int] -> CFilter
(Continue reading)

Permalink | Reply | 0 comments |
headers
Tomasz Zielonka | 1 Sep 2006 07:22
Picon

Re: Re: A free monad theorem?

On Fri, Sep 01, 2006 at 01:13:14AM +0200, Benjamin Franksen wrote:
> So getting the value out of the monad is not a pure function (extract ::
> Monad m => m a -> a). I think I stated that, already, in my previous post.

The only generic way of "extracting" values from a monadic value is
the bind operator. The lack of extract function is a feature :-)
But now I know that you are not really claiming such a function exists.

> The real question (the one that bugs me, anyway) is if one can give a
> precise meaning to the informal argument that if the definition of bind is
> to be non-trivial then its second argument must be applied to some
> non-trivial value at one point (but not, of course, in all cases, nor
> necessarily only once)

How about using monad laws, specifically:

    (return x) >>= f == f x

We assume that >>= never uses it's second argument, so:

    (return x) >>= f == (return x) >>= g

Combining it with the above monad law we get:

    f x == (return x) >>= f == (return x) >>= g == g x

so

    f x = g x
(Continue reading)

Permalink | Reply | 14 comments |
headers
Andrea Rossato | 1 Sep 2006 10:16

Re: Re: A free monad theorem?

Il Fri, Sep 01, 2006 at 07:22:02AM +0200, Tomasz Zielonka ebbe a scrivere:
> On Fri, Sep 01, 2006 at 01:13:14AM +0200, Benjamin Franksen wrote:
> > So getting the value out of the monad is not a pure function (extract ::
> > Monad m => m a -> a). I think I stated that, already, in my previous post.
> 
> The only generic way of "extracting" values from a monadic value is
> the bind operator. The lack of extract function is a feature :-)
> But now I know that you are not really claiming such a function exists.

I do not understand this discussion, but I'd like to.

Can you please tell me what you are talking about in terms of this
example?
Thanks,
Andrea

module Test where

newtype M a = TypeConstructor {unpack::(a, String)}
    deriving (Show)

instance Monad M where
    return a = (TypeConstructor (a,""))
    (>>=) m f = TypeConstructor (a1,b++b1)
                where (a,b) = unpack m
                      (a1,b1) = unpack (f a)

putB b = TypeConstructor ((),b)
putA a = (TypeConstructor (a,""))
getA (TypeConstructor (a,b)) = a
(Continue reading)

Permalink | Reply | 12 comments |
headers
Bulat Ziganshin | 1 Sep 2006 08:43
Picon

Re[2]: state and exception or types again...

Hello Andrea,

Thursday, August 31, 2006, 4:22:49 PM, you wrote:

> The tutorial will have this outline: first we build a monad adding
> output, exception, and state. Then we use monad transformer to take
> out state and output and add debug, doing lifting, put(ing) and
> get(ing) by hand, to understand the central role of type
> matching/construction.

imho, your tutorial makes the error that is a very typical: when you
write your tutorial you already know what are monads and what the
program you will construct at the end. but your reader don't know all these!
for such fresh reader this looks as you made some strange steps, write
some ugly code and he don't have chances to understand that this ugly
code is written just to show that this can be simplified using monads.
i've tried to read it imaging myself as fresh reader and was stopped
at some middle because code was too complicated to understand and
it was completely imobvious (for fresh reader) that we just wrote
"innards" of monad and then will reduce all this ugly code just to
">>=" calls

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Permalink | Reply | 3 comments |
headers
Bulat Ziganshin | 1 Sep 2006 08:48
Picon

Re: A free monad theorem?

Hello Benjamin,

Thursday, August 31, 2006, 9:23:55 PM, you wrote:

> The background for my question is an argument I had some time ago with
> someone about what the 'real nature' of monads is. He argued that monads
> are mainly about 'chaining' (somehow wrapped up) values in an associative
> way, refering to the monad laws.

my understanding of monads is that monad is a way to combine
functions. 'bind' operator defines algorithm of this combining for
each concrete monad. some monads thread values, some spread them, some
just sequence computations

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Permalink | Reply | 1 comment |
headers
Bulat Ziganshin | 1 Sep 2006 08:57
Picon

Re: Re: A free monad theorem?

Hello Benjamin,

Friday, September 1, 2006, 3:13:14 AM, you wrote:

> The real question (the one that bugs me, anyway) is if one can give a
> precise meaning to the informal argument that if the definition of bind is
> to be non-trivial then its second argument must be applied to some
> non-trivial value at one point (but not, of course, in all cases, nor
> necessarily only once), and that this implies that the computation
> represented by the first argument must somehow be 'run' (in some
> environment) in order to produce such a value.

'running' in lazy language is subtle thing :)  there is mfix/mdo

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Permalink | Reply | 0 comments |
headers
Andrea Rossato | 1 Sep 2006 11:34

Re: state and exception or types again...

Il Fri, Sep 01, 2006 at 10:43:14AM +0400, Bulat Ziganshin ebbe a scrivere:
> > The tutorial will have this outline: first we build a monad adding
> > output, exception, and state. Then we use monad transformer to take
> > out state and output and add debug, doing lifting, put(ing) and
> > get(ing) by hand, to understand the central role of type
> > matching/construction.
> 
> imho, your tutorial makes the error that is a very typical: when you
> write your tutorial you already know what are monads and what the
> program you will construct at the end. but your reader don't know all these!

Neither did I, actually.

> for such fresh reader this looks as you made some strange steps, write
> some ugly code and he don't have chances to understand that this ugly
> code is written just to show that this can be simplified using monads.
> i've tried to read it imaging myself as fresh reader and was stopped
> at some middle because code was too complicated to understand and
> it was completely imobvious (for fresh reader) that we just wrote
> "innards" of monad and then will reduce all this ugly code just to
> ">>=" calls

I do not entirely understand your point. I wrote just the first part
of the tutorial, till the "Errare Monadicum Est" chapter. From then
on, before writing the tutorial, I needed to understand what I was
headed to and so I wrote the code. Now the task is to explain each
step of that code.

Indeed I'm a fresh reader that did not find anything that she could
find useful to understand monads, and wrote her own.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Tamas K Papp | 1 Sep 2006 11:52
Picon
Favicon

Re: Re: data structures question

On Thu, Aug 31, 2006 at 11:09:07AM +0400, Bulat Ziganshin wrote:
> Hello Benjamin,
> 
> Wednesday, August 30, 2006, 11:40:09 PM, you wrote:
> 
> > Matthias Fischmann wrote:
> >> The trick is that Int is not the only index data type, but tuples of
> >> index data types are, too.  Do this:
> >> 
> >> | type Point = (State, State, Int)
> >> | type TypeV = Array State Double
> >> | 
> >> | matrix :: TypeV
> >> | matrix = array bounds values
> >> |    where
> >> |    ...
> 
> > Surely you meant to say
> 
> > | type TypeV = Array Point Double
> 
> which will require 128 gigs of memory for 32-bit cpus and even
> slightly more for 64-bit ones :)

Bulat,

Can you please explain this?  The following code works fine for me,
and I don't have that much RAM ;-) It seems I am not getting
something.
(Continue reading)

Permalink | Reply | 1 comment |

Gmane