"stream monad"

[Vlad Patryshev]

Just read this:

http://zenzike.com/posts/2010-10-21-streams-and-monad-laws

It shows, in pretty simple terms, that Scala implementation of Stream is not a monad.

It does flatten, but this flattening does not satisfy identity laws.

So maybe it's better to either delimit flattening to a Stream of finite lists, or just give it a proper name.

Just keep in mind, it's not a monad.

Do I have to provide more details?

Thanks,
-Vlad

[Rex Kerr]

If you've tracked down what the failing case is, can you post the counterexample?

For example, this works:

scala> lazy val threes: Stream[Int] = 1 #:: 2 #:: 3 #:: threes
threes: Stream[Int] = <lazy>

scala> val s = Seq(Stream.empty[Int], Stream(0, -1), threes)
s: Seq[Stream[Int]] = List(Stream(), Stream(0, ?), Stream(1, ?))

// Note--prevent hang by using `take`; this is enough to verify sequence is the same

scala> s.forall(si => si.take(15) == si.take(15).flatMap(i => Stream(i)))
res0: Boolean = true

Details matter, given that `Try` is not a monad in exceptional cases, and on purpose, because it is gratuitously unsafe otherwise.

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vlad Patryshev]

Hi Rex,

yes; as Nicolas Wu observed, the two identity laws should be observed. For the functor S representing Stream,

1. the composition of 

S[η[X]]: S[X] → S[S[X]]

and

m:S[S[X]] → S[X]

must be an identity

2.  the composition of 

η[S[X]]: S[X] → S[S[X]]

and

m:S[S[X]] → S[X]

must be an identity

The first axiom is a problem: in Scala streams, η[X](x: X) = continually(x)

If we lift it to S[X], we will have a stream of streams of constants - that is, the sequence x1,x2,... maps to (x1,x1,...),(x2,x2,...)...

It's okay, except that after flattening we will never reach the second constant; the first one (x1) will be repeating forever - according to Scala implementation.

But according to the first axiom, when flattened, it is supposed to be equal to the original stream, x1,x2,...

In the article I mentioned, the author suggested three methods of flattening; this one does not work; the other one (vertical) does not work either; the diagonal one does, but well, it's probably the worst one that we would want - jumping along the diagonal. But it's the only one that is monadic. 

Thanks,
-Vlad

[Rex Kerr]

Maybe I don't understand your notation, but if you are using `eta` for a random function, then the left identity for that function is

  Stream(x).flatMap(Stream.continually _) == Stream.continually(x)

which is true.

Also, I'm not sure these things are particularly well-defined for unbounded input, and if they are, the entire notion of sequencing unbounded inputs requires some additional mathematical work (e.g. isomorphism between elements and a set of size ℵ₁ ), after which you may or may not have a problem any more.

So, yes, if you view the Stream monad as attempting to be a monad with `pure` as `continually`, you have problems.  (Bigger problems than just flunking the monad laws.)  If Stream merely _allows_ unbounded operations, but `pure` is just the single element, you are on safer territory (at least for streams that are functionally identical to finite streams).

(Note that I call it `pure` instead of `return` because the latter, in a multiparadigm context, is almost as misleading as `def monad(x: X): Unit = println(s"Hahaha, $x")`.)

  --Rex

[Vlad Patryshev]

Hi Rex,

Sorry, I used a categorical notation.

In Scala, it would look like this:

val sx: Stream[X] = ...

sx.flatMap(Stream.continually _) 

which is definitely not sx.

The size is not ℵ₁, it's still ℵ0.

Of course we can try to define Stream to exclude infinite... but what is it? How would you define it then? List is a monad, but Stream is not List.

Thanks,
-Vlad

[Rex Kerr]

Stream is a List with lazy processing.  For finite inputs, they are the "same" monad.  (As is Vector, ArrayBuffer, etc. etc..)  The only difference is implementation.

For infinite inputs, Stream is lazy, which has different non-termination properties.  Thus, if `f` produces an unbounded result, `ls flatMap f` does not terminate (right there) if ls is a list, while `ss flatMap f` does.  (And because they're not actually the same `f`, just analogous, List and Stream both obey identity.)

Anyway, you can try to use Stream as the unbounded repeat monad, but as you point out, flatMap doesn't obey identity.

Also, I know ℕ×ℕ has cardinality ℵ₀, but Scala's Stream has fold, which means you have to deal with the cardinality of ℕ^ℕ.  And, actually, you can repeat that, so I think you get all the infinite cardinals.  Kind of a mess when dealing with an actually finite system.

  --Rex

[Alec Zorab]

Wait, why have we decided that `continually` is return for `Stream`?

val sx: Stream[X] = ...

sx.flatMap(Stream(_))

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Rex Kerr]

That's what I said!  (But one can still think about the case where it is.)

  --Rex

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

[Alec Zorab]

If you want to use `Stream.continually` as your `A => F[A]`, you can't build a monad for the reason that you can't make a satisfactory `join`.

You can make a splendidly useful Applicative Functor though, which gives you elementwise zipping of Streams.

