Difficulty understanding this type signature

Question

merge sort type signature :

def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {

The function is called using :

msort[Int]((a, b) => a < b) _

Does the type msort[Int] type the parameters a & b to Int ?

To better understand this type signature I've tried to extract the less function :

  def lessFunc[Int]((a , b) : (Int , Int)) : Boolean = {

    true

  }

But this is not correct ?

Entire code :

def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {
    def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys.reverse ::: acc
        case (_, Nil) => xs.reverse ::: acc
        case (x :: xs1, y :: ys1) =>
          if (less(x, y)) merge(xs1, ys, x :: acc)
          else merge(xs, ys1, y :: acc)
      }
    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(msort(less)(ys), msort(less)(zs), Nil).reverse
    }
  }

score 2 · Accepted Answer · edited May 23 '17 at 11:57

This is a function which takes two lists of parameters. The first list contains a less function, which as you've guessed correctly when invoked with [Int] is typing the parameters to Int.

You have just expanded it wrong. What you should have done is

def less(a: Int, b: Int) = true

or to match your anonymous function

def less(a: Int, b: Int) = a < b

Now when you call your msort like msort[Int](less) _ (see currying) you'll get a new function which is able to sort Lits[Int].

val listSorter = msort[Int](less) _
listSorter(List(1, 2, 3))

goral · Answer 2 · 2014-05-19T22:03:32.470

def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T]

is a function with two parameter lists that returns List of type T. First parentheses let you pass a function that will be used for sorting the list.

(T,T) => Boolean - means that the function will take two parameters and yield boolean.

The second parentheses take a List of type T . This T after name of the function is like generics in Java. You use it to pass a type. It can be called like:

def msort[String]((a,b) => a.length < b.length)(some list) if you want to sort List of String's by their length. Or you can call it like in the example to sort List of Ints

def msort[Int]((a,b) => a < b)(some list)

Because function is defined with two sets of parameters we can take advantage of it by applying only part of them and build specialised functions based on that one. Like for example:

val stringSort = msort[String]((a,b) => a.length < b.length) _

val ascendingIntSort = msort[Int]((a,b) => a < b) _

These are curried functions because stringSort's signature is List[Strint] => List[String]. Now you can reuse these methods by passing only instances of Lists to them:

stringSort(List("cat", "elephant", "butterfly"))

ascendingIntSort(List(4,1,3,2))

Re the 1st method signature: It is a method with two argument lists, not a curried function. Why is this confusion so widespread? — Randall Schulz, May 19 '14 at 21:58
Sorry, you are right. My mistake. Already fixed. Confusion probably comes from the fact that in terms of functionality we don't get much of a difference. — goral, May 19 '14 at 22:01

Difficulty understanding this type signature

2 Answers2