defining a type for a class with map/flatMap

[Lucas Torri]

Hello everyone,

I was trying to define a type that would address any class that has the map/flatMap methods. I tried a few different approaches, but they all give me a different compiler error or would not give me the wanted behavior. Here are a few tries:

  type M = {

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

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

  }

  val l: M[Int] = List(1)

  //error: M does not take type parameters

  type M[A] = {

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

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

  }

  val l: M[Int] = List(1)

  //error: type mismatch;

  type M[A] = {

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

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

  }

  //error: recursive method map needs result type

  //error: recursive method flatMap needs result type

  type M[A] = {

    def flatMap[B](f: A => this.type): this.type

    def map[B](f: A => B): this.type

  }

  val l: M[Int] = List(1)

  //error: type mismatch;

This doesn't seem to be that complicated, but it's giving me a hard time. Could someone help me on that?

Thanks in advance.

--
Lucas B. Torri

[Kevin Wright]

Try this one on for size:

http://www.scala-lang.org/api/current/index.html#scala.collection.generic.FilterMonadic

--
Kevin Wright
mail: kevin....@scalatechnology.com
gtalk / msn : kev.lee...@gmail.com

quora: http://www.quora.com/Kevin-Wright

google+: http://gplus.to/thecoda

twitter: @thecoda

vibe / skype: kev.lee.wright

steam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Lucas Torri]

Hey Kevin,

thanks for the help.

Sounds like a possible solution, but that would obligate me to extend this trait in all the classes I need...

That's not good enough, since some existent classes (Option, for instance) doesn't implement it as well. 

--
Lucas B. Torri

[Kris Nuttycombe]

This is not something that it is possible to do directly. Instead, you can use a typeclass. The name of the typeclass you're interested in is Monad.

trait Monad[M[_]] {

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

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

  def map[A, B](m: M[A], f: A => B): M[B] = flatMap(m, (a: A) => point(f(a)))

}

case class Monadic[M[_]: Monad, A](m: M[A]) {

  def flatMap[B](f: A => M[B]): M[B] = implicitly[Monad[M]].flatMap(m, f)

  def map[B](f: A => B): M[B] = implicitly[Monad[M]].map(m, f)

}

object Monadic {

  implicit def m2monadic[M[_]: Monad, A](m: M[A]) = Monadic[M, A](m)

[Kris Nuttycombe]

Oh, and of course, all of this (well, not sure about Monadic) is available in scalaz.

[Josh Suereth]

So here's a secret of Scala's for-expressions and the collections:

Map does not need to have the signature:  def map[A,B](f: A => B): M[B]

In fact, the map/flatMap methods across the standard library have differing signatures (implicits making the difference).  As Kevin suggests, using a type-class is a much better approach here.

Note:  You can perform all sorts of evil by simply utilizing the rewrite of for-expressions.  Look at this odd code:

scala> class Foo { def map[B](f: String => B) = f("Foo") }

defined class Foo

scala> class Bar { def flatMap[B](f: Foo => B) = f(new Foo) }

defined class Bar

scala> for(x <- new Bar; b <- x) yield "HI " + b

res2: java.lang.String = HI Foo

[Lucas Torri]

Well, let me explain a little better why I "need" this... I was taking this monads exercise on Tony's blog (http://blog.tmorris.net/understanding-monads-using-scala-part-1/)

I found the solution for problems 1 and 2, and in the end the implementation for sequenceOption and sequenceInter was identical. Both would look like this:

def sequenceOption[A](x: List[Option[A]]): Option[List[A]] =

    x.foldRight(unitalOption(List[A]())) ((e, lo) => lo flatMap(l => e map (_ :: l)))

Then, the third exercise was about removing that duplication. I thought about creating a third method, that would receive both the List (x) and the unital function (unitalOption or unitalInter).

The problem here is that both Option and Inter classes have the map and flatMap methods, but don't have a common super type.

After Kris reply, I started to do this:

  trait Monad[M[_]] {

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

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

    def map[A, B](m: M[A], f: A => B): M[B] = flatMap(m, (a: A) => point(f(a)))

  }

  case class Monadic[M[_]: Monad, A](m: M[A]) {

    def flatMap[B](f: A => M[B]): M[B] = implicitly[Monad[M]].flatMap(m, f)

    def map[B](f: A => B): M[B] = implicitly[Monad[M]].map(m, f)

  }

  object Monadic {

    implicit def m2monadic[M[_]: Monad, A](m: M[A]) = Monadic[M, A](m)

  }

  

  object OptionMonad extends Monad[Option] {

