9

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).

Improve this question
0

2 Answers 2

Reset to default
13

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for the reminder about case, I fixed my other answer accordingly! I tested it with case in my code but somehow omitted it when copying my code over.
You can put import Ordering.Implicits._ at the top of the file, and thus avoid the implicitly summons all over the place.
@missingfaktor I'm not sure how that import would help, since the Ordering.Ops that we get does not have a compare method
I don't see a good reason to use pattern matching here. (and thus not for compare either.) Hence the suggestion.
2

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).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.