But there's definitely a perfectly good Monad on Stream, with `Stream(_)` and `_.flatten` giving you your `pure` and `join` functions

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Vlad Patryshev]

Ok, Alec, can you then give a full definition of this functor/monad?

Thanks,
-Vlad

On Tue, Aug 16, 2016 at 3:22 AM, Alec Zorab <alec...@gmail.com> wrote:

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

[Vlad Patryshev]

Oh, and if Stream is defined as a List, then what is Stream.head? A function? In which category? Some Kleisli?

I'm totally confused now. Anybody?

Thanks,
-Vlad

[Rex Kerr]

Stream has a monad: the same one List has, as you can use a Stream like a List (in the domain where you have no nontermination issues).

Stream almost has a second monad (the infinite repeat one), but flatMap doesn't work.  One could define another monad with pure = Stream.continually, flatten = diag, if there was an implementation of diag.

Stream has a bunch of other stuff that isn't monadic, and not all of it is best understood in terms of category theory.  `head` throws exceptions when there is no head, but otherwise it's comonad-like.  I haven't checked whether it obeys the comonad laws.

I'm not sure why this is confusing, given that every class with a Monad in Scala also has stuff not expressible via that monad.

  --Rex

[Alec Zorab]

implicit object StreamInstance extends Monad[Stream] {

  def pure[A](a: A) : Stream[A] = Stream(a)

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

  def join(ffa: Stream[Stream[A]]) : Stream[A] = ffa.flatten

}

Rex has already addressed your comments on Stream.head.

nb. Scala's stream is pretty much Haskell's List, so if you've found a proof that it's not monadic, you're going to upset a lot of haskellers.

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Vlad Patryshev]

Seems like my view is kind of simple. If something cannot be formulated categorically, it's under suspicion.

E.g. if we allow throwing exceptions, it's okay, but we have to define the category we are in. Probably functions with exceptions - that's a Kleisli category for Exception monad.

You seem to suggest to define Stream[X] as List[X]+(N=>X) (where N is the type of natural numbers). Cool; but I'm having hard time trying to define flattening on this union; and we need to prove that it's associative. On the other hand, seems like singleton is a good candidate for pure.

The expression "has a monad" sounds weird. Do you mean, has a pair (pure, flatten) that satisfy monadic laws?

Thanks,
-Vlad

[Vlad Patryshev]

I would not say I care about haskellers; they probably know by now that not only their lazy infinite lists are not a monad, but also Hask is not a category.

It's okay, the world is moving on. It's better to correct the mistakes of the past.

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

[Rex Kerr]

Yes, I mean "has a pair (pure, flatMap) (or equivalently a trio (pure, map, join)) that satisfy monadic laws".  Stream really could have two, the natural one (List-like) and the infinite repeat one (with join being diag, and map being the same in both).

I've never found a nice way of talking about nontermination properties with category theory.  (Nor algorithmic complexity.)

Anyway, I'm just pointing out that Stream and List have different nontermination properties, not saying that it is literally List[X] + anything (and certainly not N => X).

And yes there's an isomorphism between throwing exceptions and other stuff, and no, I don't normally find that illuminating (except inasmuch as it indicates that you can potentially catch the exception and replace the good branch with some sum type that represents the failure).

  --Rex

[Vlad Patryshev]

Ok, so it seems like everything's clear now, except that formally defining infinite lists is still kind of a problem.

Thanks,
-Vlad

[Alec Zorab]

List[A] = () \/ (A, List[A])

What's the issue?

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Bardur Arantsson]

On 2016-08-17 00:48, Alec Zorab wrote:
> implicit object StreamInstance extends Monad[Stream] {
> def pure[A](a: A) : Stream[A] = Stream(a)
> def map[A, B](fa: Stream[A], f: A => B) : Stream[B] = fa map f
> def join(ffa: Stream[Stream[A]]) : Stream[A] = ffa.flatten
> }
>
> Rex has already addressed your comments on Stream.head.
>
> nb. Scala's stream is pretty much Haskell's List, so if you've found a
> proof that it's not monadic, you're going to upset a lot of haskellers.

The Haskell List monad is known to be suboptimal:

https://wiki.haskell.org/ListT_done_right

Obiously these things may not necessarily apply in Scala, but I think
the "unnecessarily strict" bit may apply?

Regards,

[Vlad Patryshev]

:) This does not look like a definition to me. It's an equation, and the existence of a solution may be questionable.

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

[Alec Zorab]

In what way do you consider the definition of infinite lists to be problematic? If you take issue with, e.g. intensional definitions of sets, then I can see how you might dislike infinite lists. Otherwise, I don't think I see your objection?

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Vlad Patryshev]

:) Say, we are in the category of finite sets. Are your lists still infinite? Do they even exist? I mean, is there a solution to this recursive equation?

In another category, Kleene star, if it exists, may be one of the solutions for the recursive definition. Are you sure it defines infinite lists?

Okay, throw in countable lists; so it is X*+(N=>X), it's another solution. Is it the only one? No way; if we are in Sets, there may be much more linear orders serving as list domains. We may need AC.

