computation vs function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

computation vs function

Daniel Carrera-4
Hello,

I have finished the tutorial at http://ertes.de/articles/monads.html and
my understanding of monads has increased greatly. I still need to cement
some concepts in my mind. What exactly is the difference between a
computation and a function? Monads revolve around computations, so I'd
like to understand computations better.

Thanks for the help.

Daniel.
Reply | Threaded
Open this post in threaded view
|

computation vs function

Brent Yorgey-2
On Wed, Apr 22, 2009 at 10:38:14PM +0200, Daniel Carrera wrote:
> Hello,
>
> I have finished the tutorial at http://ertes.de/articles/monads.html and my
> understanding of monads has increased greatly. I still need to cement some
> concepts in my mind. What exactly is the difference between a computation
> and a function? Monads revolve around computations, so I'd like to
> understand computations better.

"Computation" does not really have any technical meaning, it's just
supposed to be an intuition.  But the term "computation" is often used
to refer to things of type (m a) where m is a Monad.  You can clearly
see from the types that something of type (m a) is different than
something of type (a -> b).  The former takes no inputs and somehow
produces value(s) of type a; the latter takes something of type a as
input and produces something of type b as output.

However, you could also legitimately thing of things of type (a -> b)
as "computations"; more interestingly, you can think of things of type
(a -> m b) as "parameterized computations" which can be composed in
nice ways.

Don't rely too heavily on the "computation" idea; monads certainly
don't "revolve around computations", it's only one particular way of
giving intuition for monads which does.

-Brent
Reply | Threaded
Open this post in threaded view
|

computation vs function

Daniel Carrera-4
Brent Yorgey wrote:

> "Computation" does not really have any technical meaning, it's just
> supposed to be an intuition.  But the term "computation" is often used
> to refer to things of type (m a) where m is a Monad.  You can clearly
> see from the types that something of type (m a) is different than
> something of type (a -> b).  The former takes no inputs and somehow
> produces value(s) of type a; the latter takes something of type a as
> input and produces something of type b as output.
>
> However, you could also legitimately thing of things of type (a -> b)
> as "computations"; more interestingly, you can think of things of type
> (a -> m b) as "parameterized computations" which can be composed in
> nice ways.
>
> Don't rely too heavily on the "computation" idea; monads certainly
> don't "revolve around computations", it's only one particular way of
> giving intuition for monads which does.

Thanks. That helps a lot.

It looks to me that one could replace the word "computation" everywhere
in the article with "monadic type" (where again, "monadic type" is just
an intuition for "m a" where m is a Monad) and the article would be
equally correct. Am I right?

The Wikipedia article seems to use "monadic type" for the same things
that ertes calls "computation".

I can't decide which term gives better intuition. The term "computation"
makes binding more intuitive: The computation (m a) returns a value of
type "a" can then be fed into a function of type (a -> m b). On the
other hand, "monadic type" is more intuitive when you write "Maybe Int"
or "IO String".

Anyways, thanks for the help. I'm (slowly) making progress.

Cheers,
Daniel.
Reply | Threaded
Open this post in threaded view
|

computation vs function

Andrew Wagner
I kind of like the term "monadic action" myself. Here's another perspective
that may help you out:
I really like the idea of the "programmable semicolon". That is, in your
typical programming languages, you're really working in an implicit State
monad. All the in-scope state is carried over from line to line, and each
line is separated by a semicolon.

In Haskell, we first get rid of this. We don't like the idea of being able
to modify state without being explicit about the types. But of course we
still allow you to carry state around. You use >>= to bind "lines" together
to use the same state. That's when you get to really take things a step
further, though: because state isn't the only "side effect" which you can
capture and hide away in a >>=. You can do it with IO, non-determinism,
potential failure, etc., etc. And that's where monads come in. It's an
interface for gluing together actions with "side effects" in a way in which
the actual effects are explicit, but hidden away in the class instance.

Hope this helps!

On Wed, Apr 22, 2009 at 5:06 PM, Daniel Carrera <
[hidden email]> wrote:

