Option as applicative functor

[Marius Danciu]

Hello,

Is there a good reason why Scala Option is not an applicative functor ? I guess one could seamlessly convert an Option[T] to an Applicative[T]  using implicits but still ..

Thanks,
Marius

[Luc Duponcheel]

which library are you talking about?

anyway
if Option[T] is a Monad[T] and the library (somehow) considers a Monad[T] as an Applicative[T]
then Option[T] is an Applicative[T] as well

in general, monads are applicative as follows

app(mf, mx) = for { x <- mx ; f <- mf } yield f(x)


Luc

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

reality goes far beyond imagination

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Which Applicative do you mean? For the one in scalaz, there is an
implementation for Option.

Do you want a method on Option[T] taking an Option[T => U], returning
Option[U]?

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOPTUYAAoJEPxHMY3rBz0P/AkH+QHw/TSMY0V/xdbiJCE3tDiD
vcp/q3joi28IrbYh1tCDwUmu9Ghkt20nTI28Q6vJAjw9VIgo5B3ZZt7oSP/GH2AW
P3q4+w1/63Kr9+6Tes18iunuXhgvxNYSIko5higoqa8pYIcjqYdcH4J00X6Kmxhm
cr7SsYDcN9E3sW1KLXwITXqc/oafYaKfFRDQgJi0UUItKBrkKsFrW5E1Ur5Oer+1
RKjG8iq1TPhvsfx9VruzRW/EQZIu8Lu7lHcI3gpDD0dAfkdBKSsaatgT6bYyWKM+
z9iknqxylEGDROUridDYNwylgO3NYMDsIXjGCrMYcfZgPM7PBbDaL/f0+u29+OI=
=ZOH6
-----END PGP SIGNATURE-----

[Marius Danciu]

Precisely.

Marius

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Well then that would require such a method on many type constructors,
and the body of these methods would be a copy/paste show.

def <*>[B](f: F[A => B]): F[B] = for { ff <- f; aa <- this } yield ff(aa)

On 06/08/11 22:52, Marius Danciu wrote:
> Precisely.
>
> Marius
>
> On Sat, Aug 6, 2011 at 3:35 PM, Tony Morris <tonym...@gmail.com> wrote:
>
> On 06/08/11 21:27, Marius Danciu wrote:
>>>> Hello,
>>>>
>>>> Is there a good reason why Scala Option is not an applicative functor ? I
>>>> guess one could seamlessly convert an Option[T] to an Applicative[T]
> using
>>>> implicits but still ..
>>>>
>>>> Thanks,
>>>> Marius
>>>>
>
> Which Applicative do you mean? For the one in scalaz, there is an
> implementation for Option.
>
> Do you want a method on Option[T] taking an Option[T => U], returning
> Option[U]?
>
>
>>

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOPTmTAAoJEPxHMY3rBz0PKcwH/iIFD1ObJ9mv3guHeG8ZtA7g
FaihUXwmV+qd/mCUpvNaGp7mj1gpZwJuS2360CsFjoyKaNiA3ilI5n5ZpBNokGiT
ZgMvQb1akKCQuwIjDfmSdbiXltipsEjnh9X6210qwbpOyUip+ocniS+c3WanUvps
Au3VhUe95/cc7cesjl2oOrwdDsvwgel1mJlMnOwxTTikWoV3d7jgi/cIZCmTut9u
uJ9egAiVE4RycQ83omx/95VRyRBM78UvfHdzhzIQSkiT+NLz6qtHRniEku0Qvb7k
U9iiCq0q4m5FIKFA4HGABi09OC/I7OKneQ3uSrlLZHdF5nLJCU53XeaDLxtFaWs=
=cJng
-----END PGP SIGNATURE-----

[Marius Danciu]

HI Luc,

I'm referring to scala.Option.

Thanks,
Marius

[Marius Danciu]

Right, but I guess here could have been an Applicative[T[_]] trait that those type constructors such as Option would mixin with, avoiding copy-paste in many cases. Applicative would probably have to extend Functor[T[_]] for having unit and fmap.

