Megre two sorted Array, List vs Array

Question

This function merges two sorted lists. It takes two lists as a parameter and returns one.

def merge(xs : List[Int], ys : List[Int]) : List[Int] = {
  (xs, ys) match {
    case (Nil, Nil) => Nil
    case (Nil, ys) => ys
    case (xs, Nil) => xs
    case (x :: xs1, y :: ys1) =>
      if(x < y) x :: merge(xs1, ys)
      else y :: merge(xs, ys1)
  }
}

I wanted to rewrite this function by changing the parameter type from List to Array, and it did not work. However, going from List to Seq it worked. Could you tell me what does not work with the Arrays?

def mergeDontWork(xs : Array[Int], ys : Array[Int]) : Array[Int] = {
  (xs, ys) match {
    case (Array.empty,Array.empty) => Array.empty
    case (Array.empty, ys) => ys
    case (xs, Array.empty) => xs
    case (x +: xs1, y +: ys1) => if(x < y) x +: merge2(xs1, ys)
      else y +: merge2(xs, ys1)
  }
}

The error comes from that part of code : if(x < y) x +: merge2(xs1, ys) : Array[Any] does not conform with the expected type Array[Int]

EDIT

I finally understood how to go from List to Array thanks to the solutions proposed by pedromss and Harald. I modified the function by making it tail recursive.

    def mergeTailRecursion(xs : Array[Int], ys : Array[Int]) : Array[Int] ={

       def recurse( acc:Array[Int],xs:Array[Int],ys:Array[Int]):Array[Int]={

            (xs, ys) match {

                 case (Array(),Array()) => acc
                 case (Array(), ys) => acc++ys
                 case (xs, Array()) => acc++xs
                 case (a@Array(x, _*), b@Array(y, _*)) =>
                     if (x < y) recurse(acc:+x, a.tail, b)
                           else     recurse( acc:+y, a, b.tail)

           }

        }

           recurse(Array(),xs,ys)
     }

pedromss · Accepted Answer · 2017-09-10T18:44:34.210

You can't pattern match on Array.empty because it is a method. Use Array() instead.
(x +: xs1, y +: ys1) doesn't appear to be a valid match expression. Change to (x +: xs1, y +: ys1)

Compiling version of your code:

object Arrays extends App {

  def merge(xs: Array[Int], ys: Array[Int]): Array[Int] = {
    (xs, ys) match {
      case (Array(), Array()) => Array.empty
      case (Array(), ys2)         => ys2
      case (xs2, Array())         => xs2
      case (xs1@Array(x, _*), ys1@Array(y, _*)) =>
        if (x < y) x +: merge(xs1.tail, ys)
        else y +: merge(xs, ys1.tail)
    }
  }

  merge(Array(1, 2, 3), Array(4, 5, 6)).foreach(println)

}

Refer to [here|Why can't I pattern match on Stream.empty in Scala? for the explanation about pattern matching on methods.

And [here|How do I pattern match arrays in Scala? for the explanation about the _*. Basically it will match any number of arguments.

Lastlty about the xs1@, from the [documentation|https://www.scala-lang.org/files/archive/spec/2.11/08-pattern-matching.html]:

Pattern Binders

Pattern2 ::= varid `@' Pattern3

A pattern binder xx@pp consists of a pattern variable xx and a pattern pp. The type of the variable xx is the static type TT of the pattern pp. This pattern matches any value vv matched by the pattern pp, provided the run-time type of vv is also an instance of TT, and it binds the variable name to that value.

You could also do it with

case (Array(x, _*), Array(y, _*)) =>
            if (x < y) x +: merge(xs.tail, ys)
            else y +: merge(xs, ys.tail)

Thank you for all these detailed explanations. Your solution works very well. I modified it by making it tail recursive. see my last edit — ZchGarinch, Sep 11 '17 at 08:33

score 1 · Answer 2 · answered Sep 10 '17 at 18:25

The unapply methods of +: in the last pattern matching case doesn't seem to resolve to the right types Int and Array[Int].

You could try something like this:

case (Array(x, xs1 @_*), Array(y, ys1 @_*)) => 
  if (x<y) x +: mergeDontWork(xs.tail, ys)
  else y +: mergeDontWork(xs, ys.tail)

Unfortunately the construct xs1 @_* results in xs1 being of type Seq[Int] so it's also not possible to pass it into the recursive call. I used xs.tail as a workaround.

Thanks for your reply, it helped me understand the solution proposed above — ZchGarinch, Sep 11 '17 at 08:34

Megre two sorted Array, List vs Array

2 Answers2