typelevel / cats Goto Github PK

or really any typeclass. We got burned with an early version of twitter/bijection that did this. It meant having an implicit bijection in scope gave you an implicit conversion.

Per a conversation with Kmett that I only understood about 10% of (i.e., better than usual) the notion of Bimonad is interesting only if the Monad and Comonad instances are each others' co-algebras, otherwise we can't say anything interesting. It's also not clear whether these things we can say lead to useful derived operations. So I suggest removing Bimonad unless we can state its law and identify operations that it provides; closing the diamond is fun but not reason enough.

Do we want to do this as a separate data type, or should we explore the tagged type approach?

Also related to #31

I'll eventually take a crack at this if nobody beats me to it. Unless there's a technical or philosophical reason not to?

Cats defines a lazy version of foldRight on Foldable:

def foldRight[A, B](fa: List[A], b: Lazy[B])(f: (A, Lazy[B]) => B): Lazy[B] = {

Currently the List implementation is properly lazy, but it is not stack safe.

For example, consider the following derived Foldable method:

def exists[A](fa: F[A])(f: A => Boolean): Boolean =
  foldRight(fa, Lazy.eager(false))((a, b) => f(a) || b.force).force

This implementation will properly short-circuit for a small list:

scala> Foldable[List].exists(List(1, 2, 3)){x => println(x); x > 1}
1
2
res0: Boolean = true

However, for a large list it will throw a StackOverflowError. If a List is long enough that evaluating the predicate for each element is bad (and thus the Lazy variant is preferred), then it is likely large enough to throw this error. Therefore something needs to give.

Solutions that come to mind:

1. Use a version of foldRight for List that uses a combination of reverse and foldLeft. This would sacrifice laziness.
2. Use trampolining in the List implementation of the Lazy variant of foldRight. The trampolining would add significant overhead, but laziness would be preserved.

The second version seems preferable to me. If somebody is choosing to explicitly call the lazy (as opposed to strict) version, then they should get laziness.

However, I can also see the possibility of the abstraction becoming somewhat leaky. That is, someone defining def foo[F[_]: Foldable]... may start to think about which kinds of F people are going to be passing into this method so they can decide whether they want potential overhead of laziness or not. Having said that, it seems to me that the abstraction is still pretty leaky (or flat out wrong) if the types are suggesting they will get lazy evaluation but they don't.

What do people think? Beyond just choosing option 1 or option 2, are there other possibilities that come to mind?

we should have Show instances in std for things like Float, Double, Int, Long, etc

Bifoldable is a type class (currently not in cats) for a type that has two separate Foldables. For example, Or has a Foldable instance (via its Traverse instance) that folds over the RightOr case, but Or could equally fold over the LeftOr case.

One of my favorite methods from scalaz is MonadPlus.separate. This can do things like take a List[A Or B] and turn it into a (List[A], List[B]). Or similarly, take a List[(A, B)] and turn it into a (List[A], List[B]). In Cats, I believe we could implement the same sort of method on MonadFilter if we were to bring in a Bifoldable type class.

What do people think? Is this something that would belong in core?

Currently the BigInt and BigDecimal instances reside in anyref.scala and are mixed into AnyRefInstances. Since we have other AnyRef instances (String, Option, etc), this seems kind of odd to me. Should they just get their own files and instance traits like other std lib types?

We need to decide on a home for arbitrary instances of cats.data types.

1. cats-laws could depend on cats-data. This is simplest.
2. We could establish a new module, cats-data-laws, which pulls in both cats-laws and cats-data. This is better for future projects that build on cats-core without cats-data.

Either from the standard library is isomorphic to Or and should have instances for all of the same type classes that Or does.

I still have to use scala std Future a lot so... this would be quite useful. I think at least Monad, Comonad and Monoid should be implemented. I volunteer to implement them over the weekend.

As @retronym says:

I'd suggest to annotate the types of implicits as a rule around the code base.
It is too easy to have overly-specific structural types inferred for
implicit val fooInstance = new A with B { .... }

Even something as basic as the diagram from semigroupoid would be very useful. We can iterate and make it look nicer on a second step.

We now have a Or datatype in -data which is mostly lifted straight out of scalaz.

Right now it is

data Or a = LOr a | Ror a

We thought about -Or and Or- for constructors but the compiler seemed unhappy about. I don't think anyone loves the name LOr or ROr, but nobody seems to have a slam-dunk replacement. We're going to move on for now, but the discussion around this raised several questions we should revisit:

1. What are good names for these constructors, some suggestions i've heard:
   Bad | Good
   \Or | Or/
   Dead | Alive
2. do we want public constructors at all on these? Can we have just a catamorphism? Can we have smart constructors and extractors so that we can still pattern match?
3. Do we want to tend not to just lift code out of scalaz, perhaps we would re-think some of the decisions made in scalaz and tend to have a better chance of improving things if we are writing everything new

see #62 as a separate issue for the lazy foldRight, which I thought deserved special attention, but the rest of the methods in Foldable also deserve documentation.

My tendency would be to also give special attention to sequence_ and traverse_ as they are side-effecty and side-effecty demands more documentaiton

I've mentioned this while talking to many people, so I think it's something that we should get started on sooner rather than later.

Here are some things I imagine it doing:

1. Set expectations for contributors
2. Explain basic workflow, discussions, PR process, etc.
3. Talk about project structure, modules, etc.
4. Explain fundamental guiding principles
5. Lay out best practices and encourage consistency
6. Clearly document any exceptions or gotchas

We could use a wiki but I think I'd prefer a single Markdown document. I will try to start on this ASAP.

Travis points us to https://github.com/finagle/finagle-smtp as an example, "sbt-site lets you pull together different pieces of your project site (API docs, tutorial, etc.) and sbt-ghpages publishes them to GH Pages. They can be used independently but work together well."

in scalaz and cats, type classes are defined as trait with inheritance to express facts like all Monad are an Applicative. This leads to some ambiguous implicit resolutions and as far as I know, the solution is to create a hierarchy of traits to guide implicit search. It also creates ambiguous implicit when you have two imports that brings the same implicit in scope e.g.

import scalaz.syntax.traverse._ 
import scalaz.syntax.foldable._

I wonder if it would be possible and desirable to implement type classes using abstract class and implicit evidence to express the hierarchy between two type classes:

abstract class Equal[T]{
  def eq(v1: T, v2: T): Boolean
}

object Equal{
  def apply[T](implicit ev: Equal[T]): Equal[T] = ev
  def equalA[T]: Equal[T] = new Equal[T] {
    def eq(v1: T, v2: T): Boolean = v1 == v2
  }

  implicit val intEqual = equalA[Int]
}

abstract class Ord[T: Equal]{
  def lowerThan(v1: T, v2: T): Boolean
  def lowerThanOEqual(v1: T, v2: T): Boolean = lowerThan(v1, v2) || Equal[T].eq(v1, v2)
  def greaterThan(v1: T, v2: T): Boolean = !lowerThan(v1, v2)
  def greaterThanOEqual(v1: T, v2: T): Boolean = greaterThan(v1, v2) || Equal[T].eq(v1, v2)
}

object Ord{
  def apply[T](implicit ev: Ord[T]): Ord[T] = ev
  def fromLowerThan[T: Equal](lth: (T, T) => Boolean): Ord[T] = new Ord[T] {
    def lowerThan(v1: T, v2: T) = lth(v1, v2)
  }

  implicit val intOrd = fromLowerThan[Int](_ < _)
}

I haven't tried this technique extensively, so it might in fact causes more issues that inheritance. However, I thought it make sense to discuss this option since you are just starting cats.

This may need to be a longer-term goal, but in my view providing a linter is one of the single most important things a project can do to promote contribution.

I definitely agree that we should be documenting conventions like #27, but having to parse a bunch of guidelines in prose (and then extrapolate from the current source when the guidelines aren't 100% unambiguous, which is always) can be stressful—I know that I'm personally a lot less likely to click the submit button on local work if I'm worried that it's going to be picked apart because I didn't understand all the details of the project's contributor guidelines (and that's even if I don't think the maintainers are going to be dismissive or condescending). Being able to go through a few rounds of local correction for formatting and convention before I put something in public is hugely confidence-building.

I like both WartRemover and Scalastyle, but I'm not sure either is a perfect solution to this problem.

I've done the manual set up a few times with no luck.

This issue exists solely so I can comment on it, change it, etc. to test Gitter integration.

Currently we really don't have any tests other than some law-checking. We should set a precedent for tests that will be easy for others to follow as the contribute.

The two implementations are effectively identical:

implicit def OrShow1[A: Show, B: Show]: Show[A Or B] =
  Show.show[A Or B](_.fold(a => s"LOr(${Show[A].show(a)})", b => s"ROr(${Show[B].show(b)})"))

implicit def OrShow2[A, B](implicit showA: Show[A], showB: Show[B]): Show[A Or B] =
  Show.show[A Or B](_.fold(a => s"LOr(${showA.show(a)})", b => s"ROr(${showB.show(b)})"))

In order to make it easier for newcomers to contribute, I think cats should establish and document a convention for which of the two approaches to use.

Here is a proposed convention:
If your function needs to call a method on the type class instance, it should use the latter approach. This prevents the unnecessary calls to Show.apply.
If your function just needs the evidence of the type class instances so it can call through to another function that requires them, it should use the former aproach, as it is a bit cleaner.

There are also questions about whether you should use names like showA: Show[A] or ShowA: Show[A] or A: Show[A], etc. I don't really have a preference on convention here, but I think the more of this we can put into a contributor guide the less people have to worry about not knowing the right way to do it or submitting a pull request that gets nitpicked.

Thoughts?

We should provide a helper method to convert Try[A] into Throwable Or A.

It probably makes sense to put this on the Or companion object, because the std module does not depend on the data module. However, this does raise the question of whether we are going to have syntax for things like Try.toOr, Either.toOr. List.toNonEmptyList, etc. If so, where would it go?

Also this could be implemented as an isomophism with something like Try <~> Or[Throwable, ?], but as far as I know we don't have this sort of isomorphism defined in Cats. Do we want it?

shall we implement type class methods (e.g. map, show) on data structures in cats.data or shall we get them via ops implicit classes?

A goal of some contributors is to build an alternative to scalaz-stream.

There are a some cases (like https://github.com/tpolecat/doobie) where scalaz-stream is used with a different monad but most applications use scalaz.concurrent.Task which in turn wraps scalaz.concurrent.Future.

Are people generally satisfied with the design of scalaz's Task and Future? Should cats seek to follow a generally similar design or do something different? Does the scope of cats include these tools or would another project be appropriate?

Choice, ProChoice and probably other typeclasses have methods that take or produce Either. Ideally, we would use cats.data.Or instead of scala.Either but it means that Or need to be defined in core.

What is your thought?

non says, "it would be nice if cats.std.string._ gave you Show[String] but also Monoid[String]. which would just mean having an object that repackages the string implicits from algebra
so the user doesn't have to care where things live."

lets give at least a one-liner comment to pure, and perhaps more detail in compose about what one can do with a composite applicative

std should have typeclass instances for Map,

Map[K,?] should have instances for FlatMap, Traverse

Map[?,?] should have instances for Show

Instances in cats are checked against the type class laws. People may find certain things useful that either don't have governing laws or don't always obey them. For example, consider the following type class:

trait Foreach[F[_]]  { 
  def foreach[A](fa: F[A])(f: A => Unit): Unit
}

This type class has no meaningful laws. However, it could potentially be useful as an alternative to something like traversing a list into IO. The latter can lead to either stack overflows or excessive overhead for trampolining.

There should be a separate project to provide these sorts of things. @non has cleverly suggested the name alley-cats for such a project.

we should have one in the gh-pages

Will be helpful after #17 is done, so we have a way for people to view the fantastic typechecked doc.

Helpful documentation that doesn't go stale is a good goal. Consider usage of sbt-doctest, tut, or something similar.

• better placement for the waffle.io badge
• "How can I contribute"
• "what to do in the case of mis-communication, I've been harmed, I think ____ is a bad actor"
• mention the "meta" label for issues

I would like to check how much interest there is in taking Scala.JS seriously in cats.

That might not be an easy decision to make but it could actually be :-)

As discussed in #21, an asynchronous monad like the scalaz Task would be highly desirable for a variety of reasons including any possible streaming solution. The scalaz Task is very nice in many ways, but @tpolecat and I think it could possibly be improved. This would seem to not be a high priority at the moment, but would be nice to get on the radar.

One such issue with scalaz Task is stack overflows using Task.async.

Why would we want that but not Monad? Are there examples where we can implement one but not the other?

apply3, map3, apply4, map4... don't know if we should have some uniform arity where these things stop, in scalaz it is all over the place, some of these stop at 5 some at 8 some at 12, etc...

Use machinist for zero-cost type class ops.

The contributor guide mentions that one should run the compile, unidoc, and scalastyle tasks before submitting a PR. It would be nice if those could be subsumed under a new validateMyPR task so that you have to remeber only one task to run before submitting a PR.

I'd like to discuss if the laws that govern the functions of type classes should be put next to their definitions. Here is an example of what I have in mind:

// this is Functor.scala

trait Functor[F[_]]  {
  def map = ...
}

trait FunctorLaws[F[_]: Functor] {
  def identity(...): Boolean = ...
  def associative(...): Boolean = ...
}

I see the following advantages:

• it emphasizes the importance of laws
• the type checked laws are in the vicinity of the type class definitions and not "hidden" between test code in the laws subproject
• the laws can be used in the laws subproject
• the laws are decoupled from test code

What do you think?

should have at least Show[String] instance

We've removed documentation on Or that had been copied from Scalaz since we don't have a Validation type yet, but once we do we should reinstate this note.

especially since this is a bit of a new approach to handling a lazy fold right, this deserves lots o' doc.

the methods on Apply should have documentation, how would I use apply2, how is map2 different than apply2

I think it would be handy to have a list-like structure that supports efficient appends. This is handy for many use-cases, such as using a writer monad for logging.

The most obvious candidate is a difference list.

Do others agree that something like this should be in the data module? Are there any alternatives to difference lists that should be considered?

I would imagine that we all want this to verify pull requests before they are merged (though please speak up if you have a reason not to go with Travis).

Anyone should be able to submit a PR with a .travis.yml. I think @non will probably have to be the one to enable it as described here.

presumably using discipline.