Thanks,
Marius

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

You could say that about an enormous number of traits.

There is a "growing movement" of people who delay introduction of the
unit operation, so you'd have a trait with ap+fmap instead (semigroups
instead of monoids).

iQEcBAEBAgAGBQJOPTwJAAoJEPxHMY3rBz0PPK0IALCCSVUxZ3Uv37LQhdkA1QJ1
LlkFaJ9dFoSwqoPDe7WxuqxnWTNe12iNc7op5Mw00Ql2bSa8V7sOfVSMaj+oyxeO
Ci+QlO633wjTcsfPbcPugJ6usqN/EM6Dm0rMx/c7eeKxIktzhKT7x+vq4c29H4Ru
lG5SjMscm6teN9MMuCeCcTl1RklymAl6YvETemM1AQW3H1SNmFDpKRUyLAbkj0Vj
HuiDBzDy/4MhLj79zJTFG+/MMAOra0c99QQJ0vJvpRoHZvAhNC8y9MdOpq/h+nH3
M4prjgvG3/PyIeyVJI0p5ZJ66QnyqTJPRH/xORTMkf6hDLZhos0cJq8PMpTAVIw=
=T2dK
-----END PGP SIGNATURE-----

[Marius Danciu]

Yes indeed ...

[Luc Duponcheel]

> ... "growing movement" of people ...

I still think that nested traits
 - the outer one containing stuff like unit and join
 - the inner one containing stuff like map (>=) and ap (<*>)
is a valuable alternative

the outer traits, eventually, become something like
 - an implicit identityMonad,
 - an implicit stateTransformedIdentityMonad
 - an implicit controlTransformedIdentityMonad
 - ...
the inner traits, eventually, become case classes


agreed: it adds some complexity

ps:
personally I hope that this new DOT (dependent object types) approach
will work nicely with nested traits


Luc

[Josh Suereth]

I'm hoping to convince enough folks to get a few, small number, of type traits into the standard library to go along with Numeric.

In particular, I think Monad, Monoid and Functor could be enough to pull in most of the useful parts of Scalaz into general usage.

In particular, applicative style is very handy at times, and I'd love to see it supported in the core in a generic manner.   I'm working on expanding Jorge's implicit class Foo(x) proposal to include one that makes type trait usage in Scala more efficient and easier.   This I think is a requirement to having Scalaz like abstractions gain general acceptance in Scala.

[Erik Osheim]

On Sat, Aug 06, 2011 at 12:01:03PM -0400, Josh Suereth wrote:
> In particular, applicative style is very handy at times, and I'd love to see
> it supported in the core in a generic manner. I'm working on expanding
> Jorge's implicit class Foo(x) proposal to include one that makes type trait
> usage in Scala more efficient and easier. This I think is a requirement to
> having Scalaz like abstractions gain general acceptance in Scala.

Ever since your earlier email about this I've been interested and
waiting to see what you have. Anything you can share yet? I'd love to
be a sounding board on this, given that it could really aid the work
I'm doing with Numeric.

-- Erik

[Marius Danciu]

That'd be great and I'm sure that a lot of folks are looking for this.

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

If we could just delay the introduction of the point operation... even
Scala has this bias in its for-comprehensions.

There are many useful operations on, say map+flatMap, for which there
are structures that many not be pointed functors. It is then that you
"go sideways" and introduce the point operation.

Regardless of representation, I would suggest the following levels of
abstraction:
* map
* ap+map
* flatMap+map
...
* map+point
* ap+map+point (aka Applicative)
* flatMap+map+point (aka Monad)

