Trait for monads

[Ka Ter]

I experienced that all collection classes, options and some more classes
have common monadic methods like map, flatMap, filter, foreach, and so
on. But, is there a reason why there is no distinct interface for it ,
like a trait Monadic?
There is only the trait FilterMonadic but this is specific to collection
classes and expects a method withFilter.

If I want to generalize those monadic classes I have to apply an
implicit conversion which results in additional wrapper objects that
mostly have no additional use.

Any thoughts?

--
Best Regards

Ka Ter

[Alec Zorab]

You might want to take a look at scalaz, if you haven't already...

[Ka Ter]

I already saw scalaz. But there I also have to convert a Traversable[A]
explicitely using some 'asMA' or something like that. And I just
wondered why the scala standard lib does not provide a trait for
monadics when it itself uses that concept.

Best Regards

Ka Ter

[Rike-Benjamin Schuppner]

I don’t think there is a common interface. If you take a look at the collection classes: They all take an implicit CanBuildFrom parameter which I think is not really possible to generalise in a trait. (Or is it?)

The monadic methods are only connected through the syntax which statically transforms a for comprehension into a construct using these methods.

[Meredith Gregory]

Dear Ka,

It's even more unusual than this. Many data and control structures support multiple monadic interpretations. Therefore, it is important, from a reuse perspective to have a separation of the monadic api from the data structure. However, the for-comprehension sugar does not recognize this, but instead conflates the monadic api with the data structure. So, you need a trampoline between the two. A straightforward transliteration of the categorical structure is something like

trait Functor[M[_]] {

   def fmap [A,B] ( f : A => B ) : M[A] => M[B]

}

trait Monad[M[_]] extends {

   def unit [A] ( a : A ) : M[A]

   def mult [A] ( mma : M[M[A]]  ) : M[A]

}

then you need a trampoline into the for-comprehension syntax. This would be something like

trait ForTramp[M[_]] {

   self : Monad[M] => 

   trait Wrapper[A] {

     def inhabitant : M[A]

     def map [A,B] ( f : A => B ) : M[A] => M[B] = inhabitant.fmap( f )

     def flatMap [A,B] ( f : A => M[B] ) : M[B] = inhabitant.mult( inhabitant.fmap( f )( inhabitant ) )

   }

  implicit forTramp [A] ( ma : M[A] ) : Wrapper[A] = new Wrapper[A] { override def inhabitant : M[A] = ma }

}

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW

Seattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

[Ken McDonald]

Hi L.G,

Very cool. Also slightly spacy given that I'm operating on 2 1/2 glasses of wine. I realize you may not have the time, but if you do, would you be able to give a concrete example of your pure monadic defs (ignoring the conversion needed and all aspects of Scala for-syntax)? I'm slowly comprehending monads, but the missing pieces for me are "this...is a monad because...." and "this...is a monad because..." etc. Real examples, basically.

Thanks,

Ken

[Razvan Cojocaru]

Let me try my hand real quick at a midnight example J. This same question haunted me for a long time: who’s the monad?

 

List is the data structure. It already has the flatMap but ignore that for a moment.

 

The monad implementation for it then is:

 

object ListMonad extends Monad[List[_]] {

  def unit[A] (a:A) = List(a)

  def flatMap[A,B] (f:A=>List[B], l:List[A]):List[B] = l.flatMap (f)

}

 

Who’s the monad? Well, it says right there, the object is…

 

The data structure List, is usually also called ‘a monad’ because of the agreement that there is a ‘natural’ monad for it, i.e. a monad with the natural List flattening… in scala, things are a bit muddied also because the flatMap is a method on the List itself rather than a typeclass. However, the unit and type constructor are itself… so they can’t be expressed in a separate interface…

 

Note that Greg used the mult() in the Monad trait – that is a better depiction of the fact that this is merely an operation – the flattening. I used flatMap directly. For List, this this natural operation is concatenation.

 

Also – one of the things that a monad needs is a ‘type constructor’. List is this type constructor, for instance List[Int] is a newly constructed type.

 

Because List itself has all three characteristics of a monad, in scala, one could argue that List itself is the monad. However, there’s not much you can do with it other than using it in a for comprehension. That’s why the typeclass stuff is also needed (and available in scalaz).

- type constructor is List[]

- unit is List(a)

- flatMap is a method

 

 

To complete the pattern, you need an implicit from List to ListMonad – this is the typeclass pattern that for instance scalaz uses.

 

To understand this better, I’m sorry, but a dash of Haskell is in order. Mind you, I only understand enough Haskell to have a vague idea what the following do…

 

