type inference vs haskell?

... just to mention one thing (of course there's more to it than that) ...

Scala's type inferencer is flow based and cannot deal with recursion

$ scala
Welcome to Scala version 2.9.0.1 (Java HotSpot(TM) Server VM, Java 1.6.0_26).
Type in expressions to have them evaluated.
Type :help for more information.

scala> def fac(x: Int) = if (x == 0) { 1 } else { x * fac(x - 1) }
<console>:7: error: recursive method fac needs result type
       def fac(x: Int) = if (x == 0) { 1 } else { x * fac(x - 1) }
                                                      ^

scala> def fac(x: Int): Int = if (x == 0) { 1 } else { x * fac(x - 1) }
fac: (x: Int)Int

scala> fac(3)
res0: Int = 6

scala>

On Tue, Jul 5, 2011 at 8:39 AM, Dennis Haupt <h-star@gmx.de> wrote:

i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.

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

reality goes far beyond imagination

On 05/07/11 16:39, Dennis Haupt wrote:
> i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.

scala> val x = (_.reverse)
:7: error: missing parameter type for expanded function ((x$1)
=> x$1.reverse)
val x = (_.reverse)

>> let x = reverse
>> :t reverse
reverse :: [a] -> [a]

Tony Morris wrote:
> On 05/07/11 16:39, Dennis Haupt wrote:
>> i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.
> scala> val x = (_.reverse)
> :7: error: missing parameter type for expanded function ((x$1)
> => x$1.reverse)
> val x = (_.reverse)
>
>>> let x = reverse
>>> :t reverse
> reverse :: [a] -> [a]
>
Isn't this because Haskell's types are structural while Scala's are
nominal? AFAIU, nominal typing is what makes OO possible. Or in other
words, in Haskell, you cannot have a list of fruits containing both
apples and oranges.

So I don't think Scala's type inference is inferior, since it deals with
more complex types (meaning, more complex scenarios when analyzing a type)

Ittay

Hi Dennis!
As always many others have walked this road. You simply have to follow
the tracks.
IMHO Daniel Spiewak has quite a talent to explain things so here his
research on scala-haskell type inference:
 http://www.codecommit.com/blog/scala/what-is-hindley-milner-and-why-
is-it-cool

http://chariotsolutions.com/presentations/uncovering-the-unknown-princip...

Regards Andreas
On 5 Jul., 08:39, "Dennis Haupt" wrote:
> i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.

First off, please avoid using adjectives like "superior" -- I wouldn't know how to measure that.
Qualitatively, here are my 2 cents:

The settings are very different: Scala does local type inference, which follows from the desire to have separate compilation, and the fact that types serve as (mandatory) documentation at "module boundaries" (i.e., method signatures). You shouldn't infer them, just like we don't infer scaladoc. Along with subtyping, this constrains how far you can go in automating things.
Haskell's (original) goal is to infer every type, and the compiler will happily cross module boundaries to do so. They have long resisted adding features that break this property, but this reluctance has been eroding recently, as they start hitting the limits of what they can infer given more powerful type system extensions (for some of the earlier stuff where this started happening, see the excellent tutorial-style paper http://research.microsoft.com/en-us/um/people/simonpj/papers/higher-rank/index.htm, and for more recent work: http://haskell.org/haskellwiki/Simonpj/Talk:OutsideIn). 
They infer polymorphic types, such as in the example of _.reverse (forall a, [a] -> [a]). Scala does not do that. I claim it's only a minor nuisance.
I think of it this way: we focus on making the life of clients of abstractions easier, which is where the big pay-off is: you write an abstraction once and then use it lots and lots of times. Concretely, when you write the abstraction _.reverse, you'll need to work a little harder, but using it (applying it to arguments) is just as easy as in Haskell.
cheersadriaan
On Tue, Jul 5, 2011 at 8:39 AM, Dennis Haupt <h-star@gmx.de> wrote:

i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.

Hi ittay!
Never EVER underestimate Haskell (or Scala) ;)
http://paste.pocoo.org/show/426874/
His is your quoted list encoding using phantom types, I bet you could
his in Haskell too. The snippet is from a conversation between
@jamesiry and @fogus, which was related to that problem.
Regards Andreas
On 5 Jul., 09:05, Ittay Dror wrote:
> Tony Morris wrote:
> > On05/07/11 16:39, Dennis Haupt wrote:
> >> i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.
> > scala>  val x = (_.reverse)
> > :7: error: missing parameter type for expanded function ((x$1)
> > =>  x$1.reverse)
> >         val x = (_.reverse)
>
> >>> let x = reverse
> >>> :t reverse
> > reverse :: [a] ->  [a]
>
> Isn't this because Haskell's types are structural while Scala's are
> nominal? AFAIU, nominal typing is what makes OO possible. Or in other
> words, in Haskell, you cannot have a list of fruits containing both
> apples and oranges.
>
> So I don't think Scala's type inference is inferior, since it deals with
> more complex types (meaning, more complex scenarios when analyzing a type)
>
> Ittay

so haskell can infer the type after the declaration. i tried to do that in scala once and quickly forgot i had.

-------- Original-Nachricht --------
> Datum: Tue, 05 Jul 2011 16:55:14 +1000
> Von: Tony Morris
> An: scala-user@googlegroups.com
> Betreff: Re: [scala-user] type inference vs haskell?

> On 05/07/11 16:39, Dennis Haupt wrote:
> > i read somewhere on this list that haskells type inference is superior
> to scalas. can someone point me at something that doesn't work with scala,
> but with haskell? i'd like to see the magic.
>
> scala> val x = (_.reverse)
> :7: error: missing parameter type for expanded function ((x$1)
> => x$1.reverse)
> val x = (_.reverse)
>
> >> let x = reverse
> >> :t reverse
> reverse :: [a] -> [a]
>
>

Here is how you can do it in Haskell:

http://stackoverflow.com/questions/995781/haskell-polymorphism-and-lists/995833#676767

2011/7/5 Andreas Scheinert <andreas.scheinert@googlemail.com>

Hi ittay!
Never EVER underestimate Haskell (or Scala) ;)
http://paste.pocoo.org/show/426874/
His is your quoted list encoding using phantom types, I bet you could
his in Haskell too. The snippet is from a conversation between
@jamesiry and @fogus, which was related to that problem.
Regards Andreas
On 5 Jul., 09:05, Ittay Dror <ittay.d...@gmail.com> wrote:
> Tony Morris wrote:
> > On05/07/11 16:39, Dennis Haupt wrote:
> >> i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.
> > scala>  val x = (_.reverse)
> > <console>:7: error: missing parameter type for expanded function ((x$1)
> > =>  x$1.reverse)
> >         val x = (_.reverse)
>
> >>> let x = reverse
> >>> :t reverse
> > reverse :: [a] ->  [a]
>
> Isn't this because Haskell's types are structural while Scala's are
> nominal? AFAIU, nominal typing is what makes OO possible. Or in other
> words, in Haskell, you cannot have a list of fruits containing both
> apples and oranges.
>
> So I don't think Scala's type inference is inferior, since it deals with
> more complex types (meaning, more complex scenarios when analyzing a type)
>
> Ittay

--
Sébastien

Hi Adriaan,

Here is an example for which I see no elegant solution in Scala. Isn't this a limitation of Scala's type inference system?

Thanks,
Sebastien

Haskell:

newtype State s a = State { runState :: (s -> (a,s)) }
 
