Function call not accepting :: operator in argument-CodePudding

I'm supposed to write a recursive functional concatenation function in Scala without using standard list operators.

def myConcat: (List[Any],List[Any]) => List[Any] = {
  case (xs,Nil) => xs
  case (xs,y::ys) => myConcat(xs::y,ys)
}

which throws the error

         case (xs,y::ys) => myConcat(xs::y,ys)
                                       ^
Recursion.scala:3: error: value :: is not a member of Any

I am rather confident that this would, but that I am misunderstanding something about the syntax/typing. To the best of my knowledge xs::y should be of type List[Any].

CodePudding user response：

I assume, you cannot use List.reverse either, so, start with implementing that:

    def reverse(in: List[Any], out: List[Any]): List[Any] = in match {
      case Nil => out
      case head::tail => reverse(tail, head::out)
   }

Now, for concat:

    def concatReversed(x: List[Any], y: List[Any]) = x match {
       case Nil => y
       case head::tail => concatReversed(tail, head::y)
    }

    def concat(x: List[Any], y: List[Any]) = concatReversed(reverse(x), y)

If you are not looking for the solution to be tail-recursive, it makes things simpler (albeit less efficient):

     def concat(x: List[Any], y: List[Any]): List[Any] = x match {
       case Nil => y
       case head ::  tail => head :: concat(tail, y)
     }