There is a clear distinction between the data structure, list or [] and the monadic stuff…

 

In Haskell, the Monad typeclass is defined as :

 

class Monad m where 

    return :: a -> m a 

  

    (>>=) :: m a -> (a -> m b) -> m b 

  

This is somewhat equivalent to scala’s:

 

trait Monad[m[_]] {

  def return[a] (value:a):m[a]

  def >>=[a,b] (x1 : m[a], x2 : a=>m[b]):m[b]

 

NOW it gets interesting. To create different implementation for this, in Haskell you do this:

 

instance  Monad []  where

  m >>= k          = concat (map k m)

 

this is the list monad truly. This is equivalent to the object ListMonad I had above, together with an implicit – in Haskell, the implicit is not necessary, the language does the magic.

 

Remember that [] is the List in Haskell, so the above translates into Monad[List[_]]

 

It gets even screwier than that in Haskell J but in a good way…

 

 

Well, I probably managed to confuse you even more, but these are bits and pieces that it took me a long time to piece together. Figured it might help at least me to review their relationship J

 

Cheers,

Razie

[Vlad Patryshev]

Good point, same with monoid, something becomes a monad only if we provide unit and multiplication (If I understood you correctly).

Thanks,
-Vlad

[Adriaan Moors]

On Wed, Oct 5, 2011 at 4:15 PM, Ka Ter <ter....@googlemail.com> wrote:

But, is there a reason why there is no distinct interface for it, like a trait Monadic?

yes, because our collections don't adhere to the classical Monadic interface

scala> "abc" map (_.toInt)

res0: scala.collection.immutable.IndexedSeq[Int] = Vector(97, 98, 99)

so, written as a function, in this example, map has type String => (Char => Int) => IndexedSeq[Int]

that does not fit the monadic mold, where the signature for map must be like M[T] => (T => U) => M[U]

instead, we have more precise types for these "transformation" methods: they preserve the original collection whenever possible

scala> "abc" map (identity)

res1: String = abc

However, as illustrated in my first example, they fall back when necessary.

Thanks to the CanBuildFrom pattern, we do have a uniform signature (and an efficient, universal, implementation!) for map, waaaay up in the collection hierarchy (in TraversableLike):

  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {

    val b = bf(repr)

    b.sizeHint(this) 

    for (x <- this) b += f(x)

    b.result

  }

I think we have achieved nice, uniform, abstractions in the collection library -- nicer, dare I say it, than the venerable Monad.

(Where "nice" is defined as "a good fit for Scala and Scala programmers".)

For more details, please have a look at "Fighting Bit Rot with Types" (http://lampwww.epfl.ch/~odersky/papers/fsttcs09.html), if you hadn't already

cheers

adriaan

[Ka Ter]

ok, thanks.

Well, if Monads stay beside classes like collections or options, what is a 'monadic'? Can I say that a class that combines a data structure together with the methods of a monad methods can be called a monadic?

Best Regards

Ka Ter

Am 06.10.2011 08:53, schrieb Vlad Patryshev:

Good point, same with monoid, something becomes a monad only if we provide unit and multiplication (If I understood you correctly).

Thanks,
-Vlad

On Wed, Oct 5, 2011 at 8:30 PM, Razvan Cojocaru <p...@razie.com> wrote:

Let me try my hand real quick at a midnight example J. This same question haunted me for a long time: who�s the monad?

�

List is the data structure. It already has the flatMap but ignore that for a moment.

�

The monad implementation for it then is:

�

object ListMonad extends Monad[List[_]] {

� def unit[A] (a:A) = List(a)

� def flatMap[A,B] (f:A=>List[B], l:List[A]):List[B] = l.flatMap (f)

}

�

Who�s the monad? Well, it says right there, the object is�

�

The data structure List, is usually also called �a monad� because of the agreement that there is a �natural� monad for it, i.e. a monad with the natural List flattening� in scala, things are a bit muddied also because the flatMap is a method on the List itself rather than a typeclass. However, the unit and type constructor are itself� so they can�t be expressed in a separate interface�

�

Note that Greg used the mult() in the Monad trait � that is a better depiction of the fact that this is merely an operation � the flattening. I used flatMap directly. For List, this this natural operation is concatenation.

�

Also � one of the things that a monad needs is a �type constructor�. List is this type constructor, for instance List[Int] is a newly constructed type.

�

Because List itself has all three characteristics of a monad, in scala, one could argue that List itself is the monad. However, there�s not much you can do with it other than using it in a for comprehension. That�s why the typeclass stuff is also needed (and available in scalaz).

- type constructor is List[]

- unit is List(a)

- flatMap is a method

�

�

To complete the pattern, you need an implicit from List to ListMonad � this is the typeclass pattern that for instance scalaz uses.

�

To understand this better, I�m sorry, but a dash of Haskell is in order. Mind you, I only understand enough Haskell to have a vague idea what the following do�

�

There is a clear distinction between the data structure, list or [] and the monadic stuff�

�

In Haskell, the Monad typeclass is defined as :

�

class Monad m where�

����return :: a -> m a�

��

����(>>=) :: m a -> (a -> m b) -> m b�

��

This is somewhat equivalent to scala�s:

�

trait Monad[m[_]] {

� def return[a] (value:a):m[a]

� def >>=[a,b] (x1 : m[a], x2 : a=>m[b]):m[b]

�

NOW it gets interesting. To create different implementation for this, in Haskell you do this:

�

instance� Monad []� where

� m >>= k��������� = concat (map k m)

�

this is the list monad truly. This is equivalent to the object ListMonad I had above, together with an implicit � in Haskell, the implicit is not necessary, the language does the magic.

�

Remember that [] is the List in Haskell, so the above translates into Monad[List[_]]

�

It gets even screwier than that in Haskell J but in a good way�

�

�

Well, I probably managed to confuse you even more, but these are bits and pieces that it took me a long time to piece together. Figured it might help at least me to review their relationship J

�

Cheers,

Razie

�

From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On Behalf Of Ken McDonald
Sent: October-05-11 9:05 PM
To: scala...@googlegroups.com
Subject: Re: [scala-user] Re: Trait for monads

�

Hi L.G,

�

Very cool. Also slightly spacy given that I'm operating on 2 1/2 glasses of wine. I realize you may not have the time, but if you do, would you be able to give a concrete example of your pure monadic defs (ignoring the conversion needed and all aspects of Scala for-syntax)? I'm slowly comprehending monads, but the missing pieces for me are "this...is a monad because...." and "this...is a monad because..." etc. Real examples, basically.

�

Thanks,

Ken

[Adriaan Moors]

sure, if the data structure + those methods adhere to the monad laws, why not call it a monad?

however, if the concept you're modeling isn't *truly* a monad, why shoehorn it in?

monads are fun for theorizing, gaining insights, and they definitely influenced the design of the collection libraries (among other things)

however, monads (or anything, really) should not become a straightjacket (let them be an inspiration that trains your mind to discern abstractions in general)

thus, "but is it a monad?" is not a requirement for good design (though it may be an inspiration)

anyway, and most importantly, please (pretty please), let's not start another monadic thread on scala-user (scala-debate is meant for that)

On Thu, Oct 6, 2011 at 9:58 AM, Ka Ter <ter....@googlemail.com> wrote:

ok, thanks.

Well, if Monads stay beside classes like collections or options, what is a 'monadic'? Can I say that a class that combines a data structure together with the methods of a monad methods can be called a monadic?

Best Regards

Ka Ter

Am 06.10.2011 08:53, schrieb Vlad Patryshev:

Good point, same with monoid, something becomes a monad only if we provide unit and multiplication (If I understood you correctly).

Thanks,
-Vlad

On Wed, Oct 5, 2011 at 8:30 PM, Razvan Cojocaru <p...@razie.com> wrote:

Let me try my hand real quick at a midnight example J. This same question haunted me for a long time: who’s the monad?

 

List is the data structure. It already has the flatMap but ignore that for a moment.

 

The monad implementation for it then is:

 

object ListMonad extends Monad[List[_]] {

  def unit[A] (a:A) = List(a)

  def flatMap[A,B] (f:A=>List[B], l:List[A]):List[B] = l.flatMap (f)

}

 

Who’s the monad? Well, it says right there, the object is…

 

The data structure List, is usually also called ‘a monad’ because of the agreement that there is a ‘natural’ monad for it, i.e. a monad with the natural List flattening… in scala, things are a bit muddied also because the flatMap is a method on the List itself rather than a typeclass. However, the unit and type constructor are itself… so they can’t be expressed in a separate interface…

 

Note that Greg used the mult() in the Monad trait – that is a better depiction of the fact that this is merely an operation – the flattening. I used flatMap directly. For List, this this natural operation is concatenation.

 

Also – one of the things that a monad needs is a ‘type constructor’. List is this type constructor, for instance List[Int] is a newly constructed type.

 

Because List itself has all three characteristics of a monad, in scala, one could argue that List itself is the monad. However, there’s not much you can do with it other than using it in a for comprehension. That’s why the typeclass stuff is also needed (and available in scalaz).

- type constructor is List[]

- unit is List(a)

- flatMap is a method

 

 

To complete the pattern, you need an implicit from List to ListMonad – this is the typeclass pattern that for instance scalaz uses.

 

To understand this better, I’m sorry, but a dash of Haskell is in order. Mind you, I only understand enough Haskell to have a vague idea what the following do…

 

There is a clear distinction between the data structure, list or [] and the monadic stuff…

 

In Haskell, the Monad typeclass is defined as :

 

class Monad m where 

    return :: a -> m a 

  

    (>>=) :: m a -> (a -> m b) -> m b 

  

This is somewhat equivalent to scala’s:

 

trait Monad[m[_]] {

  def return[a] (value:a):m[a]

  def >>=[a,b] (x1 : m[a], x2 : a=>m[b]):m[b]

 

NOW it gets interesting. To create different implementation for this, in Haskell you do this:

 

instance  Monad []  where

  m >>= k          = concat (map k m)

 

this is the list monad truly. This is equivalent to the object ListMonad I had above, together with an implicit – in Haskell, the implicit is not necessary, the language does the magic.

 

Remember that [] is the List in Haskell, so the above translates into Monad[List[_]]

 

It gets even screwier than that in Haskell J but in a good way…

 

 

Well, I probably managed to confuse you even more, but these are bits and pieces that it took me a long time to piece together. Figured it might help at least me to review their relationship J

 

Cheers,

Razie

 

From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On Behalf Of Ken McDonald
Sent: October-05-11 9:05 PM
To: scala...@googlegroups.com
Subject: Re: [scala-user] Re: Trait for monads

 

Hi L.G,

 

Very cool. Also slightly spacy given that I'm operating on 2 1/2 glasses of wine. I realize you may not have the time, but if you do, would you be able to give a concrete example of your pure monadic defs (ignoring the conversion needed and all aspects of Scala for-syntax)? I'm slowly comprehending monads, but the missing pieces for me are "this...is a monad because...." and "this...is a monad because..." etc. Real examples, basically.

 

Thanks,

Ken

[Alan Burlison]

On 06/10/2011 09:13, Adriaan Moors wrote:

> anyway, and most importantly, please (pretty please), let's not start
> another monadic thread on scala-user (scala-debate is meant for that)

This is still my favourite explanation:
http://blog.plover.com/prog/burritos.html ;-)

--
Alan Burlison
--

[Tony Morris]

Scalaz has asMA to assist implicit resolution when you don't feel like using type annotation to do same. This is unrelated to using the Monad trait.

There is no known way to represent the Monad trait in scala than how scalaz does it (since if there is, scalaz would steal it!)

I assume its absence on for-comprehensions in the language is for historical reasons, since that ability was before higher kinds.

[Alan Burlison]

On 06/10/2011 08:51, Adriaan Moors wrote:

> yes, because our collections don't adhere to the classical Monadic interface

Thanks for that Adriaan, I hadn't seen that spelled out so clearly
before, and it's interesting (and helpful) to see a real example of
'stepping outside' of a purely monadic model.

--
Alan Burlison
--

[Razvan Cojocaru]

There is one advantage (or disadvantage) of the current collections
approach, as well:

These both return List(2, 3, 4) but the first one steps outside the List
monad :)

for (x <- List(1,2,3); y <- Some(x)) yield y+1
for (x <- List(1,2,3); y <- List(x)) yield y+1

-----Original Message-----
From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On

[Meredith Gregory]

Dear Ka, et al,

i attempted to give an extended example of the real benefits to reuse of separating the monad api from the data structure in this blog post, and this video presentation on MSFT's C9. i pick an extremely simple data structure, a pair of containers (such as a pair of lists or a pair of sets) that just happen to also contain instances of the data structure. i submit here and in the video that were this separation maintained a lot of the current complexity and idiosyncratic aspects of Scala's collection library would simply disappear. To put it bluntly, it would take up a smaller footprint in my tiny pea brain, and likewise take up a smaller footprint in terms of sizes of jars.

BTW, in light of the letter Martin recently responded to, this example just happens to correspond to a data structure known to represent all numbers ever invented. You could not know that and still get a lot of benefit from understanding the consequences of structuring code this way. If you do have an interest in the "theoretical" aspect of the presentation, it is very enriching and opens the doors to possibilities not touched on yet in current models of what a location in a data structure is.

Best wishes,

--greg

[Ka Ter]

Hi Greg,

creat work! Although I didn't understand the stuff completely in detail, I think it is another concept where Monads can help to simplify code. A monad is also a view. That's the main message I'll take with me.

Best Regards

Ka Ter

[Shelby]

On Oct 6 2011, 3:51 pm, Adriaan Moors <adriaan.mo...@epfl.ch> wrote:

> On Wed, Oct 5, 2011 at 4:15 PM, Ka Ter <ter.ka...@googlemail.com> wrote:
> > But, is there a reason why there is no distinct interface for it, like a
> > trait Monadic?
>
> yes, because our collections don't adhere to the classical Monadic interface
>
> scala> "abc" map (_.toInt)
> res0: scala.collection.immutable.IndexedSeq[Int] = Vector(97, 98, 99)
>
> so, written as a function, in this example, map has type String => (Char =>
> Int) => IndexedSeq[Int]
>
> that does not fit the monadic mold, where the signature for map must be like
> M[T] => (T => U) => M[U]

I have also read about this in section "6 Ad-hoc Polymorphism with
Implicits", of the paper "Fighting Bit Rot with Types" by you and
Martin Odersky. Martin re-iterated this point today:

http://groups.google.com/group/scala-language/browse_thread/thread/cfcf64dfff14e76f/a2a8673c3456cf20?#a2a8673c3456cf20

I don't understand this rationale.

Conversion of container type can be can be accomplished with
`accumulate` for any Applicative, which is a weaker requirement (and
more generally composable) than Monad. See page 7 of Applicative
Programming with Effects, McBride and Paterson. Or even more
generally, any Functor can implement a general fold, and a fold can be
employed to map and construct a new container type.

In section 6 of "Fighting Bit Rot with Types", another justification
is that BitSet must be a subtype of Set[T] (for unspecified reasons),
and thus the method `map` for Set must be supported for BitSet. With
@specialized, I am thinking BitSet[T] could be supported with
BitSet[Int] being BitSet's existing semantics, and the rest of
BitSet[T] inheriting Set[T] semantics.

I made these arguments in the past:

http://stackoverflow.com/questions/1722726/is-the-scala-2-8-collections-library-a-case-of-the-longest-suicide-note-in-hist/7397388#7397388

more below...

> instead, we have more precise types for these "transformation" methods: they
> preserve the original collection whenever possible
>
> scala> "abc" map (identity)
> res1: String = abc
>
> However, as illustrated in my first example, they fall back when necessary.
>
> Thanks to the CanBuildFrom pattern, we do have a uniform signature (and an
> efficient, universal, implementation!) for map, waaaay up in the collection
> hierarchy (in TraversableLike):
>
>   def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]):
> That = {
>     val b = bf(repr)
>     b.sizeHint(this)
>     for (x <- this) b += f(x)
>     b.result
>   }
>
> I think we have achieved nice, uniform, abstractions in the collection
> library -- nicer, dare I say it, than the venerable Monad.
> (Where "nice" is defined as "a good fit for Scala and Scala programmers".)

By re-interpreting what `map` means in category theory with the
current non-monadic Builder model, afaics we have lost the simplicity
of simple set of orthogonal composable semantics (`map`, `fold`,
monoid's `append`) and gained the complexity (and type inference
corner cases?) of implicit builders.

By violating the category theory, have we lost the modularity and
reusability to compose functions that operate on unlifted types (the
types of the parameter) with lifted (parameterized) types generally?
Have we lost the ability to generally compose Functors, Applicatives
(Monads don't generally compose)?

Abstractly:

http://groups.google.com/group/ceylon-dev/msg/681d850036db95ea
(examples at this link)

1. Functor (i.e. `map`) enables reuse of any arity 1 function on
parametrized types
(collections, etc).

2. Applicative enables reuse any function of any arity on
parametrized
types (collections, etc).

3. Monad enables composition of functions that return parametrized
types
with those that don't:
http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html

4. State monad threads the state, S, through the composition of
functions
which do and do not operate on the encapsulated state (i.e. unlifted
and lifted functions compose).

5. Traversable combines a `map` and `fold` in a single pass
of the iteration, i.e. single walk of the contained T instances.

> For more details, please have a look at "Fighting Bit Rot with Types" (http://lampwww.epfl.ch/~odersky/papers/fsttcs09.html), if you hadn't already
>
> cheers
> adriaan

P.S. Adriaan, thank you so much for implementing higher kinds (I
understand you were the main implementer), without which Functor would
be impossible.