Structure of Applicative vs. Monad computation

["Dr. Normen Müller"]

Hi, 

Taken from Typeclassopedia section 5.3 paragraph 2:

>The structure of an Applicative computation is fixed, whereas the structure of a Monad computation can change based on intermediate results.

* Why is the structure of an applicative computation fixed?

* Why can the structure of a monad computation change?

An applicative rsp. a monad give me (neglecting the call-by-name declaration)

def ap  [A, B] (fa: F[A]) (f: F[A => B]): F[B]

def bind[A, B] (fa: F[A]) (f: A => F[B]): F[B]

So why is the structure of an applicative computations fixed but not for a monad computation?

An illustrative, simple example is also appreciated.

Cheers, /nm

[Alois Cochard]

Hi Normen,

The structure of an applicative computation is fixed because the higher-order function you pass to the `ap` operation can not affect the structure (context) in any way (the higher-order function is lifter *in* the context F: F[A => B], but can not do any operation on it... it just "live" in it).

OTOH, the structure of a monad computation can change over the different application of the `bind` operation, this is simply due to the fact that the higher-order function that you pass to this operation can actually affect the structure: A => F[B], here your function can cleary create a "new" context F and replace the "old" one with it.

As an illustrative example let's take the domain of effects handling, for Applicative, you can think of any computations that can actually run concurrently and have no data dependency between them. Those computations are in that same given structure, but does not need to affect/operate on this structure in anyways.

You can imagine instances where the orderding of composition does not matter at all (as there is no data dependency).

But with a Monad, in the context of effects you can create new computation that depend on the value of a previous one (because `bind` allow you to return a new context after processing the value).
You can actually describe data-depency and affect the control flow of your effects.

I hope those short explainations will help you understand those beautitful abstractions!

Cheers

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at http://groups.google.com/group/scalaz.
For more options, visit https://groups.google.com/d/optout.

--

Λ\ois

http://twitter.com/aloiscochard

http://github.com/aloiscochard

[Normen Müller]

Hi Alois,

On Friday, June 12, 2015 at 2:24:34 PM UTC+2, Alois Cochard wrote:

Hi Normen,

The structure of an applicative computation is fixed because the higher-order function you pass to the `ap` operation can not affect the structure (context) in any way (the higher-order function is lifter *in* the context F: F[A => B], but can not do any operation on it... it just "live" in it).

Nice explanation! "It just lives in it" makes the point.

(Side note: I do not see any higher-order function here; the function I pass to `ap` is just a "normal" function from `A` to `B` lifted into the context `F`).

 

OTOH, the structure of a monad computation can change over the different application of the `bind` operation, this is simply due to the fact that the higher-order function that you pass to this operation can actually affect the structure: A => F[B], here your function can cleary create a "new" context F and replace the "old" one with it.

This I don't get. Let's instantiate `bind` for lists:

def bind[A, B](fa: F[A])(f: A => F[B]): F[B]

def bind[A, B](fa: List[A])(f: A => List[B]): List[B]

All `F`s are instantiate to `List`. So how can `f` create a new context, say, how can `f` modify the structure?

 

As an illustrative example let's take the domain of effects handling, for Applicative, you can think of any computations that can actually run concurrently and have no data dependency between them. Those computations are in that same given structure, but does not need to affect/operate on this structure in anyways.

You can imagine instances where the orderding of composition does not matter at all (as there is no data dependency).

But with a Monad, in the context of effects you can create new computation that depend on the value of a previous one (because `bind` allow you to return a new context after processing the value).
You can actually describe data-depency and affect the control flow of your effects.

I understand that with monads I can model dependencies, but how do/ can they change the structure?

 

I hope those short explainations will help you understand those beautitful abstractions!

I'm getting closer ;-)

Cheers, /nm

[Tomas Mikula]

Hi Normen,

On Fri, Jun 12, 2015 at 12:15 PM, Normen Müller
<normen....@gmail.com> wrote:
> Hi Alois,
>
> On Friday, June 12, 2015 at 2:24:34 PM UTC+2, Alois Cochard wrote:
>>
>> Hi Normen,
>>
>> The structure of an applicative computation is fixed because the
>> higher-order function you pass to the `ap` operation can not affect the
>> structure (context) in any way (the higher-order function is lifter *in* the
>> context F: F[A => B], but can not do any operation on it... it just "live"
>> in it).
>
>
> Nice explanation! "It just lives in it" makes the point.
> (Side note: I do not see any higher-order function here; the function I pass
> to `ap` is just a "normal" function from `A` to `B` lifted into the context
> `F`).
>
>>
>> OTOH, the structure of a monad computation can change over the different
>> application of the `bind` operation, this is simply due to the fact that the
>> higher-order function that you pass to this operation can actually affect
>> the structure: A => F[B], here your function can cleary create a "new"
>> context F and replace the "old" one with it.
>
>
> This I don't get. Let's instantiate `bind` for lists:
>
> def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
>
> def bind[A, B](fa: List[A])(f: A => List[B]): List[B]
>
>
> All `F`s are instantiate to `List`. So how can `f` create a new context,
> say, how can `f` modify the structure?

In bind, `f` gets to create the List (i.e. context), so it gets to
choose its structure---whether it is going to be Nil, singleton list,
etc.---based on the intermediate value(s) obtained from `fa`.

In `ap`, on the other hand, the structure of the resulting list does
not depend on the value(s) obtained from `fa`. The resulting List
structure depends only on the two lists (contexts), but not on the
contained values.

Best,
Tomas

["Dr. Normen Müller"]

Hi, thanks Alois and Tomas for your help! Cheers, /nm

> You received this message because you are subscribed to a topic in the Google Groups "scalaz" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/scalaz/DKGNn8I58RM/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to scalaz+un...@googlegroups.com.

[Alois Cochard]

You're welcome! Good to hear our messages helped you :)

You are absolutley right there is no higher order function involve, my bad sorry.

Cheers