This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Applicative functors as views vs. containers style

6 replies
marius
Joined: 2008-08-31,
User offline. Last seen 3 years 19 weeks ago.
Hi,

I was talking not so long ago with Greg Meredith about monads and I definitely like the idea that Monads are views over content and do not actually hold the content of their own. With this in mind list, option etc. are not actually monads although a lot of folks would argue that because they do obey monad laws.

For applicative functor we have the same situation in terms on how we actually view them:

Form 1 - Applicative is basically a view

trait Functor[F[_]] {
  def unit[A](a: A): F[A]
  def fmap[A, B](f: A => B): F[A] => F[B]
}


trait Applicative[F[_]] extends Functor[F] {
  def <*>[A, B](f: F[A => B]): F[A] => F[B]
}


object ApplicativeVal extends Applicative[Val] {

  def unit[A](a: A): Val[A] = new Val[A](a)

  def fmap[A, B](f: A => B): Val[A] => Val[B] = k => k.map(f)

  def <*>[A, B](f: Val[A => B]): Val[A] => Val[B] = k => for (x <- k; g <- f) yield g(x)

}


object Test extends App {

   val * : Int => Int => Int = a => b => a*b

   val a = Val(*)
   val a1 = Val(5)
   val b = Val(3)
  
   val s = (ApplicativeVal <*> (ApplicativeVal <*> a)(a1))(b)

   println(s)
}

The problem is the syntax highlighted above. We can simplify that adding:


object Val {
  implicit def val2Wrap[A](v : Val[A]): ValWrap[A] = new ValWrap(v)

  def apply[T](v: T) = new Val(v)
}

class ValWrap[T](v: Val[T]) {
  def <*>[B](a: Val[T => B]): Val[B] = (ApplicativeVal <*> a)(v)
}


val s = b <*> (a1 <*> a)

So we need some extra stuff to simplify syntax which may seem boilerplate.

Form 2- The containers are applicative


trait Functor2[F[_], T] { // I didn't find a good way to get rid of T type parameter in this representation
 
  def unit[B](b: B): F[B]

  def fmap[B](f: T => B): F[B]
}

trait Applicative2[F[_], T] extends Functor2[F, T] {

  def <*>[B](f: F[T => B]): F[B]
}

case class AppVal[A](val v: A)   extends Applicative2[AppVal, A] {
 
  def unit[B](b: B): AppVal[B] = new AppVal(b)

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

  def <*>[B](f: AppVal[A => B]): AppVal[B] = for (x <- this; g <- f) yield g(x)

  def map[B](f: A => B): AppVal[B] = unit(f(v))

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

  override def toString = v toString

}

and we can say:

  val a = AppVal(*)
  val a1 = AppVal(5)
  val b = AppVal(3)
  val s = b <*> (a1 <*> a)

At the first glance Form 2 looks more concise then Form 1 but still Form 1 seems to me more flexible to me.

Any thoughts, tips, recommendations ?

Thanks,
Marius
marius
Joined: 2008-08-31,
User offline. Last seen 3 years 19 weeks ago.
Re: Applicative functors as views vs. containers style
Oh Form 2 could be written (arguably more elegantly) as:

trait Functor2[T] {

  type F[X]
 
  def unit[B](b: B): F[B]

  def fmap[B](f: T => B): F[B]
}

trait Applicative2[T] extends Functor2[T] {

  def <*>[B](f: F[T => B]): F[B]
}


case class AppVal[A](val v: A) extends Applicative2[A]{
 
  type F[X] = AppVal[X]
 
  def unit[B](b: B): F[B] = new AppVal(b)

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

  def <*>[B](f: F[A => B]): F[B] = for (x <- this; g <- f) yield g(x)

  def map[B](f: A => B): F[B] = unit(f(v))

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

  override def toString = v toString

}


Marius

On Mon, Aug 8, 2011 at 1:34 PM, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
Hi,

I was talking not so long ago with Greg Meredith about monads and I definitely like the idea that Monads are views over content and do not actually hold the content of their own. With this in mind list, option etc. are not actually monads although a lot of folks would argue that because they do obey monad laws.

For applicative functor we have the same situation in terms on how we actually view them:

Form 1 - Applicative is basically a view