    def point[A](a: A): Option[A] = unitalOption(a)

    def flatMap[A, B](m: Option[A], f: A => Option[B]): Option[B] = m.flatMap(f)

  }

  

  object InterMonad extends Monad[Inter] {

    def point[A](a: A): Inter[A] = unitalInter(a)

    def flatMap[A, B](m: Inter[A], f: A => Inter[B]): Inter[B] = m.flatMap(f)

  }

I'm not completely sure if that's the correct path, though

[Lucas Torri]

forgot to add that the objects that I created are implicit (implicit object ...)

--
Lucas B. Torri

[Josh Suereth]

Yes, this is a great way to solve the problem.   You now know the "type class pattern" in Scala :)

[Lucas Torri]

I tried to create this method signature to the third method I talked about:

  def sequence[A, O[A] <% Monadic[O, A]](x: List[O[A]], f: List[A] => O[List[A]]): O[List[A]] = ...

but got this error:

  error: type O takes type parameters

Looks like <% doesn't work with types that have type parameters, does it?

--
Lucas B. Torri

[Razvan Cojocaru]

Here’s some of my early attempts of unifying everything but not using typeclasses (i.e. doing this the conventional OO way): https://github.com/razie/razbase/blob/master/base/src/main/scala/razie/M.scala

 

There’s quite a bit of code duplication there… I still use it occasionally ‘cause I’m lazy and the name’s short J

[Andreas Scheinert]

Hi!
I can't check right now but does it work wig an underscore:def
sequence[A, O[_] <%
?
Regards Andreas

On 14 Sep., 22:48, Lucas Torri <lucasto...@gmail.com> wrote:
> I tried to create this method signature to the third method I talked about:
>
>   def sequence[A, O[A] <% Monadic[O, A]](x: List[O[A]], f: List[A] =>
> O[List[A]]): O[List[A]] = ...
>
> but got this error:
>
>   error: type O takes type parameters
>
> Looks like <% doesn't work with types that have type parameters, does it?
>

> On Wed, Sep 14, 2011 at 5:31 PM, Josh Suereth <joshua.suer...@gmail.com>wrote:
>
>
>
>
>
> > Yes, this is a great way to solve the problem.   You now know the "type
> > class pattern" in Scala :)
>

[Tony Morris]

def sequence[A, F[_]: Monad](x: List[F[A]]): F[List[A]]

--
Tony Morris
http://tmorris.net/

[Razvan Cojocaru]

Do you know of a good online description of this “type class pattern” ?

 

From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On Behalf Of Josh Suereth
Sent: September-14-11 4:31 PM
To: Lucas Torri
Cc: scala-user
Subject: Re: [scala-user] defining a type for a class with map/flatMap

 

Yes, this is a great way to solve the problem.   You now know the "type class pattern" in Scala :)

[Kevin Wright]

Somebody had to do it :)

http://lmgtfy.com/?q=scala+type+class

[Norbert Tausch]

There is a good description within the paper: Type Classes as Objects and Implicits by Oliveira, Moors and Odersky

Best regards

Norbert Tausch

[Andreas Scheinert]

And you said type classes are no 'advanced' topic :) Well while the technical outline is nit that hard it implies quite a different design approach. In that sense it's 'still' advanced for my perception. And I would guess it would still take a while for all scala libs out there to take advantage of that.

Regards Andreas

[Kevin Wright]

They're not complicated at all.  Here's a trivial example: https://gist.github.com/937142

[Lucas Torri]

almost there (I think :)

  def sequence[A, O[_] : Monad](x: List[O[A]], f: List[A] => O[List[A]]): O[List[A]] =

    x.foldRight(f(List[A]())) { (i, il) =>

      il flatMap { l =>

        i map (_ :: l)

      }

    }

but gave me this error:

<console>:23: error: type mismatch;

 found   : il.type (with underlying type O[List[A]])

 required: ?{val flatMap: ?}