> Brent Yorgey wrote:
>
>> "Computation" does not really have any technical meaning, it's just
>> supposed to be an intuition.  But the term "computation" is often used
>> to refer to things of type (m a) where m is a Monad.  You can clearly
>> see from the types that something of type (m a) is different than
>> something of type (a -> b).  The former takes no inputs and somehow
>> produces value(s) of type a; the latter takes something of type a as
>> input and produces something of type b as output.
>>
>> However, you could also legitimately thing of things of type (a -> b)
>> as "computations"; more interestingly, you can think of things of type
>> (a -> m b) as "parameterized computations" which can be composed in
>> nice ways.
>>
>> Don't rely too heavily on the "computation" idea; monads certainly
>> don't "revolve around computations", it's only one particular way of
>> giving intuition for monads which does.
>>
>
> Thanks. That helps a lot.
>
> It looks to me that one could replace the word "computation" everywhere in
> the article with "monadic type" (where again, "monadic type" is just an
> intuition for "m a" where m is a Monad) and the article would be equally
> correct. Am I right?
>
> The Wikipedia article seems to use "monadic type" for the same things that
> ertes calls "computation".
>
> I can't decide which term gives better intuition. The term "computation"
> makes binding more intuitive: The computation (m a) returns a value of type
> "a" can then be fed into a function of type (a -> m b). On the other hand,
> "monadic type" is more intuitive when you write "Maybe Int" or "IO String".
>
> Anyways, thanks for the help. I'm (slowly) making progress.
>
> Cheers,
> Daniel.
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090422/da872308/attachment.htm
Reply | Threaded
Open this post in threaded view
|

computation vs function

Daniel Fischer-4
In reply to this post by Daniel Carrera-4
Am Mittwoch 22 April 2009 23:06:02 schrieb Daniel Carrera:

> The Wikipedia article seems to use "monadic type" for the same things
> that ertes calls "computation".
>
> I can't decide which term gives better intuition. The term "computation"
> makes binding more intuitive: The computation (m a) returns a value of
> type "a" can then be fed into a function of type (a -> m b). On the
> other hand, "monadic type" is more intuitive when you write "Maybe Int"
> or "IO String".

Yes, different expressions give better pictures for different aspects.
I think the term computation is meant to hint that the computations in one monad share a
common structure, much more so than general functions, so a different term was chosen.
Of course computations in different monads have different structures, but even these have
common aspects (which are then captured in the Monad type class).

>
> Anyways, thanks for the help. I'm (slowly) making progress.
>
> Cheers,
> Daniel.

Cheers,
Daniel
Reply | Threaded
Open this post in threaded view
|

computation vs function

Philippa Cowderoy
In reply to this post by Andrew Wagner
On Wed, 2009-04-22 at 17:13 -0400, Andrew Wagner wrote:
> I kind of like the term "monadic action" myself.

Action's great for IO, but it's less so for monads like lists that
aren't particularly about imperative ideas of computation. I still talk
about IO actions though.

--
Philippa Cowderoy <[hidden email]>

Reply | Threaded
Open this post in threaded view
|

computation vs function

Philippa Cowderoy
In reply to this post by Daniel Carrera-4
On Wed, 2009-04-22 at 23:06 +0200, Daniel Carrera wrote:
> It looks to me that one could replace the word "computation" everywhere
> in the article with "monadic type" (where again, "monadic type" is just
> an intuition for "m a" where m is a Monad) and the article would be
> equally correct. Am I right?
>

Maybe for that article, but generally it's the values that are
computations, not the types.

--
Philippa Cowderoy <[hidden email]>

Reply | Threaded
Open this post in threaded view
|

computation vs function

Philippa Cowderoy
In reply to this post by Daniel Carrera-4
On Wed, 2009-04-22 at 22:38 +0200, Daniel Carrera wrote:
> Hello,
>
> I have finished the tutorial at http://ertes.de/articles/monads.html and
> my understanding of monads has increased greatly. I still need to cement
> some concepts in my mind. What exactly is the difference between a
> computation and a function? Monads revolve around computations, so I'd
> like to understand computations better.
>

