CODEWITHSUNDEEP
functiongenericsscalahaskelltypes
Dan Burton
Dan Burton

Reputation: 53705

Generalizing scala code into a function

So I accidentally wrote a Haskell answer to a Scala question recently. Being rather familiar with Haskell, the solution came quite easily to me:

myMaxBy :: (a -> a -> Ordering) -> [a] -> [a]
myMaxBy _ [] = undefined
myMaxBy f (x:xs) = foldr step [x] xs
  where step y acc@(z:_) = case f y z of
          GT -> [y]
          EQ -> y:acc
          LT -> acc

Then someone reminded me that it was a Scala question. I set out to transate my code into Scala, and after much pain I settled for:

(List(xs.head) /: xs.tail) { (acc, y) =>
  y compare acc.head match {
    1  => List(y)
    0  => y :: acc
    -1 => acc
  }
}

But I could not for the life of me get the Scala type system to bend to my will and generalize this into a function where xs and compare are inputs (ideally, curried inputs with the comparator first). Though this is surely due to my general unfamiliarity with Scala, I also slightly blame Scala's complex (though very powerful) type system. Can you do some hand-holding and walk me through how I could turn this into a generalized function, with a type signature similar to the Haskell equivalent? (Read: as general as.) Please also demonstrate usage, if it is more complicated than myMaxBy(myCompare)(someList).

Upvotes: 9

Views: 688

Answers (2)

Luigi Plinge
Luigi Plinge

Reputation: 51109

You missed out the case keywords in your pattern-match, which are quite important!

All you need is for the collection parameter type to be able to use a compare method. There are two systems for comparing things in Scala: extending Ordered, or using an Ordering. There are implicit conversions between the two so it doesn't matter too much which you choose; the first is perhaps easier to understand.

First off, using Ordered:

  def myMaxBy[A <% Ordered[A]](xs: List[A]) = {
    (List(xs.head) /: xs.tail) { (acc, y) =>
      y compare acc.head match {
        case 1  => List(y)
        case 0  => y :: acc
        case -1 => acc
      }
    }  
  }

Here we give our generic type A a view bound using <%, which means "can be seen as". This is more general than using an upper bound <:, and useful for classes that are not themselves Ordered, but have implicit conversions to Ordered classes, e.g. Int to RichInt.

Alternatively, if you want flexibility to be able to change the ordering criteria, you can write it like this:

  def myMaxBy[A](xs: List[A])(implicit ord: Ordering[A]) = {
    (List(xs.head) /: xs.tail) { (acc, y) =>
      ord.compare(y, acc.head) match {
        case 1  => List(y)
        case 0  => y :: acc
        case -1 => acc
      }
    }
  }

When invoking, if there's an implicit Ordering[A] in scope, you can leave the second argument out. This second way also has the advantage that you can define an Ordering on arbitrary classes, whether or not they already support it.

You can invoke both using, for example, myMaxBy(List(1,2,3,4,3,4)). In the second, if you wanted, say, reverse ordering: myMaxBy(List(1,2,3,4,3,4))(Ordering.Int.reverse).

Another thing you might see in this context are context bounds. E.g. [A: Ordering]. This means the same as [A](implicit ord: Ordering[A]), which is more concise, except that you don't get a handle on the Ordering so have to summon it using implicitly. So here it's probably best to state it explicity as above.

Upvotes: 13

Jed Wesley-Smith
Jed Wesley-Smith

Reputation: 4706

You need to either have the A type extend Ordered or better, restrict it so there is an Ordering type class available. The first looks like:

def sort[A <: Ordered[A]](xs: List[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => y compare acc.head match { … } }

As Luigi points outeven better is to use the view bound <% rather than the subtype bound <: as it allows for types that have implicit conversions to Ordered views.

def sort[A <% Ordered[A]](xs: List[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => y compare acc.head match { … } }

Better though is to use the Ordering type class:

def sort[A](xs: List[A])(implicit ord: Ordering[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => ord compare (y, acc.head) match { … } }

You can use a context bound as well:

def sort[A: Ordering](xs: List[A]) = {
  val ord = implicitly[Ordering[A]]
  (List(xs.head) /: xs.tail) { (acc, y) => ord compare (y, acc.head) match { … } }
}

while this is slightly cleaner syntactically it doesn't let you pass in an explicit alternate Ordering (say case-insenitive ordering of Strings for instance).

Upvotes: 2

Related Questions