Note that implicit conversions are not applicable because they are ambiguous:

 both method unitalOption in object Unitals of type [A](a: A)Option[A]

 and method unitalInter in object Unitals of type [A](a: A)Inter[A]

 are possible conversion functions from il.type to ?{val flatMap: ?}

             il flatMap { l =>

             ^

By the way, what the colon means in "O[_] : Monad"?

--
Lucas B. Torri

[Razvan Cojocaru]

It’s a context bound.

 

Read this – it’s a great introduction to using type classes in this manner: http://debasishg.blogspot.com/2010/06/scala-implicits-type-classes-here-i.html

 

 

From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On Behalf Of Lucas Torri
Sent: September-15-11 9:56 AM
To: tmo...@tmorris.net
Cc: scala...@googlegroups.com
Subject: Re: [scala-user] defining a type for a class with map/flatMap

 

almost there (I think :)

[Josh Suereth]

I cover them pretty well in the book "Scala In Depth".  Chapter 7: Implicits and Types.

[Josh Suereth]

Also, here's another article (shameless plug): http://suereth.blogspot.com/2010/07/monkey-patching-duck-typing-and-type.html

[Razvan Cojocaru]

Wow – there’s a huge difference in what bing returns for the “type class pattern” (which I used lazily from Outlook) and google does. Needless to say the google results are actually useful J

[Andreas Scheinert]

I didn't say complicated. And I also said that the actual encoding isn't difficult neither. It's more about how your design process is influenced.

Regards Andreas

[Kris Nuttycombe]

Your def below gets desugared to this:

def sequence[A, O[_]](x: List[O[A]], f: List[A] => O[List[A]])(implicit ev: Monad[O]): O[List[A]]

Now, instead of using il.flatMap(...) use ev.flatMap(il, ...)

The "implicit typeclass" pattern could also be called "implicit strategy"  - it's just like the traditional OO "strategy" pattern (which is really just a way of encoding functions in OO) but where the strategy to use is solely determined by type and scope. You can always pass it explicitly.

Kris

[Lucas Torri]

\o/ 

it's working :D

I do feel kind of embarrassed, though. I was testing it in REPL and took a while to figure out that the a problem I was having was because of a companion object (needed to interpret the class and object together using the :paste mode) :(

Just for the record, here is what I got: https://gist.github.com/1219737

Is there any room for improvement? I was thinking that I could put unitalOption/unitalInter as implicit functions and let the compiler insert them to me... I'll give a try in a few moments.

--
Lucas B. Torri

[Tony Morris]

Woot! Now remove the List part.

def sequence[F[_]: Traverse, G[_]: Monad, A](x: F[G[A]]): G[F[A]]

Goigle for "THE Essence out the Iterator Pattern." This is a great paper, and there is also an excellent article using scala.

PS: You can replace Monad with Applicative above to get the most general function.

[Martin S. Weber]

On 09/15/11 17:22, Tony Morris wrote:
> Woot! Now remove the List part.
>
> def sequence[F[_]: Traverse, G[_]: Monad, A](x: F[G[A]]): G[F[A]]
>
> Goigle for "THE Essence out the Iterator Pattern." This is a great
> paper, and there is also an excellent article using scala.
>
> PS: You can replace Monad with Applicative above to get the most general
> function.

...which should be readily available in the standard scala library type stack
without implicit monkey patching galore. I'll never understand why this
"pimping" as an argument pro scala. After all the fact that you have to do it
to generically express some algorithms clearly states: fix the language, not:
introduce implicit hell that there's no tool support for (scaladoc??) to fix
it on-the-fly.

Oh well.

-Martin

[Kris Nuttycombe]

I don't think you'll get any argument from Tony that the Monad, Applicative, and Traverse typeclasses should be in the standard library. But if you were paying attention, you might realize that implicits are in fact the *only* way to implement this pattern without completely changing the semantics of the scala language.

Have you actually understood what sequence does, before you start making comments?

Kris

[Lucas Torri]

Traverse is part of scalaz, isn't it?

--
Lucas B. Torri

[Kris Nuttycombe]

Yes, all of these typeclasses are in Scalaz. But I find it much more helpful to write them yourself before you start using the prebuilt versions.

In fact, if you want to ensure that you've really understood monads, fix this code starting from a blank screen (and not peeking at your previous solution)

class Reader[I] extends Monad[({type M[O] = Function1[I, O]})#M] {
  def point[A](a: A): Function1[I, A] = error("todo")
  def flatMap[A, B](m: Function1[I, A], f: A => Function1[I, B]): Function1[I, B] = error("todo") 
}

[Lucas Torri]

what does 

#M

^ 

means?

--
Lucas B. Torri

[Martin S. Weber]

On 09/15/11 17:33, Kris Nuttycombe wrote:
> (...) [Y]ou might realize that implicits are

> in fact the *only* way to implement this pattern without completely
> changing the semantics of the scala language.

Interesting. I'd expect that for any types X, Y where you can map implicitly
from X to Y to gain access to an operation Y.op (as Y's only relevant
operation) implemented by means of X, you can derive X from Y, implementing
op's interface as published by Y in X by means of X.

Now you might say, well, if there is a set of (type)classes that are useful
and usually used in the wild, wild world out there, and there exists a
function canImplement: ScalaClass -> CommonlyUsedTypeClass -> boolean,
then for each SC, for each CUTC, where canImplement SC, CUTC == true, you can
SC < CUTC instead of implicit SC -> CUTC. The existence of FilterMonadic
reinforces that point of view.

No change in the semantics of the *language* necessary.

I don't see a requirement for typeclasses operating outside the type hierarchy
and would appreciate pointers to its necessity instead of insults, thank you
very much.

Regards,
-Martin

[Kris Nuttycombe]

So, what the #M means is "the type member M of the type to the left of the #"

In this case, ({type M[O] = Function1[I, O]}) is an anonymous type that has a type member named M that is a type *constructor* of one argument. In general, the # syntax is used to denote a path-dependent type; for example, in the class below: 

class A {

  class B

  def b: B = new B

}

You would refer to an arbitrary instance of b as:

val ab: A#B = (new A).b

In ({type M[O] = Function1[I, O]}) this gets a little more interesting: in Monad[M[_]] you'll see that M is a type constructor of one argument. But Function1 is a type constructor of two arguments; if we want a monad for Function1, how do we get this? The answer is the "type lambda" you see in here. We get a type constructor of one argument, M[O] by *partially applying* the type constructor Function1 to a the type I, which is fixed to the type denoted by the parameter I in Reader[I].

This is a good time to introduce the notion of "kinds" Kinds are to types what types are to values; here are some examples:

type String has kind *

type List has kind * -> *; that is, List is not a type, because in List[X] X is a type argument. So List is a function from a type (A) to a type (List[A])

type List[String] has kind *, because now the type variable in the List type constructor is fixed to a type.

type Monad[M[_]] has kind (* -> *) -> *. That is, you must give Monad a type constructor of one argument (such as List) to get a type.

So, in the type lambda above, you're partially applying the type constructor Function1, which has kind * -> * -> * to the type I, giving a type constructor of kind (* -> *) ... which is exactly what you need for a Monad! 

Kris

[Josh Suereth]

Foo.Bar where Bar is a type and Foo is a value (package/object) is shorthand for Foo.type#Bar

({type X = ....})#X  is a clever trick Jason Zaugg discovered to create anonymous types.   It's called a 'type lambda'.  You construct the anonymous type in a ({}) block and then reference it using #.    In the above case, you have a type with two parameters and the Monad interface requires a type with only one, so you need to lock yourself down to one parameter.

hence: class Reader[I] extends Monad[({type M[O] = Function1[I, O]})#M]

this locks down I in "Function[I,O]" so that the monad is declared against the type Function[I,_].   However, _ serves two purposes: existentials and placeholders.   Needless to say, this makes it unavailable for type-lambdas, leading the the above trick.

- Josh

[Daniel Sobral]

On Thu, Sep 15, 2011 at 18:57, Martin S. Weber <martin...@nist.gov> wrote:
> On 09/15/11 17:33, Kris Nuttycombe wrote:
>>
>> (...) [Y]ou might realize that implicits are
>> in fact the *only* way to implement this pattern without completely
>> changing the semantics of the scala language.
>
> Interesting. I'd expect that for any types X, Y where you can map implicitly
> from X to Y to gain access to an operation Y.op (as Y's only relevant
> operation) implemented by means of X, you can derive X from Y, implementing
> op's interface as published by Y in X by means of X.

That sounds reasonable, but only because you haven't been exposed to
anything else.

Let's consider something very, very simple. Let's go to "Int", and see
if we can do it.

Ignoring the fact that Int is finite for an instant, Int is a Monoid,
so we could have something like this:

class Int extends Monoid

So far, so good. Now, Int is also a Ring, meaning it is a Monoid in
two different ways. But that doesn't make much sense... how can it be
something in two different ways? Perhaps it might be better to say it
"has" a Monoid, but that doesn't make much sense either. And Int is
just an Int, it doesn't have components.

To solve this, we have to extend Monoid to take some parameters, so
that you can inherit it twice. I'll adopt here a feature from some
other language that permits multiple inheritance, but that handles
member conflict in a distinct manner. I'll rename Monoid's methods.

class Int extends Monoid[unit => 0, dot => +] with Monoid[unit => 1, dot => *]

Now we are fine again and can declare the Ring, but I'll pass on that
exercise and get back to the fact that Int is finite.

Int is finite, which means it doesn't _really_ follow the Monoid laws
-- for the implementation above. On the other hand, one can define Int
Monoids under module. That will require Monoid to receive parameters
-- parameters that may be only known at run time!

To get it right, then, we need to be able to treat Int as a Monoid in
an arbitrary number of ways, we need to select the methods that will
implement it, and we need to accept arguments at run-time to
parameterize our monoids. Type classes can do it, type inheritance
cannot.

>
> Now you might say, well, if there is a set of (type)classes that are useful
> and usually used in the wild, wild world out there, and there exists a
> function canImplement: ScalaClass -> CommonlyUsedTypeClass -> boolean,
> then for each SC, for each CUTC, where canImplement SC, CUTC == true, you
> can SC < CUTC instead of implicit SC -> CUTC. The existence of FilterMonadic
> reinforces that point of view.
>
> No change in the semantics of the *language* necessary.
>
> I don't see a requirement for typeclasses operating outside the type
> hierarchy and would appreciate pointers to its necessity instead of insults,
> thank you very much.
>
> Regards,
> -Martin
>

--
Daniel C. Sobral

I travel to the future all the time.

[Razvan Cojocaru]

contrasting OO inheritance vs type classes here - see the articles linked
there

http://wiki.coolscala.com/scala-patterns#toc0

-----Original Message-----
From: scala...@googlegroups.com [mailto:scala...@googlegroups.com] On
Behalf Of Martin S. Weber
Sent: September-15-11 5:57 PM
To: scala...@googlegroups.com
Subject: Re: [scala-user] defining a type for a class with map/flatMap

[Tony Morris]

On 09/16/2011 09:34 AM, Daniel Sobral wrote:

Do you remember UML diagrams? If B inherited from A, then there would be
an upward-pointing arrow from B to A. Now turn your head 90 degrees
anti-clockwise. There is a right-pointing arrow from B to A. This is a
regular function or "implication." Scala uses => or Function1 to denote
this e.g.

def k: B => A

Now make that function implicit and guarantee no side-effects (by
promised convention as in Scala or by enforcement as in inheritance).

Type-classes are just tilting your head 90 degrees. This is not to
undermine the far-reaching implications of tilting your head though.

[Daniel Sobral]

Actually, forget all that. I was watching
http://skillsmatter.com/podcast/home/practical-scalaz-2518/js-2679 and
saw an even better example.

With Scalaz, Option[A] is a Monoid _if_ A is a Monoid. How do you
express that with inheritance?

[Martin S. Weber]

Was: defining a type for a class with map/flatMap

Thanks for the replies, guys, you definitely got me thinking. I also can agree
with some of what you said, but I'm not fully convinced yet (not that you have
to care about that :)). I'll detail more below. I'm replying to three mails
here, one of tony morris and two of daniel sobral.

Finally, before we get started, this is not a campaign to introduce something
into the scala standard library. Instead I have a concern about out-of-the-box
usability of composable concepts available (or not) in the stdlib, whose
reason I cannot grasp.

Let's begin with Daniel:

On 09/15/11 19:34, Daniel Sobral wrote:

> Let's consider something very, very simple. Let's go to "Int", and see
> if we can do it.
>
> Ignoring the fact that Int is finite for an instant, Int is a Monoid,
> so we could have something like this:

I value the attempt, but Imho you should've taken something else than "Int is
a Monoid". Int is not a monoid. ({The set of all Integers}, +, 0) form a
monoid. ({The set of all Integers}, *, 1) form a monoid. Int on its own is not
a monoid. A monoid is a three-tuple and a couple of axioms. Int is, at best,
the first member of the triple. Now you might say, I'm extra picky here, but
this changes the way that things are, should be or have to be modeled to
capture the concept.

> So far, so good. Now, Int is also a Ring, meaning it is a Monoid in
> two different ways. But that doesn't make much sense... how can it be
> something in two different ways? Perhaps it might be better to say it
> "has" a Monoid, but that doesn't make much sense either. And Int is
> just an Int, it doesn't have components.

Ring : Monoid, Semigroup, axioms, but that's beside the point. Again, the
important part here is that "A Ring is a Monoid in two different ways" is
wrong. In other words, Int DOES "have" a monoid (well, not only one) WITH an
operation AND an identity. This is no concept that should be modeled INSIDE
Int at all IMHO. So that being said, derivation clearly drops out of the
picture. An Int Is Not A Monoid, thus Int </ Monoid . You can have MonoidOps
for which there is a (Int, +, 0) < MonoidOps (sadly we cannot inherit from
tuples, but a case class will do). It's natural that you fail to properly
capture the concept of monoid, ring etc. with int, because imho it's the wrong
modeling approach.

As all this monoid business can be confusing, I'll rather focus on a typeclass
T with a (for clarity) single method x[A, B] : A => B.

Daniel a bit lateron:

On 09/15/11 22:01, Daniel Sobral wrote:
> Actually, forget all that. I was watching
> http://skillsmatter.com/podcast/home/practical-scalaz-2518/js-2679 and
> saw an even better example.
>
> With Scalaz, Option[A] is a Monoid _if_ A is a Monoid. How do you
> express that with inheritance?

Again, please don't get me wrong. I may sound uberpicky here (sigh). I get
what you're saying. That is one of the reasons why I preferred the old-school
way of referring to implicits as the SLR has done for quite a while: calling
them "views". But again, the statement "An Option Is a Monoid" is wrong. Let's
look at our typeclass T with it's nifty x method:

What you're saying here is: "You can call method x on Option[A] _if_ A has
method x available, i.e., if A _is_ a T".

a) the latter part is what usually is the accepted vocabulary to express that
A derives from T.

