Where should we define type class instances?

[mpilquist]

trafficstars

E.g., right now we have a Monoid[Int] defined in the companion object for Semigroup.

scala> import leopards.Semigroup

scala> summon[Semigroup[Int]]
val res0: leopards.Semigroup.given_Semigroup_Int.type = leopards.Semigroup$given_Semigroup_Int$@1682007c

scala> 1 |+| 2                                                                                                                                          
1 |1 |+| 2
  |^^^^^
  |value |+| is not a member of Int, but could be made available as an extension method.
  |
  |The following import might fix the problem:
  |
  |  import leopards.Semigroup.given_Semigroup_Int
  |

scala> import leopards.Semigroup.given

scala> 1 |+| 2
val res1: Int = 3

So the instance is found without an explicit import but the extension methods aren't.

[mpilquist]

Snippet from Discord today:

We could either define all instances as top level definitions -- in which case import cats.given is what you'd need, but also means you will always always need import cats.given
[11:50 AM]
Instead we could define instances in companions (like we do now with cats) but then we'd need to export those instances to get syntax. Like:
trait Functor[F[_]]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]
object Functor:
  given Functor[List] with ...
export Functor.given

Without the export Functor.given, an import leopards.given won't give us extension methods.

[mpilquist]

More from Discord, using an example from @timwspence:

trait Functor[F[_]]:
  extension [A](fa: F[A])
    def fmap[B](f: A => B): F[B]

object Functor:
  given Functor[List] with
    extension [A](fa: List[A])
      def fmap[B](f: A => B): List[B] = fa.map(f)

def test[F[_] : Functor](f: F[Int]) = f.fmap(_.toString) // Works fine, compiler finds Functor extensions

@main def run =
  println(test(List(1,2,3))) // Works
  println(List(1, 2, 3).fmap(_ + 1)) // This doesn't work without importing Functor.given

@smarter Is that last line intentional? The compiler suggests the given import to add so it definitely knows about it. It seems really weird that folks don't need given imports in the body of test but do need them when working with concrete types.

[smarter]

Looks normal to me, the rules for extension methods lookup say:

2.The extension method is a member of some given instance that is visible at the point of the reference.

On the other hand when working with the concrete instance, there's no extension method fmap in scope by any rule, the compiler finds one to display in an error message by looking in your classpath for all possible importable implicits.

[smarter]

I'll note that I don't think this is fundamentally different from how Haskell for example behave, if I want to use arr I need to do:

import Control.Arrow

Which in Scala-speak would be:

import Control.Arrow
import Control.Arrow.{*, given}

[mpilquist]

Okay, thanks!

So I think our best course of action is:

1. Define instances in typeclass companion objects like is currently done in cats.
2. Export typeclass given instances to package level.

E.g.:

package cats

trait Functor[F[_]]:
  extension [A](fa: F[A])
    def fmap[B](f: A => B): F[B]
object Functor:
  given Functor[List] with ...
export Functor.given

Which then allows a simple import cats.given to get all extensions.

[alexandru]

I'm reading the issue, but I don't understand the problem. I think you can export Monad instances in Applicative's companion object, and Applicative instances in Functor's companion object:

package my.cats

trait Functor[F[_]]:
  extension [A, B](fa: F[A])
    def map(f: A => B): F[B]

object Functor:
  // Applicative instances are Functor instances
  export Applicative.given

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]

  extension [A, B](fa: F[A])
    def ap(ff: F[A => B]): F[B]

    def map2[C](fb: F[B])(f: (A, B) => C): F[C] =
      fa.ap(fb.map(b => f(_, b)))

object Applicative:
  // Monad instances are Applicative instances
  export Monad.given

extension [A](a: A)
  inline def pure[F[_]: Applicative]: F[A] =
    summon[Applicative[F]].pure(a)

trait Monad[F[_]] extends Applicative[F]:
  extension [A, B](fa: F[A])
    def flatMap(f: A => F[B]): F[B]

object Monad:
  // Instance definition goes here:
  given Monad[List] with
    def pure[A](a: A): List[A] = List(a)

    extension [A, B](fa: List[A])
      def map(f: A => B): List[B] = fa.map(f)
      def ap(ff: List[A => B]): List[B] = ff.flatMap(fa.map)
      def flatMap(f: A => List[B]): List[B] = fa.flatMap(f)

Sample code making use of the above:

// No import of any givens necessary
import my.cats.Applicative
import my.cats.Monad
import my.cats.pure

def sequence1[F[_]: Monad, A](list: List[F[A]]): F[List[A]] =
  list.foldLeft(List.newBuilder[A].pure[F]):
    (acc, a) =>
      acc.flatMap: xs =>
        a.map: x =>
          xs.addOne(x)
  .map(_.result())

def sequence2[F[_]: Applicative, A](list: List[F[A]]): F[List[A]] =
  list.foldLeft(List.newBuilder[A].pure[F]):
    (acc, a) =>
      acc.map2(a)(_ addOne _)
  .map(_.result())

Isn't this what you had in mind?