I got a feeling that in all this discussion a very specific, unique category, is implied. What category is it?

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

Thanks,
-Vlad

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

[Roland Kuhn]

As a bystander I cannot help but ask myself: what exactly is it that is being discussed here? I re-read the original post which refers to some rather obscure article about Haskell.

Could someone give an example of a programming situation in Scala (which includes the JVM as part of its context) in which this particularly fine distinction of categories actually matters?

Regards,

Roland

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.

[Vlad Patryshev]

Roland,

Here's my interpretation.

1. There was lately a question raised whether Stream is a comonad or a monad. Turned out it depends on the definition.

2. I looked it up in Haskell; in Haskell Stream[X} is defined, roughly speaking, as N => X (where N is natural numbers. 

3. With this definition, there's no reasonable flattening defined for a list, as described in an article referenced earlier.

4. Rex pointed out that Haskell's definition is no good for Scala; so Scala's lists include empty, finite, and infinite lists.

5. For instance, `pure` is just a singleton, and `flatten` is the usual list flattening (elements of the first, then elements of the second, etc).

6. I tried to define them formally (as X*+(N=>X)), but it seems like nobody agreed with me on this (so I'm confused now).

7. I also tried to figure out whether this definition is formalizable in a category; so far no progress.

8. Rex suggested to use the recursive definition of type List[X].

9. I failed to find a categorical interpretation of this definition, proof of its existence or proof of its uniqueness (it's kind of obvious to me that it's not unique).

So here we are now. I'm getting more and more a feeling that formal foundations are kind of lacking here. Meaning that counting on categorical properties of monads does not make sense until we can't even define the category.

Regarding what really matters, tastes vary; I kind of believe that to program, e.g. a pacemaker, one better should have a formally provable piece of code: life matters. But nothing matters except development speed when we are slapping together a prototype web application.

Thanks,
-Vlad

[Rex Kerr]

Roland--it's a pretty obscure issue; maybe better on scala-debate or something else rather than here.  But it's not a *completely* obscure issue, because people have done a lot of work figuring out clever ways to utilize monads.  If you have a monad on some data structure, it opens up a lot of powerful abstractions.  If you don't, it may not.  If you don't but you think you do, you could have ugly corner cases lurking there where things randomly and weirdly fail because the invariants you think you have do not apply.

Vlad--on reflection, I agree that Stream[A] is--not counting lazy evaluation properties--equivalent to List[A] | (N => A), where N is a natural number.  However, the monad used for Stream is the same on as used for List, namely the single element.  This obeys the monad laws for the List[A]-behaving part of the domain, and AFAIK also does for the infinite part save that anything that gives nontermination on a finite machine is considered equivalent as long as it still fails to terminate.

As a practical matter, you're more likely to run into issues due to the tension between a conceptually infinite Stream and a `length` method that assumes Int.MaxValue as an upper bound than you are to any corner cases regarding the monadicity of the behavior with unbounded Streams.

(There have been a number of bugs where infinite streams would hang instead of give a sensible result, but these were _not_ due to an improper definition of the monad for streams, but rather due to implementations that were too eager (and implemented an operation that isn't one of the standard monadic ones).)

  --Rex

[Alexandru Nedelcu]

Hi Vlad,

I'm not a mathematician and I don't know Haskell, but Scala's List is
not finite, only our RAM memory and CPU capacity is. The only difference
between Scala's List and Stream is the evaluation model of that tail.
Besides the evaluation model of the tail, there is no other difference.
And yes, it's probably provable that List.continually wouldn't be that
helpful. Well first of all it would never finish. But hey, that's in the
halting problem's territory.

I'm way over my head here, please don't laugh :-)

As for the Monad, I think pretty much anybody expects "pure" to be
"Stream.apply" and not "continually", just like for numbers people think
first of addition and not multiplication. There's also an important
distinction to make here. Scala's Stream does not have the behavior of
Haskell's Stream. First of all, their Stream is probably lazy in the
head.

If the Haskell folks chose "continually" as being "pure" (have no idea
if they did or didn't, I don't know Haskell yet), remember that
Haskell's type-classes have that slightly annoying and sometimes helpful
"coherence" property, meaning that you can't define two instances of a
type-class for the same type.

But that's also limiting. After all, what defines a Monad or a Monoid or
whatever is the set of operations defined on a domain of definition, not
the domain of definition itself, and for example natural numbers have
about 3 Monoid definitions that I know about.

The set of natural numbers isn't a Monoid. The addition operation on
natural numbers (along with zero) is. Similarly, it's not Stream that's
the Monad, but Stream.flatMap + Stream.apply.

And that's an important distinction to make.

Cheers,

>> <mailto:vpatr...@gmail.com>>:

>> <vpatr...@gmail.com <mailto:vpatr...@gmail.com>>

>> <mailto:vpatr...@gmail.com>> wrote:
>>
>> Seems like my view is kind of simple. If
>> something cannot be formulated
>> categorically, it's under suspicion.
>>
>> E.g. if we allow throwing exceptions, it's
>> okay, but we have to define the category
>> we are in. Probably functions with
>> exceptions - that's a Kleisli category for
>> Exception monad.
>>
>> You seem to suggest to define Stream[X] as
>> List[X]+(N=>X) (where N is the type of
>> natural numbers). Cool; but I'm having
>> hard time trying to define flattening on
>> this union; and we need to prove that it's
>> associative. On the other hand, seems like
>> singleton is a good candidate for pure.
>>
>> The expression "has a monad" sounds weird.
>> Do you mean, has a pair (pure, flatten)
>> that satisfy monadic laws?
>>
>> Thanks,
>> -Vlad
>>
>> On Tue, Aug 16, 2016 at 3:31 PM, Rex Kerr
>> <ich...@gmail.com

>> <mailto:vpatr...@gmail.com>> wrote:
>>
>> Oh, and if Stream is defined as a
>> List, then what is Stream.head? A
>> function? In which category? Some
>> Kleisli?
>>
>> I'm totally confused now. Anybody?
>>
>> Thanks,
>> -Vlad
>>
>> On Tue, Aug 16, 2016 at 2:17 PM,
>> Vlad Patryshev
>> <vpatr...@gmail.com

>> <mailto:vpatr...@gmail.com>> wrote:
>>
>> Ok, Alec, can you then give a
>> full definition of this
>> functor/monad?
>>
>>
>>
>> Thanks,
>> -Vlad
>>
>> On Tue, Aug 16, 2016 at 3:22
>> AM, Alec Zorab
>> <alec...@gmail.com

>> <mailto:alec...@gmail.com>>

>> wrote:
>>
>> Wait, why have we decided
>> that `continually` is
>> return for `Stream`?
>>
>> val sx: Stream[X] = ...
>> sx.flatMap(Stream(_))
>>
>> On Tue, 16 Aug 2016 at
>> 05:50 Rex Kerr
>> <ich...@gmail.com

>> <mailto:vpatr...@gmail.com>>

>> <mailto:ich...@gmail.com>>

>> <mailto:vpatr...@gmail.com>>

>> <mailto:ich...@gmail.com>>

>> <mailto:vpatr...@gmail.com>>

>> scala-user+...@googlegroups.com
>> <mailto:scala-user+...@googlegroups.com>.

>> For more
>> options,
>> visit
>> https://groups.google.com/d/optout

>> <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>
>> --
>> You received this
>> message because you
>> are subscribed to the
>> Google Groups
>> "scala-user" group.
>> To unsubscribe from
>> this group and stop
>> receiving emails from
>> it, send an email to

>> scala-user+...@googlegroups.com
>> <mailto:scala-user+...@googlegroups.com>.

>> For more options,
>> visit
>> https://groups.google.com/d/optout

>> <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>> --
>> You received this message because you are
>> subscribed to the Google Groups
>> "scala-user" group.
>> To unsubscribe from this group and stop
>> receiving emails from it, send an email to

>> scala-user+...@googlegroups.com
>> <mailto:scala-user+...@googlegroups.com>.

>> For more options, visit
>> https://groups.google.com/d/optout

>> <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "scala-user" group.
>> To unsubscribe from this group and stop receiving emails from it,

>> send an email to scala-user+...@googlegroups.com
>> <mailto:scala-user+...@googlegroups.com>.

>> For more options, visit https://groups.google.com/d/optout

>> <https://groups.google.com/d/optout>.

>
>
> --
> You received this message because you are subscribed to the Google
> Groups "scala-user" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to scala-user+...@googlegroups.com
> <mailto:scala-user+...@googlegroups.com>.

[Oliver Ruebenacker]

     Hello,

  I would love to see a piece of actual code together with an explanation on how the fact that something is a Monad or of this or that category gives an insight into the code one could not have as easily gained by other means.

  Thanks!

     Best, Oliver

>>                                                                     scala-user+unsubscribe@googlegroups.com

>>                                                                     <mailto:scala-user+unsub...@googlegroups.com>.

>>                                                                     For more
>>                                                                     options,
>>                                                                     visit
>>                                                                     https://groups.google.com/d/optout
>>                                                                     <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>
>>                                                 --
>>                                                 You received this
>>                                                 message because you
>>                                                 are subscribed to the
>>                                                 Google Groups
>>                                                 "scala-user" group.
>>                                                 To unsubscribe from
>>                                                 this group and stop
>>                                                 receiving emails from
>>                                                 it, send an email to

>>                                                 scala-user+unsubscribe@googlegroups.com
>>                                                 <mailto:scala-user+unsub...@googlegroups.com>.

>>                                                 For more options,
>>                                                 visit
>>                                                 https://groups.google.com/d/optout
>>                                                 <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>                             --
>>                             You received this message because you are
>>                             subscribed to the Google Groups
>>                             "scala-user" group.
>>                             To unsubscribe from this group and stop
>>                             receiving emails from it, send an email to

>>                             scala-user+unsubscribe@googlegroups.com
>>                             <mailto:scala-user+unsub...@googlegroups.com>.

>>                             For more options, visit
>>                             https://groups.google.com/d/optout
>>                             <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>     --
>>     You received this message because you are subscribed to the Google
>>     Groups "scala-user" group.
>>     To unsubscribe from this group and stop receiving emails from it,

>>     send an email to scala-user+unsubscribe@googlegroups.com
>>     <mailto:scala-user+unsub...@googlegroups.com>.

>>     For more options, visit https://groups.google.com/d/optout
>>     <https://groups.google.com/d/optout>.

>
>
> --
> You received this message because you are subscribed to the Google
> Groups "scala-user" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to scala-user+unsubscribe@googlegroups.com
> <mailto:scala-user+unsub...@googlegroups.com>.

> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Oliver Ruebenacker

Senior Software Engineer, Diabetes Portal, Broad Institute

[Rex Kerr]

It's hard to give a concise example because it works particularly well precisely when the thing is a big hairy mess. Suppose you have

  dbAugmentedUserFields.smoosh{ field =>

    if (field.hasFriends) field.friendSet

    else field.soloSet
  }

and you have no idea whether these things form a monad.  Is this code correct?  Does it even make sense?  Who knows!

If you know that (solo, smoosh) are a monad for AugmentedUserFields, and correspond to (pure, bind) or equivalently (single-arg constructor, flatMap), you can rule out a lot of craziness like if you have one field with no friends and you use this to try to expand the set of fields, you'll end up with some totally different set of fields.

Of course if you don't know it's a monad, and you have to figure out/verify its properties, you'll very likely understand them without needing to know its monadicity an explicit step along the way (unless you're so used to doing things that way that that's always where you start).

In that sense it's just like any other API that makes guarantees.  You see something that implements a trait, and then you know something about what it should do.  The only special thing about monads is that the pure/flatMap set of functionality ends up actually being extremely powerful: very often if you want to talk about a thing that is container-like or property-like and you want to do some sort of operations in that context, the only (or primary) API you need is the one for Monad.  And because a single thing can act monadically in many different ways, you can't _just_ have single trait for it and always use the trait.

Naming some obvious properties that you use all the time anyway has the advantage of allowing one to communicate quickly whether some new thing also has those obvious properties (and discourages certain types of confusing "cleverness").  When it becomes more work to learn and keep track of the names than just to state the properties, then you've gone too far; and when you use peculiar names for historical reasons instead of ones that are a better mnemonic, you may also have gone too far.  (Like "Kestrel combinator".  Goodness.  This has nothing to do with anything you might want to know: a letter chosen arbitrarily which was humorously expanded in an influential book to the name of a bird.  Any name like "peek", "sideEffect", "tap", "aside", "parenthetically", "tangent", etc. would be better.  It just means "keep what you started with, but you have a chance to do something based on its value if you want".)

It's a bit unfortunate that the not-very-friendly name "monad" was chosen for the name of this property instead of "OpBox" or something.  It's basically a box of some sort that lets you apply operations to the contents without having to (explicitly) unwrap it (or even necessarily being able to unwrap it).

  --Rex

>>                                                                     <mailto:scala-user+unsubscribe...@googlegroups.com>.

>>                                                                     For more
>>                                                                     options,
>>                                                                     visit
>>                                                                     https://groups.google.com/d/optout
>>                                                                     <https://groups.google.com/d/optout>.
>>
>>
>>
>>
>>
>>
>>
>>                                                 --
>>                                                 You received this
>>                                                 message because you
>>                                                 are subscribed to the
>>                                                 Google Groups
>>                                                 "scala-user" group.
>>                                                 To unsubscribe from
>>                                                 this group and stop
>>                                                 receiving emails from
>>                                                 it, send an email to
>>                                                 scala-user+unsubscribe@googlegroups.com

>>                                                 <mailto:scala-user+unsubscribe...@googlegroups.com>.

>>                                                 For more options,
>>                                                 visit
>>                                                 https://groups.google.com/d/optout
>>                                                 <https://groups.google.com/d/optout>.
>>
>>
>>
>>
>>
>>
>>                             --
>>                             You received this message because you are
>>                             subscribed to the Google Groups
>>                             "scala-user" group.
>>                             To unsubscribe from this group and stop
>>                             receiving emails from it, send an email to
>>                             scala-user+unsubscribe@googlegroups.com

>>                             <mailto:scala-user+unsubscribe...@googlegroups.com>.

>>                             For more options, visit
>>                             https://groups.google.com/d/optout
>>                             <https://groups.google.com/d/optout>.
>>
>>
>>
>>
>>
>>
>>     --
>>     You received this message because you are subscribed to the Google
>>     Groups "scala-user" group.
>>     To unsubscribe from this group and stop receiving emails from it,
>>     send an email to scala-user+unsubscribe@googlegroups.com

>>     <mailto:scala-user+unsubscribe...@googlegroups.com>.

>>     For more options, visit https://groups.google.com/d/optout
>>     <https://groups.google.com/d/optout>.
>
>
> --
> You received this message because you are subscribed to the Google
> Groups "scala-user" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to scala-user+unsubscribe@googlegroups.com

> <mailto:scala-user+unsubscribe@googlegroups.com>.

> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vlad Patryshev]

Alexandru,

It's a little bit more sophisticated with monads compared to monoids.

But anyway, yes, it seems like streams in Scala and streams in Haskell are two very different things.

And since, yes, theoretically a Scala list can be infinite; so the regular definition, A*, is no good.

With all this, Scala stream is not a comonad; Haskell stream, probably, is.

How monadic can be Scala stream or Scala list, one has to check; I'm trying to work on it, but it's not so simple.

There probably are conceptual consequences of the fact that our streams are not comonads.

Thanks,
-Vlad

>>     <mailto:vpatr...@gmail.com>>:

>>
>>     :) Say, we are in the category of finite sets. Are your lists
>>     still infinite? Do they even exist? I mean, is there a solution to
>>     this recursive equation?
>>
>>     In another category, Kleene star, if it exists, may be one of the
>>     solutions for the recursive definition. Are you sure it defines
>>     infinite lists?
>>
>>     Okay, throw in countable lists; so it is X*+(N=>X), it's another
>>     solution. Is it the only one? No way; if we are in Sets, there may
>>     be much more linear orders serving as list domains. We may need AC.
>>
>>     I got a feeling that in all this discussion a very specific,
>>     unique category, is implied. What category is it?
>>
>>     Thanks,
>>     -Vlad
>>
>>     On Wed, Aug 17, 2016 at 1:37 AM, Alec Zorab <alec...@gmail.com

>>     <mailto:alec...@gmail.com>> wrote:
>>
>>         In what way do you consider the definition of infinite lists
>>         to be problematic? If you take issue with, e.g. intensional
>>         definitions of sets, then I can see how you might dislike
>>         infinite lists. Otherwise, I don't think I see your objection?
>>
>>         On Wed, 17 Aug 2016 at 02:40 Vlad Patryshev

>>         <vpatr...@gmail.com <mailto:vpatr...@gmail.com>> wrote:
>>
>>             :) This does not look like a definition to me. It's an
>>             equation, and the existence of a solution may be questionable.
>>
>>             Thanks,
>>             -Vlad
>>
>>             On Tue, Aug 16, 2016 at 6:00 PM, Alec Zorab