b) Yes, we cannot express that with derivation!

c) Option[_]'s callable methods shouldn't be dependent on its type parameter
really. I can see how it comes handy in folding and collecting, but uh...
that's even a worse case of monkey patching because it's not static. If you
have a List[X], and it has a single element, would you expect to be able to
call X's methods on the List[_] ? Thought so.

d) Now if Option WERE a Monad (derived from), you could of course say,
"flatMap that shit!". You could not only -- to access method x of its embedded
instance (typed A, deriving from T), you really should be doing that.
Especially (!) if T's expecting to be wrapped up in a monad anyways. Then go
ahead and compose them ... Anyways, this makes (A < T).x available to users of
Option[A]. Why do you have to rape Option[A]'s interface for that?

Tony:

On 09/15/11 19:46, Tony Morris wrote:
> Do you remember UML diagrams? If B inherited from A, then there would be
> an upward-pointing arrow from B to A. Now turn your head 90 degrees
> anti-clockwise. There is a right-pointing arrow from B to A. This is a
> regular function or "implication." Scala uses => or Function1 to denote
> this e.g.
>
> def k: B => A

That's a smart one, especially as it's also a logical implication :) And it
conicides well with the term "view" that used to be in place for "implicits".
You can view a B as an A. There's a subtle difference though, to treat a B as
an A, you need k. If you turn your head back to upright (or, alternatively,
look at k and turn your head clock-wise 90 degrees), the world changes,
because k is already statically expressed. Which also means that you no longer
need a couple of k_n's in your toolbox to "view" B as A (R,U,S,H,...YYZ).

