CODEWITHSUNDEEP
scala
blue-sky
blue-sky

Reputation: 53826

Difficulty understanding this type signature

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
    }
  }

Upvotes: 1

Views: 116

Answers (2)

goral
goral

Reputation: 1265

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

Upvotes: 1

lpiepiora
lpiepiora

Reputation: 13749

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

Upvotes: 2

Related Questions