Computations are like "procedures" in other languages - you run them[1],
they yield a value. Conceptually, functions are (potentially infinite)
maps from their input to their output. We sometimes call functions with
types like "Int -> IO ()" monadic functions as well, which may also mean
the combination of the function and then the computation that results -
by analogy to functions in languages like C.

[1] Sometimes the runtime system runs them for you, like main. Sometimes
the computation is already its (lazily evaluated) output, like with
lists or Maybe.

--
Philippa Cowderoy <[hidden email]>

Reply | Threaded
Open this post in threaded view
|

Re: computation vs function

Ertugrul Söylemez
In reply to this post by Daniel Carrera-4
Daniel Carrera <[hidden email]> wrote:

> I have finished the tutorial at http://ertes.de/articles/monads.html
> and my understanding of monads has increased greatly. I still need to
> cement some concepts in my mind. What exactly is the difference
> between a computation and a function? Monads revolve around
> computations, so I'd like to understand computations better.

What I refer to as a 'computation' in the article is actually just a
value of type 'Monad m => m a'.  I have chosen that term, because you
can apply it to any monad I've seen.  As mentioned in section 5, you can
think of 'Just 3' as being a computation, which results in 3.  But it's
important that this is not a function, but just an independent value.

You can think of a function of type 'a -> b' as a parametric value -- a
value of type 'b' depending on some value of type 'a'.  That makes a
function of type 'Monad m => a -> m b' a parametric computation.  A
computation, where something is missing, like with an open slot, where
you need to plug a cable in first.

By the way, this is where (>>=) comes into play.  If you have a
computation, which needs a value, but that value comes as the result of
another computation, you can use the binding operator.

  f :: Monad m => a -> m b

The 'f' function is a parametric computation of type 'm b', which
depends on a value of type 'a'.  Now if

  c :: Monad m => m a

and 'm' and 'a' in 'f' are the same as 'm' and 'a' in 'c', then

  c >>= f

takes 'c', puts its result (of type 'a') into 'f', resulting in a
computation of type 'm b'.

Example:  You have a computation 'myComp', which outputs a string to
stdout prefixed with "+++ ":

  myComp :: String -> IO ()
  myComp str = putStrLn ("+++ " ++ str)

If that string is available directly, just pass it to 'myComp', which
results in a computation.  If that string is not available directly, but
comes as the result of another computation 'getLine', you use (>>=):

  getLine >>= myComp


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/


Reply | Threaded
Open this post in threaded view
|

Re: computation vs function

Daniel Carrera-4
Ertugrul Soeylemez wrote:
> What I refer to as a 'computation' in the article is actually just a
> value of type 'Monad m => m a'.  I have chosen that term, because you
> can apply it to any monad I've seen.  As mentioned in section 5, you can
> think of 'Just 3' as being a computation, which results in 3.  But it's
> important that this is not a function, but just an independent value.

Thanks.

I think the article would benefit from making the meaning of computation
clearer. The word computation appears in the tutorial 51 times before
section 5. That means that when I tried to go back for a definition of
computation I couldn't find one.

The first place you use the word computation is in the preamble, but
that's not a good place to define terms. The second time you use the
word computation is in section 2 "Motivation". This might be a good
place to define the term. The Motivation section already defines several
terms (referentially transparent, purely functional, etc), so it seems
like a good place to define computation as well.

In section 2 we can't say "Monad => m a" or "Just 3" because the terms
are not introduced yet. Perhaps you could say something like this:

<idea>
The word 'computation' here is not a technical term. I use it to refer
to something that returns a value without taking in any parameters. For
example (m a) is a computation that takes no parameters but returns a
value of type 'a' whereas (a -> b) is a function that takes a parameter
of type 'a' and returns a value of type 'b'. It is important that a
computation is not a function, but an independent value.
</idea>

I think that adding that as the third paragraph in the Motivation
section would be helpful. In addition, in the Preamble, when you use the
word computation, I would add "(see next section)".