I guess I am encouraging this direction because I came up with it myself
after observing that (to summarise) "not all semigroups are monoids",
then I was subsequently convinced by Edward Kmett about this direction
(while hiding the fact that I was already well-persuaded).

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOPcGzAAoJEPxHMY3rBz0PG88H/1TkciGB/w/u8C78QeuNhtWf
GP13VSOPqDP9RCctSfOD6p5daRox+PKlNZj641DpD2dfY3o8S0x+DnDk1oUIVIjQ
8pLIVMP7WWp0s6G5zRLiu1+JDLwk16Ds44q60FOGMEzzCn5sDevc2qfd7xKipTi1
I7uFVmn36thk6VMAFKN9IbnGNpgogN2Wp2JzK/4f7lKaM+Nj4+sXEGu5ItWQXkX6
dAew9c2p2cQnTvgiUUPFyMsOYZtYjq/h/bF7ILmjm/Fk66t02P5QXZ2Ffc6aLoAS
EHLWTRyr5Vcq0vaoKna9OfhqyrVeFVIm8FOzpG9kxy0jSzPNwP0TVE29/adN/vI=
=8AjM
-----END PGP SIGNATURE-----

[Josh Suereth]

What you call Applicative, I call functor, at least from what I understand of the raw translation of the laws of Functors to C.S.   Functors preserve morphisms (i.e. ap) and I'm not really sure it makes sense to call something a Functor that does not have a "point" i.e. def point[Functor[_]](a: A): Functor[A].

So, in adding Functor + Monad to the std lib, what I really want is a type-class way to enter into for-expressions and the ability to use applicative style on anything and everything in Scala out of the box.

Here's my definition of Functor + Monad:

trait Functor[T[_]] {

   def apply[A](x: A): T[A]                               // my preferred implementation for 'point'

   def fmap[A,B](x : T[A])(f : T[A=>B]) : T[B]    // ap, but not ap

   def map[A,B](x : T[A])(f: A=>B) : T[B] = fmap(x, apply(f))

}

abstract class Monad[T[_]](functor: Functor[T[_]]) {

  def flatten[A](m : T[T[A]]) : T[A]

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

    flatten(functor.map(x)(f))

  def apply[A](m: A): T[A] = functor(m)

}

Where "flatten" and "apply" are the join + zero of Monoid defined on Functors.  In an ideal langauge, you could abstract that all out, but let's be practical.

So, in any case, given those two deifnitons, I should be able to:

def foo[T[_]: Monad,A,B](t: T[A], t2: T[B]) = for { x <- t; y <- t2 } yield doSomething(x,y)

*or*

def makeConnection[T[_]: Functor](url: T[String], user: T[String], pw: T[String]): T[java.sql.Connection] = 

    url <*> user <*> pw apply java.sql.DriverManager.getConnection

This, I'd love to have in the std library.  Is there anything that would be 'hurt' in not having an abstraction with just map or just flatMap + map or map + ap?  I'm just curious, as I haven't been as far down library design as you have.

Finally, the google doc of my proposal for type traits is almost ready.   Want to send it past a few folks to get the "ZOMG WHAT ARE YOU TRYING TO DO, KILL US" comments out of the way first.

- Josh

[Vlad Patryshev]

:) Oh how I share this categorist's frustration over terms misused/abused.

See, actually by applicative (in cartesian-closed categories), I  believe they mean preservation of exponent.

F[X] x F[Y^X] -> F[Y]

http://presheaf.com/cache/d211k3i3k6qw6r5e2wq5m3a1x4nt59.png



Thanks,
-Vlad

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

An applicative functor is a special type of functor. Not all functors
are applicative. Indeed, not all functors are pointed functors (all
applicative functors are pointed functors). There are also plenty of
functors that have F[A => B] => F[A] => F[B] but not necessarily point
(A => F[A]).

iQEcBAEBAgAGBQJOPj8EAAoJEPxHMY3rBz0PUgUH/iuqH7Fm4zC5QnTM40CWXU8m
i88Kek5DDycJYro5caVYxB1Lz3v57ILXlEqWNZDgo7xBf/2EvWvbVgZKC1MY9cq+
RkggKm5XMMaxLzD3B865VF11HoNTB5nT7MWPcpxh5agrSbtLJK3Q1yubOU3H++SO
LycwJDFymfYn22iyvvb1/+xpudN1dSpmyJ5ZgJrReB9aXaR4I9Be9kx8ZmO+Cjxk
rzg/QoMFGvNTa0V0PVQn5J/5V2t79ZnzM30lPaxU5JPKdwlYiPbrUWgCLh3aBMfj
jqAXXHRwE1TcvWLkBdsgwfSGDKbLKlNyGQ+vvC8azQSX5f3n3O/Orr/gHPr/Qpc=
=Kc2K
-----END PGP SIGNATURE-----