trait Functor[F[_]] {
  def unit[A](a: A): F[A]
  def fmap[A, B](f: A => B): F[A] => F[B]
}


trait Applicative[F[_]] extends Functor[F] {
  def <*>[A, B](f: F[A => B]): F[A] => F[B]
}


object ApplicativeVal extends Applicative[Val] {

  def unit[A](a: A): Val[A] = new Val[A](a)

  def fmap[A, B](f: A => B): Val[A] => Val[B] = k => k.map(f)

  def <*>[A, B](f: Val[A => B]): Val[A] => Val[B] = k => for (x <- k; g <- f) yield g(x)

}


object Test extends App {

   val * : Int => Int => Int = a => b => a*b

   val a = Val(*)
   val a1 = Val(5)
   val b = Val(3)
  
   val s = (ApplicativeVal <*> (ApplicativeVal <*> a)(a1))(b)

   println(s)
}

The problem is the syntax highlighted above. We can simplify that adding:


object Val {
  implicit def val2Wrap[A](v : Val[A]): ValWrap[A] = new ValWrap(v)

  def apply[T](v: T) = new Val(v)
}

class ValWrap[T](v: Val[T]) {
  def <*>[B](a: Val[T => B]): Val[B] = (ApplicativeVal <*> a)(v)
}


val s = b <*> (a1 <*> a)

So we need some extra stuff to simplify syntax which may seem boilerplate.

Form 2- The containers are applicative


trait Functor2[F[_], T] { // I didn't find a good way to get rid of T type parameter in this representation
 
  def unit[B](b: B): F[B]

  def fmap[B](f: T => B): F[B]
}

trait Applicative2[F[_], T] extends Functor2[F, T] {

  def <*>[B](f: F[T => B]): F[B]
}

case class AppVal[A](val v: A)   extends Applicative2[AppVal, A] {
 
  def unit[B](b: B): AppVal[B] = new AppVal(b)

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

  def <*>[B](f: AppVal[A => B]): AppVal[B] = for (x <- this; g <- f) yield g(x)

  def map[B](f: A => B): AppVal[B] = unit(f(v))

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

  override def toString = v toString

}

and we can say:

  val a = AppVal(*)
  val a1 = AppVal(5)
  val b = AppVal(3)
  val s = b <*> (a1 <*> a)

At the first glance Form 2 looks more concise then Form 1 but still Form 1 seems to me more flexible to me.

Any thoughts, tips, recommendations ?

Thanks,
Marius

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Applicative functors as views vs. containers style

On Mon, Aug 8, 2011 at 07:34, Marius Danciu wrote:
> Hi,
>
> I was talking not so long ago with Greg Meredith about monads and I
> definitely like the idea that Monads are views over content and do not
> actually hold the content of their own. With this in mind list, option etc.
> are not actually monads although a lot of folks would argue that because
> they do obey monad laws.

This seems to be mixing two concepts: monads as structures that abide
by certain laws, and monads as an API.

Something like a list is certainly a monad, and your concern seems to
be if it should implement the API directly, or through a third party.
The latter method, which you call "view", is known as the type class
pattern in Scala. This pattern has a strong following in the Scala
community due to some advantages over inheritance. For example:

* It does not require the classes to be designed with the API (ie, can
be "retrofitted" without changing the class).
* It can offer multiple implementations where they are available
(think monoid and Int, for instance, where (1, *) and (0, +) both
fit).
* It separate concerns.

Scalaz uses this pattern everywhere. In Scala itself, the distinction
can be seen in Ordered vs Ordering.

marius
Joined: 2008-08-31,
User offline. Last seen 3 years 19 weeks ago.
Re: Applicative functors as views vs. containers style
Daniel,

Thanks for your thoughts. Your highlights match with my initial intuition.

Thanks,
Marius

On Mon, Aug 8, 2011 at 3:39 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Mon, Aug 8, 2011 at 07:34, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi,
>
> I was talking not so long ago with Greg Meredith about monads and I
> definitely like the idea that Monads are views over content and do not
> actually hold the content of their own. With this in mind list, option etc.
> are not actually monads although a lot of folks would argue that because
> they do obey monad laws.

This seems to be mixing two concepts: monads as structures that abide
by certain laws, and monads as an API.