Question: Would it be reasonable to say that a computation is a wrapper?
I'm not sure, because I don't know if a computation always results in
the *same* value (you know, side-effects). I know that "Just 3" always
results in 3, but is that universal?

Cheers,
Daniel.
Reply | Threaded
Open this post in threaded view
|

Re: computation vs function

Ertugrul Söylemez
Daniel Carrera <[hidden email]> wrote:

> > What I refer to as a 'computation' in the article is actually just a
> > value of type 'Monad m => m a'.  I have chosen that term, because
> > you can apply it to any monad I've seen.  As mentioned in section 5,
> > you can think of 'Just 3' as being a computation, which results in
> > 3.  But it's important that this is not a function, but just an
> > independent value.
>
> Thanks.
>
> I think the article would benefit from making the meaning of
> computation clearer. The word computation appears in the tutorial 51
> times before section 5. That means that when I tried to go back for a
> definition of computation I couldn't find one.
>
> The first place you use the word computation is in the preamble, but
> that's not a good place to define terms. The second time you use the
> word computation is in section 2 "Motivation". This might be a good
> place to define the term. The Motivation section already defines
> several terms (referentially transparent, purely functional, etc), so
> it seems like a good place to define computation as well.
>
> In section 2 we can't say "Monad => m a" or "Just 3" because the terms
> are not introduced yet. Perhaps you could say something like this:
>
> <idea>
> The word 'computation' here is not a technical term. I use it to refer
> to something that returns a value without taking in any
> parameters. For example (m a) is a computation that takes no
> parameters but returns a value of type 'a' whereas (a -> b) is a
> function that takes a parameter of type 'a' and returns a value of
> type 'b'. It is important that a computation is not a function, but an
> independent value.
> </idea>
>
> I think that adding that as the third paragraph in the Motivation
> section would be helpful. In addition, in the Preamble, when you use
> the word computation, I would add "(see next section)".

Yes, you're right about that and I'm going to restructure it a bit, when
I've got some time.  But I can't do much more than clarifying that the
term is just an intuition and that it shouldn't be confused with
functions, maybe writing a bit more about the difference between the
two.

This is precisely the reason why I mentioned Brent's blog post [1].  He
hit the nail right on the head.  I think a monads tutorial is supposed
to be read twice.


> Question: Would it be reasonable to say that a computation is a
> wrapper?  I'm not sure, because I don't know if a computation always
> results in the *same* value (you know, side-effects). I know that
> "Just 3" always results in 3, but is that universal?

Don't confuse the concept of a computation with the concept of running
it.  A computation does not result at all, unless you have a notion of
running it.  That notion defines what it means for a computation to
"result".  An IO computation can give different results in each run, a
Maybe computation can't.  I'm giving a few examples to make this
clearer:

* IO:  Running an IO computation is possible through running the
  program.  There is no safe notion of running a computation from
  Haskell.  This is intentional, as you can see in more detail in the
  tutorial.

* Parser:  Running a Parser computation is possible through parsing a
  text.  The result is the outcome of that process.

* State s:  Running a 'State s'-computation means calling the underlying
  function, which implements the stateful computation, with an initial
  state value.

* Maybe and []:  Running a Maybe or list computation is extracting its
  value through support functions (fromJust, maybe, head, tail, etc.) or
  through pattern matching.

Replace "wrapper" by "container", then you have another intuition for
monadic values.  An IO container contains some value, which depends on
world state, the Maybe container contains some value or not, the list
container contains arbitrarily many values, the Parser container
contains the outcome of parsing something, etc.

All in all, a monad is a wrapper type, but it doesn't exactly wrap
values.  There is an interesting counter-example, the unit monad:

  data Unit a = Unit

Think of it as a Maybe monad, which is constrained to Nothing.  There is
no result of the computation, there is no value in the container, there
is no whatever in the burrito.  Nonetheless Unit is a perfectly valid
monad and here is its instance:

  instance Monad Unit where
    return  = const Unit
    _ >>= _ = Unit


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/