>>             <alec...@gmail.com <mailto:alec...@gmail.com>> wrote:
>>
>>                 List[A] = () \/ (A, List[A])
>>
>>                 What's the issue?
>>
>>
>>                 On Wed, 17 Aug 2016, 01:18 Vlad Patryshev,

>>                 <vpatr...@gmail.com <mailto:vpatr...@gmail.com>>

>>                 wrote:
>>
>>                     Ok, so it seems like everything's clear now,
>>                     except that formally defining infinite lists is
>>                     still kind of a problem.
>>
>>                     Thanks,
>>                     -Vlad
>>
>>                     On Tue, Aug 16, 2016 at 4:37 PM, Rex Kerr

>>                     <ich...@gmail.com <mailto:ich...@gmail.com>> wrote:
>>
>>                         Yes, I mean "has a pair (pure, flatMap) (or
>>                         equivalently a trio (pure, map, join)) that
>>                         satisfy monadic laws".  Stream really could
>>                         have two, the natural one (List-like) and the
>>                         infinite repeat one (with join being diag, and
>>                         map being the same in both).
>>
>>                         I've never found a nice way of talking about
>>                         nontermination properties with category
>>                         theory.  (Nor algorithmic complexity.)
>>
>>                         Anyway, I'm just pointing out that Stream and
>>                         List have different nontermination properties,
>>                         not saying that it is literally List[X] +
>>                         anything (and certainly not N => X).
>>
>>                         And yes there's an isomorphism between
>>                         throwing exceptions and other stuff, and no, I
>>                         don't normally find that illuminating (except
>>                         inasmuch as it indicates that you can
>>                         potentially catch the exception and replace
>>                         the good branch with some sum type that
>>                         represents the failure).
>>
>>                           --Rex
>>
>>                         On Tue, Aug 16, 2016 at 4:18 PM, Vlad
>>                         Patryshev <vpatr...@gmail.com

