Type inference question using Scalaz.ListW.<^>

Question

I was playing around with ListW.<^>, the definition of which is as follows:

def <^>[B: Zero](f: NonEmptyList[A] => B): B = value match {
  case Nil => ∅
  case h :: t => f(Scalaz.nel(h, t))
}

I cannot figure out how come Option is being chosen as the Zero type for this example

scala> case class CC(v : Int)
defined class CC

scala> val posns = List(CC(2), CC(5), CC(1))
posns: List[CC] = List(CC(2), CC(5), CC(1))

So now I have a List of these things. My goal is to get back an Option[CC] for the min/max of posns where I get a None for min if there are no values below zero and similar for max.

scala> import scalaz._; import Scalaz._
import scalaz._
import Scalaz._

scala> implicit val CCOrder = new Order[CC] { 
       | def order(v1 : CC, v2 : CC) = orderBy( (v : CC) => v.v ).order(v1, v2) 
       | }
CCOrder: java.lang.Object with scalaz.Order[CC] = $anon$1@1e48d65

scala> posns.filter(_.v < 0) <^> (_.min)
res0: Option[CC] = None

scala> posns.filter(_.v > 0) <^> (_.max)
res1: Option[CC] = Some(CC(5))

Option was exactly the Zero type I wanted! Can anyone explain how come Option is being chosen by the typer? I don't declare it anywhere!

Answer 1

The definitions for ListW#<^> and MA#min:

sealed trait MA[M[_], A] extends PimpedType[M[A]] {
  def min(implicit r: Foldable[M], ord: Order[A]): Option[A] =
    foldl1((x: A, y: A) => if (x ≨ y) x else y)
}

sealed trait ListW[A] extends PimpedType[List[A]] {
  def <^>[B: Zero](f: NonEmptyList[A] => B): B = value match {
    case Nil => ∅
    case h :: t => f(Scalaz.nel(h, t))
  }
}

Here are the relevant inferred types, implicit conversion, and implicit parameters. scalac -Xprint:typer will reveal this.

object test {
  import scalaz._
  import Scalaz._

  case class CC(v: Int)
  val posns = List(CC(2), CC(5), CC(1))
  val filtered = posns.filter(((x$1: CC) => x$1.v.<(0)))
  val listw = Scalaz.ListTo[CC](posns.filter(((x$1: CC) => x$1.v.<(0))))
  listw.<^>[Option[CC]]{
    (x$2: scalaz.NonEmptyList[CC]) =>
      Scalaz.maImplicit[scalaz.NonEmptyList, CC](x$2).min(Foldable.NonEmptyListFoldable, CCOrder)
  }(Zero.OptionZero[CC]);
}

List@#<^> runs the provided function from NonEmptyList[A] => B if the pimped list is non-empty, otherwise returns the Zero for type B. MA#min actually returns Option[B] -- it is a general function for containers, not a specific one for NonEmptyList, where it could return a B.

A more direct way to achieve this is to call MA#min directly. Unfortunately, List already has a min function, new in Scala 2.8, so the implicit view to MA is not triggered without a type hint:

posns.filter(_.v < 0).min
<console>:16: error: could not find implicit value for parameter cmp: Ordering[CC]
   posns.filter(_.v < 0).min

(posns.filter(_.v < 0): MA[List, CC]).min
res7: Option[CC] = None

This is one of the motivating reasons to provide symbolic identifiers in Scalaz -- it is a crude form of namespacing!

Side note: you can simplify your instance of the Order instance for CC:

implicit val CCOrder: Order[CC] = orderBy(_.v)
CCOrder: scalaz.Order[CC] = scalaz.Orders$$anon$2@fc2528