[Josh Suereth]

On Sun, Aug 7, 2011 at 3:30 AM, Tony Morris <tonym...@gmail.com> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

An applicative functor is a special type of functor. Not all functors
are applicative. Indeed, not all functors are pointed functors (all
applicative functors are pointed functors). There are also plenty of
functors that have F[A => B] => F[A] => F[B] but not necessarily point
(A => F[A]).

This of course, implies that they are Functors of the empty set.

So first, I think I messed up my terminology.  Applicative ( F[A=>B] => F[A] => F[B] ) is indeed *not* defined for all Functors.  Functors 'preserve morphisms' which is, they define  (A=>B) => (F[A] => F[B]) which is simply the 'map' operation, not fmap.  So, I totally understand the need for a separate Applicative trait now.

Now, Some Functors do not have direct constructors on all types, but if they are not over the empty-set of types, one can derive a generic apply *if and only if* there is exactly one F[A] that can be constructed and 'map' is defined for all functions A=>B and functor instances F[A].   That is:

Given a single instance of F[X], I can define point as:   def point[A](a: A) = instanceOfF.map(ignore => a)

This isn't particularly useful, but it means that for all Functors defined against non-empty categories that also have a map function that spans all types, given a single 'point' manipulation, I can derive a point opreation for all possible types and values.

I think the issue here is one of practicality.   For example, the ManagedResource[_] trait in my scala-arm library defines a map operation that works across all possible function A => B.   However, the constructor for ManagedResource[_] only accepts types that are supported with an implicit Resource type class.   So, you could use these to say that ManagedResource is a Functor defined on types that are supported with Resource type classes.   Defining this in Scala is difficult/impractical in the type system.   However, since the map operation is define on all types, we can construct a point operation given any ManagedResource.   Again, this is impractical in real-lift code.

So, while I disagree on terminology, I do agree that I think you may have outlined the abstractions appropriately.   I'd like to choose a new non-confusing name first though :)

I think these abstractions are the only ones I'd like to see directly...

map + ap (for Applicative style usage)

map + flatMap (for Monads + for expression)

map + flatMap + withFilter  (stronger for expression)

As for point, although I'd argue that if you support any of those abstraction, you can construct a point operation as long as your category F[_] is non-empty... it's also impractical for certain types of Functors.

- Josh

[Josh Suereth]

In any case, are you interested in developing a small subset(the least controversial) of scalaz to push into scala-incubator.  If we start now, we can hopefully gain enough traction.

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sure! Though I never can work out which is most controversial.

iQEcBAEBAgAGBQJOPwZVAAoJEPxHMY3rBz0PE58H/j8i2gAEcXiGHpcb2yDF64EV
yhYoXeLG4o5mLuxRzBJcvL6Quvm2O22edkOD0Bpqy6Y6lX9iAwcEIblcdHKgHzv3
h2yjBeKOD5QxUxH/9whCHOV/inJbYH1dZDL4LwjE3UW9CkjzLwp/Tr4bHCQAKDr5
TJXR72LaR9Nnd0JZ8L8XIDMEaBPi0vLVioCulg3WrrihzViNY6ZUOmh2Q2kcdhA7
HQKKnL6Za0gQYb6OQ2FzvxSSwmvQECXDbsRtp+vE9rQq8nX2swpe/ba1b8p7mS/M
o+1J8rU8e2ZydbV/wCuKDKOuGdh79emPaTj9zsCLml5XabshGAh5d3IvDx+eF6Y=
=vgKQ
-----END PGP SIGNATURE-----

[Simon Ochsenreither]

Just wondering...

Which package name do you intend to use?

Thanks and bye,

Simon

[Josh Suereth]

scalax.functional? scalax.category?