>>                         <mailto:vpatr...@gmail.com>> wrote:
>>
>>                             Seems like my view is kind of simple. If
>>                             something cannot be formulated
>>                             categorically, it's under suspicion.
>>
>>                             E.g. if we allow throwing exceptions, it's
>>                             okay, but we have to define the category
>>                             we are in. Probably functions with
>>                             exceptions - that's a Kleisli category for
>>                             Exception monad.
>>
>>                             You seem to suggest to define Stream[X] as
>>                             List[X]+(N=>X) (where N is the type of
>>                             natural numbers). Cool; but I'm having
>>                             hard time trying to define flattening on
>>                             this union; and we need to prove that it's
>>                             associative. On the other hand, seems like
>>                             singleton is a good candidate for pure.
>>
>>                             The expression "has a monad" sounds weird.
>>                             Do you mean, has a pair (pure, flatten)
>>                             that satisfy monadic laws?
>>
>>                             Thanks,
>>                             -Vlad
>>
>>                             On Tue, Aug 16, 2016 at 3:31 PM, Rex Kerr
>>                             <ich...@gmail.com

>>                                 <mailto:vpatr...@gmail.com>> wrote:
>>
>>                                     Oh, and if Stream is defined as a
>>                                     List, then what is Stream.head? A
>>                                     function? In which category? Some
>>                                     Kleisli?
>>
>>                                     I'm totally confused now. Anybody?
>>
>>                                     Thanks,
>>                                     -Vlad
>>
>>                                     On Tue, Aug 16, 2016 at 2:17 PM,
>>                                     Vlad Patryshev
>>                                     <vpatr...@gmail.com