instance Monad (State s) where
 return a        = State $ \s -> (a,s)
 (State x) >>= f = State $ \s ->
     let (v,s') = x s
     in runState (f v) s'

Scala:


trait Monad[M[_]] {

  def unit[A](a: => A):M[A]
  def bind[A, B](m:M[A], f:A => M[B]):M[B]
}
 
class State[S, A](runState:S => (S, A))
  
implicit val stateMonad = new Monad[({type T[A] = State[S, A] forSome {type S}})#T] {
  ??
}

2011/7/5 Adriaan Moors <adriaan.moors@epfl.ch>

First off, please avoid using adjectives like "superior" -- I wouldn't know how to measure that.
Qualitatively, here are my 2 cents:

The settings are very different: Scala does local type inference, which follows from the desire to have separate compilation, and the fact that types serve as (mandatory) documentation at "module boundaries" (i.e., method signatures). You shouldn't infer them, just like we don't infer scaladoc. Along with subtyping, this constrains how far you can go in automating things.
Haskell's (original) goal is to infer every type, and the compiler will happily cross module boundaries to do so. They have long resisted adding features that break this property, but this reluctance has been eroding recently, as they start hitting the limits of what they can infer given more powerful type system extensions (for some of the earlier stuff where this started happening, see the excellent tutorial-style paper http://research.microsoft.com/en-us/um/people/simonpj/papers/higher-rank/index.htm, and for more recent work: http://haskell.org/haskellwiki/Simonpj/Talk:OutsideIn). 
They infer polymorphic types, such as in the example of _.reverse (forall a, [a] -> [a]). Scala does not do that. I claim it's only a minor nuisance.
I think of it this way: we focus on making the life of clients of abstractions easier, which is where the big pay-off is: you write an abstraction once and then use it lots and lots of times. Concretely, when you write the abstraction _.reverse, you'll need to work a little harder, but using it (applying it to arguments) is just as easy as in Haskell.
cheersadriaan
On Tue, Jul 5, 2011 at 8:39 AM, Dennis Haupt <h-star@gmx.de> wrote:

i read somewhere on this list that haskells type inference is superior to scalas. can someone point me at something that doesn't work with scala, but with haskell? i'd like to see the magic.

--
Sébastien

On Tue, Jul 5, 2011 at 2:30 PM, Sébastien Bocq wrote:
> Here is an example for which I see no elegant solution in Scala. Isn't this
> a limitation of Scala's type inference system?

> class State[S, A](runState:S => (S, A))
>
> implicit val stateMonad = new Monad[({type T[A] = State[S, A] forSome {type
> S}})#T] {
> ??
> }

Isn't this sufficient?

implicit def stateMonad[S] = new Monad[({type T[A] = State[S, A]})#T] {
// All good!
}

Missing type inference never limits what you can express, it only
limits the brevity with which you can express it.

-jason

It is not enough.

First you must create the monad class explicitly for each type S.

implicit val m = stateMonad[Int]

And then, you can't define/use sequence_ in a generic manner. For example, the following obviously will not work:

def sequence_[M[_], A](ms:M[A]*)(implicit m:Monad[M]):M[Unit] =
  if (ms.isEmpty) m.unit(())
  else m.bind(ms.head, {_:A => sequence_(ms.tail:_*)(m)})
     
val move = new State[Int, Unit](pos => (pos + 1, ()))

sequence(move, move)

type mismatch;  found   : State[Int,Unit]  required: ?M[ ?A ]

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

2011/7/5 Jason Zaugg <jzaugg@gmail.com>

On Tue, Jul 5, 2011 at 2:30 PM, Sébastien Bocq <sebastien.bocq@gmail.com> wrote:
> Here is an example for which I see no elegant solution in Scala. Isn't this
> a limitation of Scala's type inference system?

> class State[S, A](runState:S => (S, A))
>
> implicit val stateMonad = new Monad[({type T[A] = State[S, A] forSome {type
> S}})#T] {
>   ??
> }

Isn't this sufficient?

 implicit def stateMonad[S] = new Monad[({type T[A] = State[S, A]})#T] {
    // All good!
 }

Missing type inference never limits what you can express, it only
limits the brevity with which you can express it.

-jason

--
Sébastien

On Tue, Jul 5, 2011 at 10:24, Sébastien Bocq wrote:
> It is not enough.
>
> First you must create the monad class explicitly for each type S.
>
> implicit val m = stateMonad[Int]

implicit def m[T] = stateMonad[T]

So there's no particular need to be explicit about each type S.

>
> And then, you can't define/use sequence_ in a generic manner. For example,
> the following obviously will not work:
>
> def sequence_[M[_], A](ms:M[A]*)(implicit m:Monad[M]):M[Unit] =
>   if (ms.isEmpty) m.unit(())
>   else m.bind(ms.head, {_:A => sequence_(ms.tail:_*)(m)})
>
> val move = new State[Int, Unit](pos => (pos + 1, ()))
>
> sequence(move, move)
>
> type mismatch;  found   : State[Int,Unit]  required: ?M[ ?A ]

I'll let Jason handle this, but, it seems to me, all that is missing
is an implicit.

> I know there are tricks, I merely wanted to point out that it can't be
> expressed as elegantly as in Haskell because the type system is less
> powerful.

Actually, it can't because the type system is *more* powerful, making
the type inference less able.

The settings are very different: Scala does local type inference, which follows from the desire to have separate compilation, and the fact that types serve as (mandatory) documentation at "module boundaries" (i.e., method signatures). You shouldn't infer them, just like we don't infer scaladoc.

This is key. Long ago I was very interested in pure functional programming (was doing a Ph.D. program on it), and I found that the functional community was so enamored of type inference that they were writing code that was, IMHO, almost unreadable. Type signatures provide a _very_ valuable form of documentation (and one that people can't omit :-) )
Ken 

On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq <sebastien.bocq@gmail.com> wrote:

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

it's not the type system, it's the type inferencer
we don't infer types like `({type T[A] = State[S, A]})#T` (that requires higher-order unification, which is a pending enhancement: https://issues.scala-lang.org/browse/SI-2712)
type inference is tuned for cases where a class type can be inferred, thus, this type checks:
trait Monad[M[_]] {  def unit[A](a: => A):M[A]  def bind[A, B](m:M[A], f:A => M[B]):M[B]}

trait StateMonad[A] extends Monad[StateMonad] { // key difference: now we have StateMonad as an available type to be inferred   type S  val runState: S => (S, A)  def unit[A](a: => A): StateMonad[A] = error("")  def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("") }  object Test {    implicit def stateMonad[S] = new Monad[StateMonad] {    def unit[A](a: => A): StateMonad[A] = error("")    def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("")   }    def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]): M[Unit] =    if (ms.isEmpty) m.unit(())    else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})     val move = new StateMonad[Unit]{type S = Int; val runState = {pos: S => (pos + 1, ())}}    val x = sequence(move, move)}

I know, I know, it's not as Haskelly. Maybe it can be made  openly extensible similar to what type classes offer, but I don't see how immediately...
adriaan

2011/7/5 Adriaan Moors <adriaan.moors@epfl.ch>

On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq <sebastien.bocq@gmail.com> wrote:

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

it's not the type system, it's the type inferencer
we don't infer types like `({type T[A] = State[S, A]})#T` (that requires higher-order unification, which is a pending enhancement: https://issues.scala-lang.org/browse/SI-2712)
type inference is tuned for cases where a class type can be inferred, thus, this type checks:
trait Monad[M[_]] {  def unit[A](a: => A):M[A]  def bind[A, B](m:M[A], f:A => M[B]):M[B]}

trait StateMonad[A] extends Monad[StateMonad] { // key difference: now we have StateMonad as an available type to be inferred   type S  val runState: S => (S, A)  def unit[A](a: => A): StateMonad[A] = error("")  def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("") }  object Test {    implicit def stateMonad[S] = new Monad[StateMonad] {    def unit[A](a: => A): StateMonad[A] = error("")    def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("")   }    def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]): M[Unit] =    if (ms.isEmpty) m.unit(())    else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})     val move = new StateMonad[Unit]{type S = Int; val runState = {pos: S => (pos + 1, ())}}    val x = sequence(move, move)}

I know, I know, it's not as Haskelly. Maybe it can be made  openly extensible similar to what type classes offer, but I don't see how immediately...
adriaan

Yes, I should have said type inferencer. It's an interesting approach, I never saw it before.

Thanks for the explanation,
Sébastien

i lost track here:

trait Monad[M[_]] {

  def unit[A](a: => A):M[A]
  def bind[A, B](m:M[A], f:A => M[B]):M[B]
}
 
and here:
({type T[A] = State[S, A]})#T

and here:
"forSome"

i'm pretty sure it's awesome, but what is it?

Am 05.07.2011 18:45, schrieb Sébastien Bocq:

8Ad_TvXQnsbSVLNzEQg [at] mail [dot] gmail [dot] com" type="cite">

2011/7/5 Adriaan Moors <adriaan [dot] moors [at] epfl [dot] ch" rel="nofollow">adriaan.moors@epfl.ch>

On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq <sebastien [dot] bocq [at] gmail [dot] com" target="_blank" rel="nofollow">sebastien.bocq@gmail.com> wrote:

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

it's not the type system, it's the type inferencer
we don't infer types like `({type T[A] = State[S, A]})#T` (that requires higher-order unification, which is a pending enhancement: https://issues.scala-lang.org/browse/SI-2712)
type inference is tuned for cases where a class type can be inferred, thus, this type checks:
trait Monad[M[_]] {   def unit[A](a: => A):M[A]   def bind[A, B](m:M[A], f:A => M[B]):M[B] }

trait StateMonad[A] extends Monad[StateMonad] { // key difference: now we have StateMonad as an available type to be inferred   type S   val runState: S => (S, A)   def unit[A](a: => A): StateMonad[A] = error("")   def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("") }    object Test {      implicit def stateMonad[S] = new Monad[StateMonad] {     def unit[A](a: => A): StateMonad[A] = error("")     def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("")   }      def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]): M[Unit] =     if (ms.isEmpty) m.unit(())     else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})      val move = new StateMonad[Unit]{type S = Int; val runState = {pos: S => (pos + 1, ())}}      val x = sequence(move, move) }

I know, I know, it's not as Haskelly. Maybe it can be made  openly extensible similar to what type classes offer, but I don't see how immediately...
adriaan

Yes, I should have said type inferencer. It's an interesting approach, I never saw it before.

Thanks for the explanation,
Sébastien

On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath <h-star@gmx.de> wrote:

i lost track here:

trait Monad[M[_]] {

  def unit[A](a: => A):M[A]
  def bind[A, B](m:M[A], f:A => M[B]):M[B]
}

That's one representation of a Monad typeclass. The idea is they you would have one or more implicit concrete implementation available to be injected wherever you need monadic features for some container type "M[_]".

"unit" is the an abstraction for a constructor of the monad type.
"bind" is the abstraction which you probably know better as "flatMap" in Scala.
 

 
and here:
({type T[A] = State[S, A]})#T

Currently, this is the best way to define a partially-applied type constructor in Scala. That is, imagine a type constructor with two arguments T[A, B]. Now say you want to define a one-argument type constructor by providing a concrete binding for A -- e.g., you want to bind A to "Int". You would get a new type constructor with only a single argument: T2[B] = T[Int, B]. But in Scala you can't create new type constructors like that. Currently the only way to pull it off is using that ugly construct you see above.

That is:

"{type T2[A] = State[Int, A]}" defines an anonymous class with a single member: a 1-parameter type constructor named "T2". T2[A] is an alias for State[Int, A], where only State's second type parameter, "A", is unbound.

"({type T2[A] = State[Int, A]})#T2" is an explicit reference to the "T2" type constructor inside the anonymous class. The net effect is that you end up with a new type constructor, T2, that has one type argument, and which is equal to "State[A, B]" with "A" bound to "Int".
 

and here:
"forSome"

I know those are called "existential types", but honestly I don't use them and only have an intuitive sense of what they mean when I'm looking at code that uses them. Perhaps someone else can take a swing? or maybe Google can shed light for you if use search for "Scala existential type"?


--
Best regards,
Brian Maso
(949) 395-8551
Follow me: @bmaso
brian@blumenfeld-maso.com
 

i'm pretty sure it's awesome, but what is it?

Am 05.07.2011 18:45, schrieb Sébastien Bocq:

2011/7/5 Adriaan Moors <adriaan.moors@epfl.ch>

On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq <sebastien.bocq@gmail.com> wrote:

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

it's not the type system, it's the type inferencer
we don't infer types like `({type T[A] = State[S, A]})#T` (that requires higher-order unification, which is a pending enhancement: https://issues.scala-lang.org/browse/SI-2712)
type inference is tuned for cases where a class type can be inferred, thus, this type checks:
trait Monad[M[_]] {   def unit[A](a: => A):M[A]   def bind[A, B](m:M[A], f:A => M[B]):M[B] }

trait StateMonad[A] extends Monad[StateMonad] { // key difference: now we have StateMonad as an available type to be inferred   type S   val runState: S => (S, A)   def unit[A](a: => A): StateMonad[A] = error("")   def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("") }    object Test {      implicit def stateMonad[S] = new Monad[StateMonad] {     def unit[A](a: => A): StateMonad[A] = error("")     def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("")   }      def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]): M[Unit] =     if (ms.isEmpty) m.unit(())     else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})      val move = new StateMonad[Unit]{type S = Int; val runState = {pos: S => (pos + 1, ())}}      val x = sequence(move, move) }

I know, I know, it's not as Haskelly. Maybe it can be made  openly extensible similar to what type classes offer, but I don't see how immediately...
adriaan

Yes, I should have said type inferencer. It's an interesting approach, I never saw it before.

Thanks for the explanation,
Sébastien

On Tue, Jul 5, 2011 at 16:06, HamsterofDeath wrote:
> i lost track here:
>
> trait Monad[M[_]] {
>
> def unit[A](a: => A):M[A]
> def bind[A, B](m:M[A], f:A => M[B]):M[B]
> }
>
> and here:
> ({type T[A] = State[S, A]})#T

Structural type. Let's see a simple structural type:

def [T <: { def close(): Unit }](list: List[T]) = list foreach (_.close())

The structural type here is "{ def close(): Unit }" -- or any type
whose structure includes a 0-arity method called "close" that returns
Unit.

So "{ type T[A] = State[S, A] }" is a structural type, where the
abstract type T[A] is defined as being an alias for State[S, A]. Next,
we put that inside () and put an #T afterwards. That means all
subtypes T of the afore-mentioned structural type.

To better understand it, consider this:

scala> def f[M[_]](m: M[Int]) = m
f: [M[_]](m: M[Int])M[Int]

scala> f[List](List(1, 2, 3))
res3: List[Int] = List(1, 2, 3)

So f expects a type constructor M. Well, the T of the type we have
been discussing is a type constructor as well -- from T[A] it produces
a State[S, A]. Let's try to apply it here:

scala> import scala.collection.generic.GenericTraversableTemplate
import scala.collection.generic.GenericTraversableTemplate

scala> f[({ type T[A] = GenericTraversableTemplate[A, List] })#T](List(1, 2, 3))
res5: scala.collection.generic.GenericTraversableTemplate[Int,[+A]List[A]]
= List(1, 2, 3)

I used GenericTraversableTemplate because it's second parameter is a
type constructor, as we require for this example. A
GenericTraversableTemplate takes two parameters -- the first is the
element type, just like in List. The second is the type constructor
that's used in various methods. We could not use it directly with f:

scala> f[GenericTraversableTemplate[_, List]](List(1,2 ,3))
:12: error:
scala.collection.generic.GenericTraversableTemplate[_, List] takes no
type parameters, expected: one

So, using that little trick, we created a type constructor T which was
used to convert GenericTraversableTemplate from two parameters to a
type constructor with one parameter -- the other having been bound to
List.

>
> and here:
> "forSome"

Existential type. I might be mistaken -- and the explanation probably
has errors anyway --, but I think this is related to logic
quantifiers. The types we are used to are universal quantifiers: if we
say

def f[T](lst: List[T]): Option[T] = lst.headOption

We mean that for all T, lst will be of type List[T]. On the other
hand, if we have:

def f(lst: List[T] forSome { type T }): Boolean = lst.isEmpty

We mean that there exists a type T, of which we know nothing about,
for which the type of lst will be List[T].

In particular, notice that we know precisely what's the T in the first
example, so we can use it as a return type, but we know nothing about
it in the second example -- but, as it happens, we don't need to.

>
> i'm pretty sure it's awesome, but what is it?

implicit val stateMonad = new Monad[({type T[A] = State[S, A] forSome
{type S}})#T]

We declare that stateMonad is a Monad (remember that Monad is trait
Monad[M[_]] -- needs a type constructor) whose type parameter is a
type constructor T[A], which constructs a State[S, A], where S is some
type which we know nothing about (but that it exists :).

I hope this helps, and I hope even more that I get corrected for any
misunderstandings I might have. :-)

i think i got the basic concept.
i didn't know you can use types in structural types.

about forsome:

if i understood that correctly, it covers the case where i simply omit
the type parameter in java because i don't care about it

Am 05.07.2011 21:56, schrieb Daniel Sobral:
> On Tue, Jul 5, 2011 at 16:06, HamsterofDeath wrote:
>> i lost track here:
>>
>> trait Monad[M[_]] {
>>
>> def unit[A](a: => A):M[A]
>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>> }
>>
>> and here:
>> ({type T[A] = State[S, A]})#T
> Structural type. Let's see a simple structural type:
>
> def [T <: { def close(): Unit }](list: List[T]) = list foreach (_.close())
>
> The structural type here is "{ def close(): Unit }" -- or any type
> whose structure includes a 0-arity method called "close" that returns
> Unit.
>
> So "{ type T[A] = State[S, A] }" is a structural type, where the
> abstract type T[A] is defined as being an alias for State[S, A]. Next,
> we put that inside () and put an #T afterwards. That means all
> subtypes T of the afore-mentioned structural type.
>
> To better understand it, consider this:
>
> scala> def f[M[_]](m: M[Int]) = m
> f: [M[_]](m: M[Int])M[Int]
>
> scala> f[List](List(1, 2, 3))
> res3: List[Int] = List(1, 2, 3)
>
> So f expects a type constructor M. Well, the T of the type we have
> been discussing is a type constructor as well -- from T[A] it produces
> a State[S, A]. Let's try to apply it here:
>
> scala> import scala.collection.generic.GenericTraversableTemplate
> import scala.collection.generic.GenericTraversableTemplate
>
> scala> f[({ type T[A] = GenericTraversableTemplate[A, List] })#T](List(1, 2, 3))
> res5: scala.collection.generic.GenericTraversableTemplate[Int,[+A]List[A]]
> = List(1, 2, 3)
>
> I used GenericTraversableTemplate because it's second parameter is a
> type constructor, as we require for this example. A
> GenericTraversableTemplate takes two parameters -- the first is the
> element type, just like in List. The second is the type constructor
> that's used in various methods. We could not use it directly with f:
>
> scala> f[GenericTraversableTemplate[_, List]](List(1,2 ,3))
> :12: error:
> scala.collection.generic.GenericTraversableTemplate[_, List] takes no
> type parameters, expected: one
>
> So, using that little trick, we created a type constructor T which was
> used to convert GenericTraversableTemplate from two parameters to a
> type constructor with one parameter -- the other having been bound to
> List.
>
>> and here:
>> "forSome"
> Existential type. I might be mistaken -- and the explanation probably
> has errors anyway --, but I think this is related to logic
> quantifiers. The types we are used to are universal quantifiers: if we
> say
>
> def f[T](lst: List[T]): Option[T] = lst.headOption
>
> We mean that for all T, lst will be of type List[T]. On the other
> hand, if we have:
>
> def f(lst: List[T] forSome { type T }): Boolean = lst.isEmpty
>
> We mean that there exists a type T, of which we know nothing about,
> for which the type of lst will be List[T].
>
> In particular, notice that we know precisely what's the T in the first
> example, so we can use it as a return type, but we know nothing about
> it in the second example -- but, as it happens, we don't need to.
>
>> i'm pretty sure it's awesome, but what is it?
> implicit val stateMonad = new Monad[({type T[A] = State[S, A] forSome
> {type S}})#T]
>
> We declare that stateMonad is a Monad (remember that Monad is trait
> Monad[M[_]] -- needs a type constructor) whose type parameter is a
> type constructor T[A], which constructs a State[S, A], where S is some
> type which we know nothing about (but that it exists :).
>
> I hope this helps, and I hope even more that I get corrected for any
> misunderstandings I might have. :-)
>

Currently, this is the best way to define a partially-applied type constructor in Scala
-> my brain made click. yes, that was the best way to explain it (for me)

about the monad:
"unit" wraps an A with an M, and "bind" converts the wrapped thing it into something else which is also wrapped?

the method names are pretty confusing, but i think i get it. i watched this:
http://vimeo.com/10482466
and it became pretty clear


Am 05.07.2011 21:49, schrieb Brian Maso:

HojfAfZO8r37v2GA-LjUEFT_XtLGnqfXCHQ3fw [at] mail [dot] gmail [dot] com" type="cite">

On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath <h-star [at] gmx [dot] de" rel="nofollow">h-star@gmx.de> wrote:

i lost track here:

trait Monad[M[_]] {

  def unit[A](a: => A):M[A]
  def bind[A, B](m:M[A], f:A => M[B]):M[B]
}

That's one representation of a Monad typeclass. The idea is they you would have one or more implicit concrete implementation available to be injected wherever you need monadic features for some container type "M[_]".

"unit" is the an abstraction for a constructor of the monad type.
"bind" is the abstraction which you probably know better as "flatMap" in Scala.
 

 
and here:
({type T[A] = State[S, A]})#T

Currently, this is the best way to define a partially-applied type constructor in Scala. That is, imagine a type constructor with two arguments T[A, B]. Now say you want to define a one-argument type constructor by providing a concrete binding for A -- e.g., you want to bind A to "Int". You would get a new type constructor with only a single argument: T2[B] = T[Int, B]. But in Scala you can't create new type constructors like that. Currently the only way to pull it off is using that ugly construct you see above.

That is:

"{type T2[A] = State[Int, A]}" defines an anonymous class with a single member: a 1-parameter type constructor named "T2". T2[A] is an alias for State[Int, A], where only State's second type parameter, "A", is unbound.

"({type T2[A] = State[Int, A]})#T2" is an explicit reference to the "T2" type constructor inside the anonymous class. The net effect is that you end up with a new type constructor, T2, that has one type argument, and which is equal to "State[A, B]" with "A" bound to "Int".
 

and here:
"forSome"

I know those are called "existential types", but honestly I don't use them and only have an intuitive sense of what they mean when I'm looking at code that uses them. Perhaps someone else can take a swing? or maybe Google can shed light for you if use search for "Scala existential type"?


--
Best regards,
Brian Maso
(949) 395-8551
Follow me: @bmaso
brian [at] blumenfeld-maso [dot] com" target="_blank" rel="nofollow">brian@blumenfeld-maso.com
 

i'm pretty sure it's awesome, but what is it?

Am 05.07.2011 18:45, schrieb Sébastien Bocq:

2011/7/5 Adriaan Moors <adriaan [dot] moors [at] epfl [dot] ch" target="_blank" rel="nofollow">adriaan.moors@epfl.ch>

On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq <sebastien [dot] bocq [at] gmail [dot] com" target="_blank" rel="nofollow">sebastien.bocq@gmail.com> wrote:

I know there are tricks, I merely wanted to point out that it can't be expressed as elegantly as in Haskell because the type system is less powerful.

it's not the type system, it's the type inferencer
we don't infer types like `({type T[A] = State[S, A]})#T` (that requires higher-order unification, which is a pending enhancement: https://issues.scala-lang.org/browse/SI-2712)
type inference is tuned for cases where a class type can be inferred, thus, this type checks:
trait Monad[M[_]] {   def unit[A](a: => A):M[A]   def bind[A, B](m:M[A], f:A => M[B]):M[B] }

trait StateMonad[A] extends Monad[StateMonad] { // key difference: now we have StateMonad as an available type to be inferred   type S   val runState: S => (S, A)   def unit[A](a: => A): StateMonad[A] = error("")   def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("") }    object Test {      implicit def stateMonad[S] = new Monad[StateMonad] {     def unit[A](a: => A): StateMonad[A] = error("")     def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]): StateMonad[B] = error("")   }      def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]): M[Unit] =     if (ms.isEmpty) m.unit(())     else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})      val move = new StateMonad[Unit]{type S = Int; val runState = {pos: S => (pos + 1, ())}}      val x = sequence(move, move) }

I know, I know, it's not as Haskelly. Maybe it can be made  openly extensible similar to what type classes offer, but I don't see how immediately...
adriaan

Yes, I should have said type inferencer. It's an interesting approach, I never saw it before.

Thanks for the explanation,
Sébastien

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

On 05/07/11 22:56, Jason Zaugg wrote:
> On Tue, Jul 5, 2011 at 2:30 PM, Sébastien Bocq
> wrote:
>> Here is an example for which I see no elegant solution in Scala.
>> Isn't this a limitation of Scala's type inference system?
>
>> class State[S, A](runState:S => (S, A))
>>
>> implicit val stateMonad = new Monad[({type T[A] = State[S, A]
>> forSome {type S}})#T] { ?? }
>
> Isn't this sufficient?
>
> implicit def stateMonad[S] = new Monad[({type T[A] = State[S,
> A]})#T] { // All good! }
>
> Missing type inference never limits what you can express, it only
> limits the brevity with which you can express it.
>
> -jason
In this case, you could also argue Scala does better in one respect.
While Haskell type-constructors are curried, making the above
expression much easier, you cannot rearrange (e.g. flip) them.

implicit def stateExpFunctor[A] = new ExpFunctor[({type T[S] =
State[S, A]})#T]

versus

newtype FlipState a s = FlipState (State s a)

instance Monad (FlipState a) where

... then wrapping/unwrapping

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

On 06/07/11 06:10, HamsterofDeath wrote:
> Currently, this is the best way to define a partially-applied type
> constructor in Scala -> my brain made click. yes, that was the best
> way to explain it (for me)
>
> about the monad: "unit" wraps an A with an M, and "bind" converts
> the wrapped thing it into something else which is also wrapped?
>
> the method names are pretty confusing, but i think i get it. i
> watched this: http://vimeo.com/10482466 and it became pretty clear
>
bind is often called "flatMap" in Scala.

See if this helps
http://blog.tmorris.net/what-does-monad-mean/

Chapter 6 of Scala In Depth covers all three of these, funny enough.

Just a quick note:  forSome is the longhand of _ in existential types ( or _ is the shorthand of forSome....). 

List[T] forSome { type T }
is equivalent to
List[_]

(assuming they are in the same location.)

The primary use cases I've had for structural types are
*  dealing with legacy Java code
* dealing abstractly with abstract types on traits.

trait Foo {
  type Bar <: Disposable
  def bar : Bar
}

val buffer = ArrayBuffer[x.Bar forSome { val x : Foo }]()

def add(x : Foo) {
  buffer.add(x)
}

notice the existential is a *val*.  The type of the buffer is one that only accepts Bar types on Foo values.  Quite a fun trick.

On Jul 5, 2011 4:10 PM, "HamsterofDeath" <h-star@gmx.de> wrote:
> Currently, this is the best way to define a partially-applied type
> constructor in Scala
> -> my brain made click. yes, that was the best way to explain it (for me)
>
> about the monad:
> "unit" wraps an A with an M, and "bind" converts the wrapped thing it
> into something else which is also wrapped?
>
> the method names are pretty confusing, but i think i get it. i watched this:
> http://vimeo.com/10482466
> and it became pretty clear
>
>
> Am 05.07.2011 21:49, schrieb Brian Maso:
>>
>>
>> On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath <h-star@gmx.de
>> <mailto:h-star@gmx.de>> wrote:
>>
>> i lost track here:
>>
>> trait Monad[M[_]] {
>>
>> def unit[A](a: => A):M[A]
>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>> }
>>
>>
>> That's one representation of a Monad typeclass. The idea is they you
>> would have one or more implicit concrete implementation available to
>> be injected wherever you need monadic features for some container type
>> "M[_]".
>>
>> "unit" is the an abstraction for a constructor of the monad type.
>> "bind" is the abstraction which you probably know better as "flatMap"
>> in Scala.
>>
>>
>>
>> and here:
>> ({type T[A] = State[S, A]})#T
>>
>>
>> Currently, this is the best way to define a partially-applied type
>> constructor in Scala. That is, imagine a type constructor with two
>> arguments T[A, B]. Now say you want to define a one-argument type
>> constructor by providing a concrete binding for A -- e.g., you want to
>> bind A to "Int". You would get a new type constructor with only a
>> single argument: T2[B] = T[Int, B]. But in Scala you can't create new
>> type constructors like that. Currently the only way to pull it off is
>> using that ugly construct you see above.
>>
>> That is:
>>
>> "{type T2[A] = State[Int, A]}" defines an anonymous class with a
>> single member: a 1-parameter type constructor named "T2". T2[A] is an
>> alias for State[Int, A], where only State's second type parameter,
>> "A", is unbound.
>>
>> "({type T2[A] = State[Int, A]})#T2" is an explicit reference to the
>> "T2" type constructor inside the anonymous class. The net effect is
>> that you end up with a new type constructor, T2, that has one type
>> argument, and which is equal to "State[A, B]" with "A" bound to "Int".
>>
>>
>>
>>
>> and here:
>> "forSome"
>>
>>
>> I know those are called "existential types", but honestly I don't use
>> them and only have an intuitive sense of what they mean when I'm
>> looking at code that uses them. Perhaps someone else can take a swing?
>> or maybe Google can shed light for you if use search for "Scala
>> existential type"?
>>
>>
>> --
>> Best regards,
>> Brian Maso
>> (949) 395-8551
>> Follow me: @bmaso
>> brian@blumenfeld-maso.com <mailto:brian@blumenfeld-maso.com>
>>
>>
>>
>>
>> i'm pretty sure it's awesome, but what is it?
>>
>>
>>
>>
>>
>> Am 05.07.2011 18:45, schrieb Sébastien Bocq:
>>>
>>>
>>> 2011/7/5 Adriaan Moors <adriaan.moors@epfl.ch
>>> <mailto:adriaan.moors@epfl.ch>>
>>>
>>>
>>>
>>> On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq
>>> <sebastien.bocq@gmail.com <mailto:sebastien.bocq@gmail.com>>
>>> wrote:
>>>
>>> I know there are tricks, I merely wanted to point out
>>> that it can't be expressed as elegantly as in Haskell
>>> because the type system is less powerful.
>>>
>>> it's not the type system, it's the type inferencer
>>>
>>> we don't infer types like `({type T[A] = State[S, A]})#T`
>>> (that requires higher-order unification, which is a pending
>>> enhancement: https://issues.scala-lang.org/browse/SI-2712)
>>>
>>> type inference is tuned for cases where a class type can be
>>> inferred, thus, this type checks:
>>>
>>> trait Monad[M[_]] {
>>> def unit[A](a: => A):M[A]
>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>>> }
>>>
>>>
>>> trait StateMonad[A] extends Monad[StateMonad] { // key
>>> difference: now we have StateMonad as an available type to be
>>> inferred
>>> type S
>>> val runState: S => (S, A)
>>> def unit[A](a: => A): StateMonad[A] = error("")
>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>> StateMonad[B] = error("")
>>> }
>>>
>>> object Test {
>>>
>>> implicit def stateMonad[S] = new Monad[StateMonad] {
>>> def unit[A](a: => A): StateMonad[A] = error("")
>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>> StateMonad[B] = error("")
>>> }
>>>
>>> def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]):
>>> M[Unit] =
>>> if (ms.isEmpty) m.unit(())
>>> else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})
>>>
>>> val move = new StateMonad[Unit]{type S = Int; val runState
>>> = {pos: S => (pos + 1, ())}}
>>>
>>> val x = sequence(move, move)
>>> }
>>>
>>>
>>> I know, I know, it's not as Haskelly. Maybe it can be made
>>> openly extensible similar to what type classes offer, but I
>>> don't see how immediately...
>>>
>>> adriaan
>>>
>>>
>>> Yes, I should have said type inferencer. It's an interesting
>>> approach, I never saw it before.
>>>
>>> Thanks for the explanation,
>>> Sébastien
>>
>>
>>
>>
>>
>

Perhaps I'm mistaking something here, but shouldn't that read:

def add(x : Foo) {
buffer.add(x.bar)
}

instead of

def add(x : Foo) {
buffer.add(x)
}

Regards,
Rüdiger

2011/7/6 Josh Suereth :
> Chapter 6 of Scala In Depth covers all three of these, funny enough.
>
> Just a quick note:  forSome is the longhand of _ in existential types ( or _
> is the shorthand of forSome....).
>
> List[T] forSome { type T }
> is equivalent to
> List[_]
>
> (assuming they are in the same location.)
>
> The primary use cases I've had for structural types are
> *  dealing with legacy Java code
> * dealing abstractly with abstract types on traits.
>
> trait Foo {
>   type Bar <: Disposable
>   def bar : Bar
> }
>
> val buffer = ArrayBuffer[x.Bar forSome { val x : Foo }]()
>
> def add(x : Foo) {
>   buffer.add(x)
> }
>
> notice the existential is a *val*.  The type of the buffer is one that only
> accepts Bar types on Foo values.  Quite a fun trick.
>
> On Jul 5, 2011 4:10 PM, "HamsterofDeath" wrote:
>> Currently, this is the best way to define a partially-applied type
>> constructor in Scala
>> -> my brain made click. yes, that was the best way to explain it (for me)
>>
>> about the monad:
>> "unit" wraps an A with an M, and "bind" converts the wrapped thing it
>> into something else which is also wrapped?
>>
>> the method names are pretty confusing, but i think i get it. i watched
>> this:
>> http://vimeo.com/10482466
>> and it became pretty clear
>>
>>
>> Am 05.07.2011 21:49, schrieb Brian Maso:
>>>
>>>
>>> On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath >> > wrote:
>>>
>>> i lost track here:
>>>
>>> trait Monad[M[_]] {
>>>
>>> def unit[A](a: => A):M[A]
>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>>> }
>>>
>>>
>>> That's one representation of a Monad typeclass. The idea is they you
>>> would have one or more implicit concrete implementation available to
>>> be injected wherever you need monadic features for some container type
>>> "M[_]".
>>>
>>> "unit" is the an abstraction for a constructor of the monad type.
>>> "bind" is the abstraction which you probably know better as "flatMap"
>>> in Scala.
>>>
>>>
>>>
>>> and here:
>>> ({type T[A] = State[S, A]})#T
>>>
>>>
>>> Currently, this is the best way to define a partially-applied type
>>> constructor in Scala. That is, imagine a type constructor with two
>>> arguments T[A, B]. Now say you want to define a one-argument type
>>> constructor by providing a concrete binding for A -- e.g., you want to
>>> bind A to "Int". You would get a new type constructor with only a
>>> single argument: T2[B] = T[Int, B]. But in Scala you can't create new
>>> type constructors like that. Currently the only way to pull it off is
>>> using that ugly construct you see above.
>>>
>>> That is:
>>>
>>> "{type T2[A] = State[Int, A]}" defines an anonymous class with a
>>> single member: a 1-parameter type constructor named "T2". T2[A] is an
>>> alias for State[Int, A], where only State's second type parameter,
>>> "A", is unbound.
>>>
>>> "({type T2[A] = State[Int, A]})#T2" is an explicit reference to the
>>> "T2" type constructor inside the anonymous class. The net effect is
>>> that you end up with a new type constructor, T2, that has one type
>>> argument, and which is equal to "State[A, B]" with "A" bound to "Int".
>>>
>>>
>>>
>>>
>>> and here:
>>> "forSome"
>>>
>>>
>>> I know those are called "existential types", but honestly I don't use
>>> them and only have an intuitive sense of what they mean when I'm
>>> looking at code that uses them. Perhaps someone else can take a swing?
>>> or maybe Google can shed light for you if use search for "Scala
>>> existential type"?
>>>
>>>
>>> --
>>> Best regards,
>>> Brian Maso
>>> (949) 395-8551
>>> Follow me: @bmaso
>>> brian@blumenfeld-maso.com
>>>
>>>
>>>
>>>
>>> i'm pretty sure it's awesome, but what is it?
>>>
>>>
>>>
>>>
>>>
>>> Am 05.07.2011 18:45, schrieb Sébastien Bocq:
>>>>
>>>>
>>>> 2011/7/5 Adriaan Moors >>> >
>>>>
>>>>
>>>>
>>>> On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq
>>>> >
>>>> wrote:
>>>>
>>>> I know there are tricks, I merely wanted to point out
>>>> that it can't be expressed as elegantly as in Haskell
>>>> because the type system is less powerful.
>>>>
>>>> it's not the type system, it's the type inferencer
>>>>
>>>> we don't infer types like `({type T[A] = State[S, A]})#T`
>>>> (that requires higher-order unification, which is a pending
>>>> enhancement: https://issues.scala-lang.org/browse/SI-2712)
>>>>
>>>> type inference is tuned for cases where a class type can be
>>>> inferred, thus, this type checks:
>>>>
>>>> trait Monad[M[_]] {
>>>> def unit[A](a: => A):M[A]
>>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>>>> }
>>>>
>>>>
>>>> trait StateMonad[A] extends Monad[StateMonad] { // key
>>>> difference: now we have StateMonad as an available type to be
>>>> inferred
>>>> type S
>>>> val runState: S => (S, A)
>>>> def unit[A](a: => A): StateMonad[A] = error("")
>>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>>> StateMonad[B] = error("")
>>>> }
>>>>
>>>> object Test {
>>>>
>>>> implicit def stateMonad[S] = new Monad[StateMonad] {
>>>> def unit[A](a: => A): StateMonad[A] = error("")
>>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>>> StateMonad[B] = error("")
>>>> }
>>>>
>>>> def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]):
>>>> M[Unit] =
>>>> if (ms.isEmpty) m.unit(())
>>>> else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})
>>>>
>>>> val move = new StateMonad[Unit]{type S = Int; val runState
>>>> = {pos: S => (pos + 1, ())}}
>>>>
>>>> val x = sequence(move, move)
>>>> }
>>>>
>>>>
>>>> I know, I know, it's not as Haskelly. Maybe it can be made
>>>> openly extensible similar to what type classes offer, but I
>>>> don't see how immediately...
>>>>
>>>> adriaan
>>>>
>>>>
>>>> Yes, I should have said type inferencer. It's an interesting
>>>> approach, I never saw it before.
>>>>
>>>> Thanks for the explanation,
>>>> Sébastien
>>>
>>>
>>>
>>>
>>>
>>
>

Yes, sorry.  I was typing that from my phone :)

On Wed, Jul 6, 2011 at 5:24 AM, Ruediger Keller <ruediger.keller@rk42.de> wrote:

Perhaps I'm mistaking something here, but shouldn't that read:

def add(x : Foo) {
 buffer.add(x.bar)
}

instead of

def add(x : Foo) {
 buffer.add(x)
}

Regards,
Rüdiger



2011/7/6 Josh Suereth <joshua.suereth@gmail.com>:
> Chapter 6 of Scala In Depth covers all three of these, funny enough.
>
> Just a quick note:  forSome is the longhand of _ in existential types ( or _
> is the shorthand of forSome....).
>
> List[T] forSome { type T }
> is equivalent to
> List[_]
>
> (assuming they are in the same location.)
>
> The primary use cases I've had for structural types are
> *  dealing with legacy Java code
> * dealing abstractly with abstract types on traits.
>
> trait Foo {
>   type Bar <: Disposable
>   def bar : Bar
> }
>
> val buffer = ArrayBuffer[x.Bar forSome { val x : Foo }]()
>
> def add(x : Foo) {
>   buffer.add(x)
> }
>
> notice the existential is a *val*.  The type of the buffer is one that only
> accepts Bar types on Foo values.  Quite a fun trick.
>
> On Jul 5, 2011 4:10 PM, "HamsterofDeath" <h-star@gmx.de> wrote:
>> Currently, this is the best way to define a partially-applied type
>> constructor in Scala
>> -> my brain made click. yes, that was the best way to explain it (for me)
>>
>> about the monad:
>> "unit" wraps an A with an M, and "bind" converts the wrapped thing it
>> into something else which is also wrapped?
>>
>> the method names are pretty confusing, but i think i get it. i watched
>> this:
>> http://vimeo.com/10482466
>> and it became pretty clear
>>
>>
>> Am 05.07.2011 21:49, schrieb Brian Maso:
>>>
>>>
>>> On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath <h-star@gmx.de
>>> <mailto:h-star@gmx.de>> wrote:
>>>
>>> i lost track here:
>>>
>>> trait Monad[M[_]] {
>>>
>>> def unit[A](a: => A):M[A]
>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>>> }
>>>
>>>
>>> That's one representation of a Monad typeclass. The idea is they you
>>> would have one or more implicit concrete implementation available to
>>> be injected wherever you need monadic features for some container type
>>> "M[_]".
>>>
>>> "unit" is the an abstraction for a constructor of the monad type.
>>> "bind" is the abstraction which you probably know better as "flatMap"
>>> in Scala.
>>>
>>>
>>>
>>> and here:
>>> ({type T[A] = State[S, A]})#T
>>>
>>>
>>> Currently, this is the best way to define a partially-applied type
>>> constructor in Scala. That is, imagine a type constructor with two
>>> arguments T[A, B]. Now say you want to define a one-argument type
>>> constructor by providing a concrete binding for A -- e.g., you want to
>>> bind A to "Int". You would get a new type constructor with only a
>>> single argument: T2[B] = T[Int, B]. But in Scala you can't create new
>>> type constructors like that. Currently the only way to pull it off is
>>> using that ugly construct you see above.
>>>
>>> That is:
>>>
>>> "{type T2[A] = State[Int, A]}" defines an anonymous class with a
>>> single member: a 1-parameter type constructor named "T2". T2[A] is an
>>> alias for State[Int, A], where only State's second type parameter,
>>> "A", is unbound.
>>>
>>> "({type T2[A] = State[Int, A]})#T2" is an explicit reference to the
>>> "T2" type constructor inside the anonymous class. The net effect is
>>> that you end up with a new type constructor, T2, that has one type
>>> argument, and which is equal to "State[A, B]" with "A" bound to "Int".
>>>
>>>
>>>
>>>
>>> and here:
>>> "forSome"
>>>
>>>
>>> I know those are called "existential types", but honestly I don't use
>>> them and only have an intuitive sense of what they mean when I'm
>>> looking at code that uses them. Perhaps someone else can take a swing?
>>> or maybe Google can shed light for you if use search for "Scala
>>> existential type"?
>>>
>>>
>>> --
>>> Best regards,
>>> Brian Maso
>>> (949) 395-8551
>>> Follow me: @bmaso
>>> brian@blumenfeld-maso.com <mailto:brian@blumenfeld-maso.com>
>>>
>>>
>>>
>>>
>>> i'm pretty sure it's awesome, but what is it?
>>>
>>>
>>>
>>>
>>>
>>> Am 05.07.2011 18:45, schrieb Sébastien Bocq:
>>>>
>>>>
>>>> 2011/7/5 Adriaan Moors <adriaan.moors@epfl.ch
>>>> <mailto:adriaan.moors@epfl.ch>>
>>>>
>>>>
>>>>
>>>> On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq
>>>> <sebastien.bocq@gmail.com <mailto:sebastien.bocq@gmail.com>>
>>>> wrote:
>>>>
>>>> I know there are tricks, I merely wanted to point out
>>>> that it can't be expressed as elegantly as in Haskell
>>>> because the type system is less powerful.
>>>>
>>>> it's not the type system, it's the type inferencer
>>>>
>>>> we don't infer types like `({type T[A] = State[S, A]})#T`
>>>> (that requires higher-order unification, which is a pending
>>>> enhancement: https://issues.scala-lang.org/browse/SI-2712)
>>>>
>>>> type inference is tuned for cases where a class type can be
>>>> inferred, thus, this type checks:
>>>>
>>>> trait Monad[M[_]] {
>>>> def unit[A](a: => A):M[A]
>>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>>>> }
>>>>
>>>>
>>>> trait StateMonad[A] extends Monad[StateMonad] { // key
>>>> difference: now we have StateMonad as an available type to be
>>>> inferred
>>>> type S
>>>> val runState: S => (S, A)
>>>> def unit[A](a: => A): StateMonad[A] = error("")
>>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>>> StateMonad[B] = error("")
>>>> }
>>>>
>>>> object Test {
>>>>
>>>> implicit def stateMonad[S] = new Monad[StateMonad] {
>>>> def unit[A](a: => A): StateMonad[A] = error("")
>>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>>>> StateMonad[B] = error("")
>>>> }
>>>>
>>>> def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]):
>>>> M[Unit] =
>>>> if (ms.isEmpty) m.unit(())
>>>> else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})
>>>>
>>>> val move = new StateMonad[Unit]{type S = Int; val runState
>>>> = {pos: S => (pos + 1, ())}}
>>>>
>>>> val x = sequence(move, move)
>>>> }
>>>>
>>>>
>>>> I know, I know, it's not as Haskelly. Maybe it can be made
>>>> openly extensible similar to what type classes offer, but I
>>>> don't see how immediately...
>>>>
>>>> adriaan
>>>>
>>>>
>>>> Yes, I should have said type inferencer. It's an interesting
>>>> approach, I never saw it before.
>>>>
>>>> Thanks for the explanation,
>>>> Sébastien
>>>
>>>
>>>
>>>
>>>
>>
>

Ok, thanks. I just wanted to make sure I'm not misunderstanding something. :-)

Regards,
Rüdiger

2011/7/6 Josh Suereth :
> Yes, sorry.  I was typing that from my phone :)
>
> On Wed, Jul 6, 2011 at 5:24 AM, Ruediger Keller
> wrote:
>>
>> Perhaps I'm mistaking something here, but shouldn't that read:
>>
>> def add(x : Foo) {
>>  buffer.add(x.bar)
>> }
>>
>> instead of
>>
>> def add(x : Foo) {
>>  buffer.add(x)
>> }
>>
>> Regards,
>> Rüdiger
>>
>>
>>
>> 2011/7/6 Josh Suereth :
>> > Chapter 6 of Scala In Depth covers all three of these, funny enough.
>> >
>> > Just a quick note:  forSome is the longhand of _ in existential types (
>> > or _
>> > is the shorthand of forSome....).
>> >
>> > List[T] forSome { type T }
>> > is equivalent to
>> > List[_]
>> >
>> > (assuming they are in the same location.)
>> >
>> > The primary use cases I've had for structural types are
>> > *  dealing with legacy Java code
>> > * dealing abstractly with abstract types on traits.
>> >
>> > trait Foo {
>> >   type Bar <: Disposable
>> >   def bar : Bar
>> > }
>> >
>> > val buffer = ArrayBuffer[x.Bar forSome { val x : Foo }]()
>> >
>> > def add(x : Foo) {
>> >   buffer.add(x)
>> > }
>> >
>> > notice the existential is a *val*.  The type of the buffer is one that
>> > only
>> > accepts Bar types on Foo values.  Quite a fun trick.
>> >
>> > On Jul 5, 2011 4:10 PM, "HamsterofDeath" wrote:
>> >> Currently, this is the best way to define a partially-applied type
>> >> constructor in Scala
>> >> -> my brain made click. yes, that was the best way to explain it (for
>> >> me)
>> >>
>> >> about the monad:
>> >> "unit" wraps an A with an M, and "bind" converts the wrapped thing it
>> >> into something else which is also wrapped?
>> >>
>> >> the method names are pretty confusing, but i think i get it. i watched
>> >> this:
>> >> http://vimeo.com/10482466
>> >> and it became pretty clear
>> >>
>> >>
>> >> Am 05.07.2011 21:49, schrieb Brian Maso:
>> >>>
>> >>>
>> >>> On Tue, Jul 5, 2011 at 12:06 PM, HamsterofDeath > >>> > wrote:
>> >>>
>> >>> i lost track here:
>> >>>
>> >>> trait Monad[M[_]] {
>> >>>
>> >>> def unit[A](a: => A):M[A]
>> >>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>> >>> }
>> >>>
>> >>>
>> >>> That's one representation of a Monad typeclass. The idea is they you
>> >>> would have one or more implicit concrete implementation available to
>> >>> be injected wherever you need monadic features for some container type
>> >>> "M[_]".
>> >>>
>> >>> "unit" is the an abstraction for a constructor of the monad type.
>> >>> "bind" is the abstraction which you probably know better as "flatMap"
>> >>> in Scala.
>> >>>
>> >>>
>> >>>
>> >>> and here:
>> >>> ({type T[A] = State[S, A]})#T
>> >>>
>> >>>
>> >>> Currently, this is the best way to define a partially-applied type
>> >>> constructor in Scala. That is, imagine a type constructor with two
>> >>> arguments T[A, B]. Now say you want to define a one-argument type
>> >>> constructor by providing a concrete binding for A -- e.g., you want to
>> >>> bind A to "Int". You would get a new type constructor with only a
>> >>> single argument: T2[B] = T[Int, B]. But in Scala you can't create new
>> >>> type constructors like that. Currently the only way to pull it off is
>> >>> using that ugly construct you see above.
>> >>>
>> >>> That is:
>> >>>
>> >>> "{type T2[A] = State[Int, A]}" defines an anonymous class with a
>> >>> single member: a 1-parameter type constructor named "T2". T2[A] is an
>> >>> alias for State[Int, A], where only State's second type parameter,
>> >>> "A", is unbound.
>> >>>
>> >>> "({type T2[A] = State[Int, A]})#T2" is an explicit reference to the
>> >>> "T2" type constructor inside the anonymous class. The net effect is
>> >>> that you end up with a new type constructor, T2, that has one type
>> >>> argument, and which is equal to "State[A, B]" with "A" bound to "Int".
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> and here:
>> >>> "forSome"
>> >>>
>> >>>
>> >>> I know those are called "existential types", but honestly I don't use
>> >>> them and only have an intuitive sense of what they mean when I'm
>> >>> looking at code that uses them. Perhaps someone else can take a swing?
>> >>> or maybe Google can shed light for you if use search for "Scala
>> >>> existential type"?
>> >>>
>> >>>
>> >>> --
>> >>> Best regards,
>> >>> Brian Maso
>> >>> (949) 395-8551
>> >>> Follow me: @bmaso
>> >>> brian@blumenfeld-maso.com
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> i'm pretty sure it's awesome, but what is it?
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> Am 05.07.2011 18:45, schrieb Sébastien Bocq:
>> >>>>
>> >>>>
>> >>>> 2011/7/5 Adriaan Moors > >>>> >
>> >>>>
>> >>>>
>> >>>>
>> >>>> On Tue, Jul 5, 2011 at 3:24 PM, Sébastien Bocq
>> >>>> >
>> >>>> wrote:
>> >>>>
>> >>>> I know there are tricks, I merely wanted to point out
>> >>>> that it can't be expressed as elegantly as in Haskell
>> >>>> because the type system is less powerful.
>> >>>>
>> >>>> it's not the type system, it's the type inferencer
>> >>>>
>> >>>> we don't infer types like `({type T[A] = State[S, A]})#T`
>> >>>> (that requires higher-order unification, which is a pending
>> >>>> enhancement: https://issues.scala-lang.org/browse/SI-2712)
>> >>>>
>> >>>> type inference is tuned for cases where a class type can be
>> >>>> inferred, thus, this type checks:
>> >>>>
>> >>>> trait Monad[M[_]] {
>> >>>> def unit[A](a: => A):M[A]
>> >>>> def bind[A, B](m:M[A], f:A => M[B]):M[B]
>> >>>> }
>> >>>>
>> >>>>
>> >>>> trait StateMonad[A] extends Monad[StateMonad] { // key
>> >>>> difference: now we have StateMonad as an available type to be
>> >>>> inferred
>> >>>> type S
>> >>>> val runState: S => (S, A)
>> >>>> def unit[A](a: => A): StateMonad[A] = error("")
>> >>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>> >>>> StateMonad[B] = error("")
>> >>>> }
>> >>>>
>> >>>> object Test {
>> >>>>
>> >>>> implicit def stateMonad[S] = new Monad[StateMonad] {
>> >>>> def unit[A](a: => A): StateMonad[A] = error("")
>> >>>> def bind[A, B](m: StateMonad[A], f:A => StateMonad[B]):
>> >>>> StateMonad[B] = error("")
>> >>>> }
>> >>>>
>> >>>> def sequence[M[_], A](ms: M[A]*)(implicit m: Monad[M]):
>> >>>> M[Unit] =
>> >>>> if (ms.isEmpty) m.unit(())
>> >>>> else m.bind(ms.head, {_:A => sequence(ms.tail:_*)(m)})
>> >>>>
>> >>>> val move = new StateMonad[Unit]{type S = Int; val runState
>> >>>> = {pos: S => (pos + 1, ())}}
>> >>>>
>> >>>> val x = sequence(move, move)
>> >>>> }
>> >>>>
>> >>>>
>> >>>> I know, I know, it's not as Haskelly. Maybe it can be made
>> >>>> openly extensible similar to what type classes offer, but I
>> >>>> don't see how immediately...
>> >>>>
>> >>>> adriaan
>> >>>>
>> >>>>
>> >>>> Yes, I should have said type inferencer. It's an interesting
>> >>>> approach, I never saw it before.
>> >>>>
>> >>>> Thanks for the explanation,
>> >>>> Sébastien
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>
>> >
>
>