Scala Pattern type is incompatible with expected type

Question

This is a sequel to Why can't I run such scala code? (reduceRight List class method)

I am following the accepted answer there to rename my abstract class and add list: List[T] as a parameter of the method foldRight.

abstract class ListT {
    def foldRight[U](z : U)(list: List[T], op: (T, U) => U): U = list match {
        case Nil => z
        case x :: xs => op(x, foldRight(z)(xs, op))
    }
}

But I still get the error for the 'def' line

multiple markers at this line, not found: type T

@LuisMiguelMejíaSuárez abstract class List[T]? No~ That is exactly the answer to the reduceRight method thread that I quoted. — PhysicsMath
Then you need to define the type parameter T somewhere. Anyways, it is kind of weird to have the method receive another List. Especially because that is the list from the stdlib... what exactly do you want to do? Define your own List class with a foldRight method? Or your own foldRight function? — Luis Miguel Mejía Suárez
". I don't care whether it operates on the stdlib List[T] or a customized abstract class." You will need to know what kind of list you operate on if you want that pattern matching to work. Nil and :: come from the stdlib. — Thilo
Start from scratch: yes. But more by defining MyList[T], MyNil, myConcat. You don't really care about what T is (assuming your list can work with any type of element). — Thilo

Luis Miguel Mejía Suárez Luis Miguel Mejía Suárez · Accepted Answer · 2019-06-29T12:58:55

Lets start by scratch, that should help you grasp the concepts.

We will create our own simple functional List.
It will be called MyList, will have an empty list called MyNil and the cons class / operator as :!:.

// Here we create the type MyList.
// The sealed is used to signal that the only valid implementations
//   will be part of this file. This is because, a List is an ADT.
// The A (which could be a T or whatever) is just a type parameter
//   it means that our list can work with any arbitrary type (like Int, String or My Class)
//   and we just give it a name, in order to be able to refer to it in the code.
// Finally, the plus (+) sign, tells the compiler that MyList is covariant in A.
//    That means: If A <: B Then MyList[A] <: MyList[B]
//    (<: means subtype of)
sealed trait MyList[+A] {
  def head: A // Here we say that the head of a List of As is an A.
  def tail: MyList[A] // As well, a tail of a List of As is another list of As.

  // Here we define the cons operator, to prepend elements to the list.
  // You can see that it will just create a new cons class with the new element as the head & this as the tail.
  // Now, you may be wondering why we added a new type B and why it must be a super type of A
  // You can check out this answer of mine:
  // https://stackguides.com/questions/54163830/implementing-a-method-inside-a-scala-parameterized-class-with-a-covariant-type/54164135#54164135
  final def :!:[B >: A](elem: B): MyList[B] =
    new :!:(elem, this)

  // Finally, foldRigh!
  // You can see that we added a new type parameter B.
  // In this case, it does not have any restriction because the way fold works.
  final def foldRight[B](z: B)(op: (A, B) => B): B = this match {
    case MyNil   => z
    case h :!: t =>  op(h, t.foldRight(z)(op))
  }
}

object MyList {
  // Factory.
  def apply[A](elems: A*): MyList[A] =
    if (elems.nonEmpty) {
      elems.head :!: MyList(elems.tail : _*)
    } else {
      MyNil
    }
}

// Implementations of the MyList trait.
final case class :!:[+A](head: A, tail: MyList[A]) extends MyList[A]
final case object MyNil extends MyList[Nothing] {
  override def head = throw new NoSuchElementException("head of empty list")
  override def tail = throw new NoSuchElementException("tail of empty list")
}

Now you can:

val l1 = MyList(2, 3, 4) // l1: MyList[Int] = 2 :!: 3 :!: 4 :!: MyNil
val l2 = 1 :!: l1 // // l2: MyList[Int] = 1 :!: 2 :!: 3 :!: 4 :!: MyNil
val sum = l2.foldRight(0)(_ + _) // sum: Int = 10

Scala Pattern type is incompatible with expected type

1 Answers