>>                                     <mailto:vpatr...@gmail.com>> wrote:
>>
>>                                         Ok, Alec, can you then give a
>>                                         full definition of this
>>                                         functor/monad?
>>
>>
>>
>>                                         Thanks,
>>                                         -Vlad
>>
>>                                         On Tue, Aug 16, 2016 at 3:22
>>                                         AM, Alec Zorab
>>                                         <alec...@gmail.com

>>                                         <mailto:alec...@gmail.com>>

>>                                         wrote:
>>
>>                                             Wait, why have we decided
>>                                             that `continually` is
>>                                             return for `Stream`?
>>
>>                                             val sx: Stream[X] = ...
>>                                             sx.flatMap(Stream(_))
>>
>>                                             On Tue, 16 Aug 2016 at
>>                                             05:50 Rex Kerr
>>                                             <ich...@gmail.com

>>                                                 <mailto:vpatr...@gmail.com>>

>>                                                     <mailto:ich...@gmail.com>>

>>                                                         <mailto:vpatr...@gmail.com>>

>>                                                             <mailto:ich...@gmail.com>>

>>                                                                 <mailto:vpatr...@gmail.com>>

>>                                                                     <mailto:scala-user+unsub...@googlegroups.com>.

>>                                                                     For more
>>                                                                     options,
>>                                                                     visit
>>                                                                     https://groups.google.com/d/optout