Also, all of A's methods are available in B without any impact. Tools know how
to support it (look at scaladoc and go find the methods of something's
superclasses. Now look again and find the methods that it can gain via
views/implicits) [I'm aware that's not a good argument per se. Tools, as some
humans, can, potentially eventually learn something. It seems though that it's
taking way longer for the available tools than for the humans to pick up the
concept].

So the benefit (and curse!) of k is: It's not premeditated. You can write it
yourself. Well, you also have to write it yourself. That might come in handy
if you want to change the view on A, but come as a nuisance if you really
don't want to change the view. You want a "B of A". More importantly, you
might want a "C of B of A" - but implicits aren't transitive. Derivation is.

And last, but not least, you want to use a library without writing the
boilerplate code yourself. After all, abstraction is about reusability. If, to
reuse, you have to repeat yourself, something in the conceptual model is quite
off IMHO. ...which is why I don't understand why some of the CUTC classes
aren't thrown into the Stdlib type stack, right where they belong.

Thanks for the replies, and thanks for the link, Razvan!

Regards,
-Martin

[Daniel Sobral]

On Fri, Sep 16, 2011 at 18:59, Martin S. Weber <martin...@nist.gov> wrote:
>
> Let's begin with Daniel:
>

> I value the attempt, but Imho you should've taken something else than "Int
> is a Monoid". Int is not a monoid. ({The set of all Integers}, +, 0) form a
> monoid. ({The set of all Integers}, *, 1) form a monoid. Int on its own is
> not a monoid. A monoid is a three-tuple and a couple of axioms. Int is, at
> best, the first member of the triple. Now you might say, I'm extra picky
> here, but this changes the way that things are, should be or have to be
> modeled to capture the concept.

