Applicative functors as views vs. containers style

[Marius Danciu]

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 Danciu]

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

[Daniel Sobral]

On Mon, Aug 8, 2011 at 07:34, Marius Danciu <marius...@gmail.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.

[Marius Danciu]

Daniel,

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

Thanks,
Marius

[Meredith Gregory]

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

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

Seattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

[Luc Duponcheel]

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

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

reality goes far beyond imagination

[Meredith Gregory]

Dear Luc,

Just so! 

Best wishes,

--greg

[Shelby]

Let's derive the Liskov Substition Principle from first principles to unify subtyping with the conjunctive and disjunctive operations over (a.k.a. "conjunctivity" and "disjunctivity" of) sets, i.e. everything not outside any (a.k.a. intersection) of and inside all (a.k.a. union) of the sets respectively.

A supertype is the disjunction of its subtypes and a subtype is the conjunction of its supertypes. Profound.

We can't assign the subtype's TYPE to the supertype's TYPE (nor vice versa) because a disjunction is not equivalent to a conjunction.

A supertype is also the conjunction of the subtype variants for each named (i.e. nominal type of) member (i.e. operations a.k.a. methods), because each method implicitly (not Scala's implicit keyword) includes a `this` parameter-- don't conflate this with holding an INSTANCE of the TYPE as this sentence relates types not instances. Thus if our typesystem allows refering to an instance of a subtype with a supertyped reference because the system does not allow invoking methods without a downcast to the required subtype for the `this` of the method, then we can assign instances of subtypes to supertyped references.

In abstract type theory, the type of the `this` parameter for each of the supertype's methods is a disjunction of all the subtypes wherein the method returns the uninstantiable bottom type (e.g. `Nothing` in Scala) if the method is undefined for a subtype. Due to (the membership rule) being conditioned on the enclosing type in this way, the "conjunctivity" and "disjunctivity" (thus the requirement for covariance or contravariance) transpose on each enclosing step starting from the nominal (name of the) type, to the (function a.k.a. method or type parameter) members, to the types of the (function or type) parameters of the members, to the types of the (function or type) parameters of the types of the (function or type) parameters of the members, and so on recursively.

The relationship with covariance is consistent with either dual of De Morgan's laws e.g. one of the duals states the conjunction of all methods for subtypes A and B = not((not A) disjunction (not B)) where inverting the covariance (between co <--> contra) is equivalent to not in this formation, thus subparameters are the inverted covariance requirement of the disjunction of the inverted covariance requirements of the subsubparameters, and so on recursively. The post derives from prior discussion about a union type and Adriaan Moors explanatoin of potential new typing engine for a future Scala:

https://groups.google.com/d/msg/scala-language/z89k3_8U528/-Opsbk4hfmMJ

A subtype is also the disjunction of the subtype variants for each named member (i.e. operations a.k.a. methods) of its supertypes which are unimplemented (i.e. undefined), because the type of the `this` parameter for the unimplemented supertype's methods is the conjunction of all subtypes of the supertypes. This applies to unimplemented inherited methods in abstract types, interfaces, and the bottom type (e.g. `Nothing` in Scala).

Methods can return (assign from) conjunctions and input (assign to) disjunctions of a covariant member, or vice versa for a contraviant member, because we can assign covariantly from conjunctions e.g. val t: A = new (A with B) but not vice versa e.g. val t: A with B = new A. Similarly for disjunctions e.g. val t:Any = new A but not e.g. val t:A = new Any, where I am forced to write Any (the disjunction of every type in the universe, i.e. the top type) in my example because Scala doesn't have a first-class disjunction.

Thus as Luc Duponcheel wrote upthread, subtyping introduces the tradeoff that types can return covariant members and input contravariant members-- or both only for invariant members. Thus covariant type parametrized collections (e.g. List[+A] in Scala) can't enforce criteria w.r.t to the covariant member e.g. force appended elements to be subtypes of the covariant type parameter, e.g. A:

class List[+A](head: A, tail: List[A]) {

   def append[B <: A](el: B) = new List(el, this)

}

error: covariant type A occurs in contravariant position in type >: Nothing <: A of type B

          def append[B <: A](el: B) = new List(el, this)

                     ^

So they must be allowed to be subtypes:

class List[+A](head: A, tail: List[A]) {

   def append[B >: A](el: B) = new List(el, this)

}

defined class List

Yet that tradeoff doesn't apply if the restriction on the type parameter itself:

class List[+A <: C, C](head: A, tail: List[A,C]) {

   def append[B <: C](el: B) = new List(el, this)

}

defined class List

Type classes are a form of polymorphism (i.e. extensibility) where the `this` parameter is a type parameter of the operations. The operations for a concrete type can be matched nominally (by name) as shown in the OP or even structurally (although this can be erased and sometime cause reflection on the JVM and thus is probably inefficient).

As Daniel Sobral et. al wrote upthread, distinguish the model (e.g. Applicative or Monad) from the type of polymorphism (subtyping or type classes) employed to accomplish the model. For example, I believe I have shown how to combine subtyping and typeclasses to implement those models:

https://groups.google.com/d/msg/scala-debate/LWBz3-Q0pNI/y7PXwHi8MBUJ

As for the aforementioned tradeoff Luc Duponcheel wrote about, the model can be a criteria of membership and I am not sure if such a tradeoff ultimately exists. It seems to be always about raising the semantic abstraction to another level that paradigm shifts away the limitation. So more power to the models since they are obviously orthogonal to thus high-level semantics than the choice of polymorphism! By high-level, I measuring the relative distance of semantics from the imperative towards the declarative:

http://stackoverflow.com/questions/602444/what-is-functional-declarative-and-imperative-programming/15382180#15382180

The lower number of votes compared to my other very popular answer on that question, indicates most don't really grasp it or the relevance yet (or that I am wrong).

[Shelby]

On Sunday, September 15, 2013 4:49:14 PM UTC+8, Shelby wrote: 

Yet that tradeoff doesn't apply if the restriction on the type parameter itself:

 

class List[+A <: C, C](head: A, tail: List[A,C]) {

   def append[B <: C](el: B) = new List(el, this)

}

defined class List

...

  

As Daniel Sobral et. al wrote upthread, distinguish the model (e.g. Applicative or Monad) from the type of polymorphism (subtyping or type classes) employed to accomplish the model. For example, I believe I have shown how to combine subtyping and typeclasses to implement those models:

https://groups.google.com/d/msg/scala-debate/LWBz3-Q0pNI/y7PXwHi8MBUJ

Note that in the aforementioned link to my model of a Functor, Applicative, or Monad, the "non-static" methods from the typeclass are moved into subtying employing a higher-kinded type parameter Sub (now renamed SUB since it is a type parameter), i.e. analogous to the role of the C type parameter in the example above to constrain the criteria to a model thus covariance is an orthogonal issue of providing criteria (i.e. a model).

[Shelby]

On Monday, September 16, 2013 6:35:40 AM UTC+8, Shelby wrote: 

constrain the criteria to a model thus covariance is an orthogonal issue of providing criteria (i.e. a model).

s/orthogonal issue of providing/orthogonal issue TO providing/

[Shelby]

On Sunday, September 15, 2013 4:49:14 PM UTC+8, Shelby wrote: 

Yet that tradeoff doesn't apply if the restriction on the type parameter itself:

class List[+A <: C, C](head: A, tail: List[A,C]) {

   def append[B <: C](el: B) = new List(el, this)

}

defined class List

Well that was wrong in the sense the List is still invariant. So it wasn't a counter-example to  Luc Deponcheel's post.

However, I think we have conflated the covariant type with Scala's uncontrollable subsumption (as to which is the cause of the inability to restrict input types):

https://groups.google.com/forum/#!topic/scala-language/B6f-iubR9Mk

Thus there may be a solution. Let's see what others have to say.