>>                                                                     <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>
>>                                                 --
>>                                                 You received this
>>                                                 message because you
>>                                                 are subscribed to the
>>                                                 Google Groups
>>                                                 "scala-user" group.
>>                                                 To unsubscribe from
>>                                                 this group and stop
>>                                                 receiving emails from
>>                                                 it, send an email to
>>                                                 scala-user+unsubscribe@googlegroups.com

>>                                                 <mailto:scala-user+unsub...@googlegroups.com>.

>>                                                 For more options,
>>                                                 visit
>>                                                 https://groups.google.com/d/optout

>>                                                 <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>                             --
>>                             You received this message because you are
>>                             subscribed to the Google Groups
>>                             "scala-user" group.
>>                             To unsubscribe from this group and stop
>>                             receiving emails from it, send an email to
>>                             scala-user+unsubscribe@googlegroups.com

>>                             <mailto:scala-user+unsub...@googlegroups.com>.

>>                             For more options, visit
>>                             https://groups.google.com/d/optout

>>                             <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>     --
>>     You received this message because you are subscribed to the Google
>>     Groups "scala-user" group.
>>     To unsubscribe from this group and stop receiving emails from it,
>>     send an email to scala-user+unsubscribe@googlegroups.com

>>     <mailto:scala-user+unsub...@googlegroups.com>.

>>     For more options, visit https://groups.google.com/d/optout

>>     <https://groups.google.com/d/optout>.

>
>
> --
> You received this message because you are subscribed to the Google
> Groups "scala-user" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to scala-user+unsubscribe@googlegroups.com

> <mailto:scala-user+unsub...@googlegroups.com>.

[Alec Zorab]

Haskell streams can be empty, so they can't be comonadic

>>                                                                     scala-user+...@googlegroups.com

>>                                                                     <mailto:scala-user+...@googlegroups.com>.

>>                                                                     For more
>>                                                                     options,
>>                                                                     visit
>>                                                                     https://groups.google.com/d/optout

>>                                                                     <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>
>>                                                 --
>>                                                 You received this
>>                                                 message because you
>>                                                 are subscribed to the
>>                                                 Google Groups
>>                                                 "scala-user" group.
>>                                                 To unsubscribe from
>>                                                 this group and stop
>>                                                 receiving emails from
>>                                                 it, send an email to

>>                                                 scala-user+...@googlegroups.com

>>                                                 <mailto:scala-user+...@googlegroups.com>.

>>                                                 For more options,
>>                                                 visit
>>                                                 https://groups.google.com/d/optout

>>                                                 <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>                             --
>>                             You received this message because you are
>>                             subscribed to the Google Groups
>>                             "scala-user" group.
>>                             To unsubscribe from this group and stop
>>                             receiving emails from it, send an email to

>>                             scala-user+...@googlegroups.com

>>                             <mailto:scala-user+...@googlegroups.com>.