Something like a list is certainly a monad, and your concern seems to
be if it should implement the API directly, or through a third party.
The latter method, which you call "view", is known as the type class
pattern in Scala. This pattern has a strong following in the Scala
community due to some advantages over inheritance. For example:

* It does not require the classes to be designed with the API (ie, can
be "retrofitted" without changing the class).
* It can offer multiple implementations where they are available
(think monoid and Int, for instance, where (1, *) and (0, +) both
fit).
* It separate concerns.

Scalaz uses this pattern everywhere. In Scala itself, the distinction
can be seen in Ordered vs Ordering.

--
Daniel C. Sobral

I travel to the future all the time.

Meredith Gregory
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Applicative functors as views vs. containers style
Dear Daniel,
i appreciate your attempt to clarify Marius question. i think his question comes from an interesting and valid view point. Unfortunately, the languages computer science, mathematics and logic is not uniform nor uniformly spoken. When i am using the word views and API i am attempting to point at something behind the idea of typeclass. As i'm sure we both know, computational phenomena -- like functors, natural transformations and monads -- did not begin with Haskell, nor are they likely to end with it. ;-)
Monads, aka triples, are an algebraic theory. As a theory it has models. In mathematics, computer science and logic what is uniformly accepted is that it is just good hygiene to distinguish a theory from its models. Thus, we may say that List is a model of the algebraic theory of monad. We may -- and many excellent mathematicians, computer scientists and logicians do -- abuse language and say that List is a monad. Yet, what is meant by those excellent folks is precisely that List is a model of the theory -- and not the theory. 
The idea of the Haskell typeclass was intended to capture this idea in a computational setting. The Haskell instance expression is intended to be (an approximation of) the proof of the conformance of some model to some algebraic theory. This is -- of course -- up to the limits of what may be expressed in typeclass and instance expressions -- which leave out things like functoriality, naturality and conherence conditions to stay within reasonable complexity limits. 
The value of the separation of model from theory in mathematics is that models may be
  • models of more than one theory
  • models of one theory in more than one way
This value gets transported to practical computing in much the same way and my C9 talk on Conway Games was to illustrate this point. It is crucial, however, that we understand the origin of things. At the risk of being a bore, let me reiterate: the typeclass pattern actually derives from a clear mathematical idea that separates theory and model and this separation has practical value for the working mathematician, computer scientist and logician. 
Organizing code along these time-honored practices has a corresponding value for the working programmer who is seeking to get more reuse from her code. Specifically, if she has a concrete structure (be it a data or a control structure) it may be 
  • an implementation of a trait (or an instance of a typeclass) in more than one way; or,
  • it may be an implementation of more than one trait (or an instance of more than one typeclass)
Seen from this perspective Marius asks a reasonable question. There is a broad class of type constructors that enjoy functoriality. Exposing this sort of thing would be of benefit. In fact, it's not done very well in Haskell, as many Haskellians (such as Dan Piponi of Neighborhood of Infinity fame) have noted.
Best wishes,
--greg

On Mon, Aug 8, 2011 at 5:39 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Mon, Aug 8, 2011 at 07:34, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi,
>
> I was talking not so long ago with Greg Meredith about monads and I
> definitely like the idea that Monads are views over content and do not
> actually hold the content of their own. With this in mind list, option etc.
> are not actually monads although a lot of folks would argue that because
> they do obey monad laws.

This seems to be mixing two concepts: monads as structures that abide
by certain laws, and monads as an API.

Something like a list is certainly a monad, and your concern seems to
be if it should implement the API directly, or through a third party.
The latter method, which you call "view", is known as the type class
pattern in Scala. This pattern has a strong following in the Scala
community due to some advantages over inheritance. For example:

* It does not require the classes to be designed with the API (ie, can
be "retrofitted" without changing the class).
* It can offer multiple implementations where they are available
(think monoid and Int, for instance, where (1, *) and (0, +) both
fit).
* It separate concerns.

Scalaz uses this pattern everywhere. In Scala itself, the distinction
can be seen in Ordered vs Ordering.

--
Daniel C. Sobral

I travel to the future all the time.



--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com
Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Applicative functors as views vs. containers style
Greg,

just to double-check ...