An interface is a set of operations -- of varying arities -- over a
set of objects. In an OO environment, one of these objects -- the
first one -- is "special". In fact, *all* operations in a pure OO
language are methods defined over a set of objects through classes
that implement interfaces -- though terminology may vary.

So ({The set of all Integers}, +) certainly qualifies as an interface.
In, fact, it is an interface almost by definition, but there's still
the "0" missing. Alas, most OO languages offer class methods in one
way or another -- Scala through companion objects, Java as statics,
Smalltalk on class objects, etc. Keeping with Java ("interface" is a
Java concept), one _can_ have "zero" as a static, completing ({The set
of all Intergers}, +, zero).

So, while "integers" are numbers, "Int", the class, fits the bill. Int
is not "The set of all Integers". Int is "The set of all Integers"
*plus* operations.

So, while I'll certainly grant you pickyness, I'll be picky too and
demand you recognize that "Int", the class, is *not* just the first
member of the triple.

> Again, please don't get me wrong. I may sound uberpicky here (sigh). I get

> what you're saying. That is one of the reasons why I preferred the
> old-school way of referring to implicits as the SLR has done for quite a
> while: calling them "views". But again, the statement "An Option Is a
> Monoid" is wrong. Let's look at our typeclass T with it's nifty x method:
>
> What you're saying here is: "You can call method x on Option[A] _if_ A has
> method x available, i.e., if A _is_ a T".
>
> a) the latter part is what usually is the accepted vocabulary to express
> that A derives from T.
>
> b) Yes, we cannot express that with derivation!
>
> c) Option[_]'s callable methods shouldn't be dependent on its type parameter
> really. I can see how it comes handy in folding and collecting, but uh...
> that's even a worse case of monkey patching because it's not static. If you
> have a List[X], and it has a single element, would you expect to be able to
> call X's methods on the List[_] ? Thought so.