>>                             For more options, visit
>>                             https://groups.google.com/d/optout

>>                             <https://groups.google.com/d/optout>.

>>
>>
>>
>>
>>
>>
>>     --
>>     You received this message because you are subscribed to the Google
>>     Groups "scala-user" group.
>>     To unsubscribe from this group and stop receiving emails from it,

>>     send an email to scala-user+...@googlegroups.com

>>     <mailto:scala-user+...@googlegroups.com>.

>>     For more options, visit https://groups.google.com/d/optout

>>     <https://groups.google.com/d/optout>.

>
>
> --
> You received this message because you are subscribed to the Google
> Groups "scala-user" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to scala-user+...@googlegroups.com

> <mailto:scala-user+...@googlegroups.com>.

[Julian Michael]

There's some discussion in this thread of Lists/Streams "being infinite." It probably would help to define what this means. If you mean that a value of type List[A] can be infinite, i.e., have an infinite number of elements, I would disagree.

What is a value? I'll go with the definition familiar from the study of programming languages, and reason backwards from the assumption that Scala satisfies progress and preservation. In this case a value of type List[A] is a term of that type after it has finished evaluating. All such values can be constructed by a finite number of applications of Nil/Cons. We know this because Cons is call-by-value in its arguments and Nil and Cons are the only constructors.

You cannot access the head of a list while the tail is "still evaluating." In order to be handed a nonempty list, i.e., a Cons(h, t), someone must have evaluated t.

Anything that happens during a nonterminating computation of type List[A] is unobservable to the rest of the program (...ignoring side effects as always) so all such terms are observationally equivalent. You may say the term is not a value or you may say it is the singular value ⊥, but don't say the list is infinite. Indeed, you could claim anything you want about the "actual list"—it's full of 2's!—and be just as correct, because the claim can never be falsified. So the proper way to think about it is that there is no actual list. It is ⊥.

If you want a formal definition of List, use the standard inductive definition. This—barring null, ???, exceptions, side effects, and other quirks that we've been ignoring anyway—is Scala's list. It is not Haskell's list. That is, it is the least fixed point of F_A where F_A(X) = (A * X) + 1, where 1 is the singleton type. Stream[A], on the other hand, is the greatest fixed point of the same equation. (Indeed, you may notice that they both satisfy it.) The easiest way to see this is to view that equation as a definition principle. How do you come to have a list? Well, you can make one either by starting with an A and another list, or with nothing at all. So the definition principle works leftward—start with A * List[A] or 1, and that means you have a List[A]. How do you come to have a stream? Well, you simply provide the uncons operation: the pair (A * Stream[A]) that it breaks down into, or 1, signaling the end. So the definition principle works rightward.

You'll notice that with such definition principles, I can't create an infinite list, even though I have a partial programming language. I can try: def infinite: List[Int] = 1 :: infinite; infinite. Stack overflow—because, as is immediately apparent, infinite needs to be evaluated in order for it to be constructed. Because Cons is call-by-value, it eliminates the sort of circular solutions to the equation that would give us infinite lists, yielding the least solution to the equation. But with the uncons approach of streams:

  trait Stream[A] {

    def uncons: Either[(A, Stream[A]), Unit]

  }

  val infinite: Stream[Int] = new Stream[Int] {

    override def uncons = Left(1, this)

  }

Works perfectly fine—because the stream is defined by the operation, not the values held inside it, so it can hold itself. Another way of implementing this same logic is by using a call-by-name Cons operator, which is essentially what #:: is. What this means is that all of the "circular" solutions—and maybe some transcendental non-circular ones too—are allowed, i.e., we now have the greatest solution to the above equation. How do I say this stream is infinite? Easy—it's observationally distinguishable from every list.

Vlad, if you want a categorical definition, it's this one. Suppose we have a category where the objects are types and arrows are terms. (We may not, but we've maintained the fiction so far anyway.) Given a functor F, an F-Algebra is a pair (X, a: F(X) -> X). F-Algebras form a category, where the arrows are commuting squares formed in the obvious way by a: F(X) -> X, b: F(Y) -> Y, f: X -> Y, and F(f): F(X) -> F(Y). The inductive type defined by F is an initial object in the category of F-algebras. There, the "type" is X, and the arrow a is its constructor. For List[A], the functor is F(X) = (A * X) + 1, as I said before. There is also a notion of F-coalgebra, which consists of a pair (X, z: X -> F(X)). The coinductive type for F is the final object in the category of F-coalgebras. Stream[A] is the coinductive type for the functor I gave. (Oh, right, and the action of F on arrows is the obvious one—the result just moves A and 1 around untouched and applies the original arrow to the nested X.)

The categorical definition makes it more or less clear how the constructor serves as a proper definition principle for List and Stream. In particular, being an initial object tells you this: that giving a value of type B on 1 (Nil) and a "succession" function that takes an (A * B) to a B together uniquely defines a function from List[A] to B—and oh hey, that's exactly a fold. At the same time, it allows you to verify that your intuitive denotational/set-theoretic characterization of the list and stream types is accurate.