apart from separating theories from their models ...

[ and using the computer science vocabulary (not the mathematics or logic one) ]


do the different representations of a potential model of a theory
as a structure also not play any role here?

I mean, for example, that a set of type X can be represented
 - extentionally (by somehow enumerating its elements) or
 - intentionally (by somehow defining a criterium for its elements)
leading to different desirable properties of those structures, for example
 - extentionally defined sets are naturally covariant in X
 - intentionally defined sets are naturally contravariant in X


and, is what I just wrote not something you already wrote yourself
to this emailing list?

Luc

On Wed, Aug 10, 2011 at 7:08 AM, Meredith Gregory <lgreg [dot] meredith [at] gmail [dot] com> wrote:
Dear Daniel,
i appreciate your attempt to clarify Marius question. i think his question comes from an interesting and valid view point. Unfortunately, the languages computer science, mathematics and logic is not uniform nor uniformly spoken. When i am using the word views and API i am attempting to point at something behind the idea of typeclass. As i'm sure we both know, computational phenomena -- like functors, natural transformations and monads -- did not begin with Haskell, nor are they likely to end with it. ;-)
Monads, aka triples, are an algebraic theory. As a theory it has models. In mathematics, computer science and logic what is uniformly accepted is that it is just good hygiene to distinguish a theory from its models. Thus, we may say that List is a model of the algebraic theory of monad. We may -- and many excellent mathematicians, computer scientists and logicians do -- abuse language and say that List is a monad. Yet, what is meant by those excellent folks is precisely that List is a model of the theory -- and not the theory. 
The idea of the Haskell typeclass was intended to capture this idea in a computational setting. The Haskell instance expression is intended to be (an approximation of) the proof of the conformance of some model to some algebraic theory. This is -- of course -- up to the limits of what may be expressed in typeclass and instance expressions -- which leave out things like functoriality, naturality and conherence conditions to stay within reasonable complexity limits. 
The value of the separation of model from theory in mathematics is that models may be
  • models of more than one theory
  • models of one theory in more than one way
This value gets transported to practical computing in much the same way and my C9 talk on Conway Games was to illustrate this point. It is crucial, however, that we understand the origin of things. At the risk of being a bore, let me reiterate: the typeclass pattern actually derives from a clear mathematical idea that separates theory and model and this separation has practical value for the working mathematician, computer scientist and logician. 
Organizing code along these time-honored practices has a corresponding value for the working programmer who is seeking to get more reuse from her code. Specifically, if she has a concrete structure (be it a data or a control structure) it may be 
  • an implementation of a trait (or an instance of a typeclass) in more than one way; or,
  • it may be an implementation of more than one trait (or an instance of more than one typeclass)
Seen from this perspective Marius asks a reasonable question. There is a broad class of type constructors that enjoy functoriality. Exposing this sort of thing would be of benefit. In fact, it's not done very well in Haskell, as many Haskellians (such as Dan Piponi of Neighborhood of Infinity fame) have noted.
Best wishes,
--greg

On Mon, Aug 8, 2011 at 5:39 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Mon, Aug 8, 2011 at 07:34, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi,
>
> I was talking not so long ago with Greg Meredith about monads and I
> definitely like the idea that Monads are views over content and do not
> actually hold the content of their own. With this in mind list, option etc.
> are not actually monads although a lot of folks would argue that because
> they do obey monad laws.

This seems to be mixing two concepts: monads as structures that abide
by certain laws, and monads as an API.

Something like a list is certainly a monad, and your concern seems to
be if it should implement the API directly, or through a third party.
The latter method, which you call "view", is known as the type class
pattern in Scala. This pattern has a strong following in the Scala
community due to some advantages over inheritance. For example:

* It does not require the classes to be designed with the API (ie, can
be "retrofitted" without changing the class).
* It can offer multiple implementations where they are available
(think monoid and Int, for instance, where (1, *) and (0, +) both
fit).
* It separate concerns.

Scalaz uses this pattern everywhere. In Scala itself, the distinction
can be seen in Ordered vs Ordering.

--
Daniel C. Sobral

I travel to the future all the time.



--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Meredith Gregory
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Applicative functors as views vs. containers style
Dear Luc,
Just so! 
Best wishes,
--greg