It is static. It is resolved at compile time.

I don't understand what you mean with List[X], but, yes, there are
certain methods on X that I do wish to call on List[X].

> d) Now if Option WERE a Monad (derived from), you could of course say,
> "flatMap that shit!". You could not only -- to access method x of its
> embedded instance (typed A, deriving from T), you really should be doing
> that. Especially (!) if T's expecting to be wrapped up in a monad anyways.
> Then go ahead and compose them ... Anyways, this makes (A < T).x available
> to users of Option[A]. Why do you have to rape Option[A]'s interface for
> that?

Monoid != Monad.

You miss the point completely. Let's go back to the monoid definition:
(set of objects, associative binary operation, identity under
operation). If A implements a monoid, then there is an associative
binary operation and an identity under that operation, over the whole
set of objects of type Option[A]. The question is not whether
Option[A] implements the monad -- it does. The question is just how we
abstract away the implementation into an usable interface.

[Tony Morris]

Ease up fella. All monads are monoids. The associative and identity laws common to both is not a coincidence.

However, this discussion started around flatMap+map, which as you might note, is not quite a monad. Specifically, it is missing the identity operation, aka unit.

Small excursion follows.

What do we call monoids that are absent identity? Exactly, semigroups. I draw attention to the thread where I plead for the splitting of monoid into semigroup, with emphasis on the fact that scala even has built in syntax for this structure and its distinction to monoids, with for-comprehensions that run on any semigroup(oid), which is not necessarily a monoid. I could episode this importance all day, but instead, let's just agree to not repeat haskell's mistakes here, given we have the benefit of hindsight.

[Tony Morris]

And by episode my spell checker meant emphasise.

[Kevin Wright]

On 17 September 2011 01:24, Tony Morris <tmo...@tmorris.net> wrote:

Ease up fella. All monads are monoids.

... in the category of endofunctors :)

http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html

[Martin S. Weber]

On 09/16/11 19:01, Daniel Sobral wrote:
> On Fri, Sep 16, 2011 at 18:59, Martin S. Weber<martin...@nist.gov> wrote:
>>
>> Let's begin with Daniel:
>>
>> I value the attempt, but Imho you should've taken something else than "Int
>> is a Monoid". Int is not a monoid. ({The set of all Integers}, +, 0) form a
>> monoid. ({The set of all Integers}, *, 1) form a monoid. Int on its own is
>> not a monoid. A monoid is a three-tuple and a couple of axioms. Int is, at
>> best, the first member of the triple. Now you might say, I'm extra picky
>> here, but this changes the way that things are, should be or have to be
>> modeled to capture the concept.
>
> An interface is a set of operations -- of varying arities -- over a
> set of objects. In an OO environment, one of these objects -- the
> first one -- is "special".

To quote yourself: "That sounds reasonable, but only because you haven't been
exposed to anything else." (else = CLOS/generic methods in case you wonder).

> So ({The set of all Integers}, +) certainly qualifies as an interface.

I agree.

> In, fact, it is an interface almost by definition, but there's still
> the "0" missing. Alas, most OO languages offer class methods in one
> way or another -- Scala through companion objects, Java as statics,
> Smalltalk on class objects, etc. Keeping with Java ("interface" is a
> Java concept), one _can_ have "zero" as a static, completing ({The set
> of all Intergers}, +, zero).

Yes, and you can have many zeros. The point is that Int has many binary
operations with an identity satisfying the monoid requirements. You thus have
to identify the triple: Int (implicitly as this is our "special, first"
object), + (or any other binary method you want to take) and the accompanying
identity (0 in that case). Again, (Int, +, 0) != (Int, *, 1) != (Int,
addition-in-a-modulo-field, 0) != .... != Int. Which is why I said I wanted to
keep Monoid out of the equation. Hope that wish now makes sense to you. If you
keep saying, Int IS a monoid, I'll only answer with the question: "which?". If
you can, with no further pointers, code or something else answer that
question, I'll accept your answer. Point is (see above), you won't. So please,
let's keep monoid out of it, eh?

>
> So, while "integers" are numbers, "Int", the class, fits the bill. Int
> is not "The set of all Integers". Int is "The set of all Integers"
> *plus* operations.
>
> So, while I'll certainly grant you pickyness, I'll be picky too and
> demand you recognize that "Int", the class, is *not* just the first
> member of the triple.

Yeah, it has many more members that satisfy for the 2nd and 3rd position, too.
You only have to identify them. Which is, btw, a good point for the implicits
/ call-site influence of implicits, because that's exactly what you doing.
But, all it does (in the case of Monoid!) is fixing a broken (imho, see above)
design by requiring call-site fixup.

>> c) Option[_]'s callable methods shouldn't be dependent on its type parameter
>> really. I can see how it comes handy in folding and collecting, but uh...
>> that's even a worse case of monkey patching because it's not static. If you
>> have a List[X], and it has a single element, would you expect to be able to
>> call X's methods on the List[_] ? Thought so.
>
> It is static. It is resolved at compile time.

Yeah and its interface depends on its type-parameter. Not exactly static.
Maybe statically typed, but definitely not static.

>
> I don't understand what you mean with List[X], but, yes, there are
> certain methods on X that I do wish to call on List[X].
>
>> d) Now if Option WERE a Monad (derived from), you could of course say,
>> "flatMap that shit!". You could not only -- to access method x of its
>> embedded instance (typed A, deriving from T), you really should be doing
>> that. Especially (!) if T's expecting to be wrapped up in a monad anyways.
>> Then go ahead and compose them ... Anyways, this makes (A< T).x available
>> to users of Option[A]. Why do you have to rape Option[A]'s interface for
>> that?
>
> Monoid != Monad.

Exactly (save for tony's remarks, as it's SO obvious that something in a
category will always be a monoid, given you have identity, composition and
arrows readily available). And as I've gone to some pains to detail, I did NOT
want to talk about Monoid. So read d) again please, this time assuming the
first sentence indeed means Monad.

> You miss the point completely. Let's go back to the monoid definition:
> (set of objects, associative binary operation, identity under
> operation). If A implements a monoid, then there is an associative
> binary operation and an identity under that operation, over the whole
> set of objects of type Option[A].

It shouldn't. Option[A] != A. Again. You tweak an interface unnecessarily.
Option[A] supports passing a computation inside itself. You don't need to rape
Option's interface.

> The question is not whether
> Option[A] implements the monad -- it does.

Yeah, so there definitely should be a Monad appearing in its superclasses.

> The question is just how we
> abstract away the implementation into an usable interface.

Sorry, I cannot make any sense out of this sentence.

Anyways, Option[A]'s taking over of some of A's methods is extremely ugly IMHO
but completely besides the point. My point is (and was all the time) that we
do have a way to compose functionality while also giving it a name:
derivation. We have a system to avoid repeating yourself: libraries. There's
ample use of derivation in the library itself. And there's a lot of users who
keep painting the same anonymous arrows between one concept that is heavily
used by a library (some of scalaz's "type"classes) and another concept that is
heavily used by a library (some of scala's stdlib's classes). In other words,
the users repeat themselves and they cannot express the relationship (this IS
that) with the native, transitive way the language supports for that (this
extends that). I'm still to see a good argument for the exclusion of some
common typeclasses from the scala standard library.

Regards,
-Martin