On Wed, Aug 10, 2011 at 11:57 AM, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Greg,

just to double-check ...

apart from separating theories from their models ...

[ and using the computer science vocabulary (not the mathematics or logic one) ]


do the different representations of a potential model of a theory
as a structure also not play any role here?

I mean, for example, that a set of type X can be represented
 - extentionally (by somehow enumerating its elements) or
 - intentionally (by somehow defining a criterium for its elements)
leading to different desirable properties of those structures, for example
 - extentionally defined sets are naturally covariant in X
 - intentionally defined sets are naturally contravariant in X


and, is what I just wrote not something you already wrote yourself
to this emailing list?

Luc

On Wed, Aug 10, 2011 at 7:08 AM, Meredith Gregory <lgreg [dot] meredith [at] gmail [dot] com> wrote:
Dear Daniel,
i appreciate your attempt to clarify Marius question. i think his question comes from an interesting and valid view point. Unfortunately, the languages computer science, mathematics and logic is not uniform nor uniformly spoken. When i am using the word views and API i am attempting to point at something behind the idea of typeclass. As i'm sure we both know, computational phenomena -- like functors, natural transformations and monads -- did not begin with Haskell, nor are they likely to end with it. ;-)
Monads, aka triples, are an algebraic theory. As a theory it has models. In mathematics, computer science and logic what is uniformly accepted is that it is just good hygiene to distinguish a theory from its models. Thus, we may say that List is a model of the algebraic theory of monad. We may -- and many excellent mathematicians, computer scientists and logicians do -- abuse language and say that List is a monad. Yet, what is meant by those excellent folks is precisely that List is a model of the theory -- and not the theory. 
The idea of the Haskell typeclass was intended to capture this idea in a computational setting. The Haskell instance expression is intended to be (an approximation of) the proof of the conformance of some model to some algebraic theory. This is -- of course -- up to the limits of what may be expressed in typeclass and instance expressions -- which leave out things like functoriality, naturality and conherence conditions to stay within reasonable complexity limits. 
The value of the separation of model from theory in mathematics is that models may be
  • models of more than one theory
  • models of one theory in more than one way
This value gets transported to practical computing in much the same way and my C9 talk on Conway Games was to illustrate this point. It is crucial, however, that we understand the origin of things. At the risk of being a bore, let me reiterate: the typeclass pattern actually derives from a clear mathematical idea that separates theory and model and this separation has practical value for the working mathematician, computer scientist and logician. 
Organizing code along these time-honored practices has a corresponding value for the working programmer who is seeking to get more reuse from her code. Specifically, if she has a concrete structure (be it a data or a control structure) it may be 
  • an implementation of a trait (or an instance of a typeclass) in more than one way; or,
  • it may be an implementation of more than one trait (or an instance of more than one typeclass)
Seen from this perspective Marius asks a reasonable question. There is a broad class of type constructors that enjoy functoriality. Exposing this sort of thing would be of benefit. In fact, it's not done very well in Haskell, as many Haskellians (such as Dan Piponi of Neighborhood of Infinity fame) have noted.
Best wishes,
--greg

On Mon, Aug 8, 2011 at 5:39 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Mon, Aug 8, 2011 at 07:34, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi,
>
> I was talking not so long ago with Greg Meredith about monads and I
> definitely like the idea that Monads are views over content and do not
> actually hold the content of their own. With this in mind list, option etc.
> are not actually monads although a lot of folks would argue that because
> they do obey monad laws.

This seems to be mixing two concepts: monads as structures that abide
by certain laws, and monads as an API.

Something like a list is certainly a monad, and your concern seems to
be if it should implement the API directly, or through a third party.
The latter method, which you call "view", is known as the type class
pattern in Scala. This pattern has a strong following in the Scala
community due to some advantages over inheritance. For example:

* It does not require the classes to be designed with the API (ie, can
be "retrofitted" without changing the class).
* It can offer multiple implementations where they are available
(think monoid and Int, for instance, where (1, *) and (0, +) both
fit).
* It separate concerns.

Scalaz uses this pattern everywhere. In Scala itself, the distinction
can be seen in Ordered vs Ordering.

--
Daniel C. Sobral

I travel to the future all the time.



--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland