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, Jun 29 '19 at 01:50
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, Jun 29 '19 at 01:55
@LuisMiguelMejíaSuárez Yes, I agree. But Prof Odersky did exactly that in his Coursera course Functional Programming Principles in Scala, which conflicts with the List[T] defined in Scala standard library — PhysicsMath, Jun 29 '19 at 04:08
ham, how does that answers my question? You can define your own `List[T]` which will shade the one in the stdlib, it may cause problems, which is why most people will recommended using a different name. But again the question is, you want to implement your own List, with a couple of methods, from scratch? Or you want to implement your own foldRight function for the list in the stdlib? — Luis Miguel Mejía Suárez, Jun 29 '19 at 04:23
@LuisMiguelMejíaSuárez I want to implement my own foldRight method. I don't care whether it operates on the stdlib List[T] or a customized abstract class. — PhysicsMath, Jun 29 '19 at 04:26
Then you only need to add the `T` type parameter to the definition of the **method**. For example: `def foldRight[T, U](list: List[T])(z : U)(op: (T, U) => U): U = ...` — Luis Miguel Mejía Suárez, Jun 29 '19 at 04:35
@LuisMiguelMejíaSuárez Could you write it up as an answer filling in the detailed code? I will accept it as the answer and endorse it. — PhysicsMath, Jun 29 '19 at 04:54
". 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, Jun 29 '19 at 06:37
@Thilo OK, so List[T], foldRight, Nil, :: are all in stdlib. To make my own abstract class and define similar methods I have to start all over from scratch by defining type T, right? — PhysicsMath, Jun 29 '19 at 06:53
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, Jun 29 '19 at 07:12

Luis Miguel Mejía Suárez · Answer 1 · 2019-06-30T14:43:30.547

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://stackoverflow.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

What a detailed solution and explanation! Starting everything from scratch illustrates clearly how the relevant type and methods are defined in stdlib. Many thanks Luis! — PhysicsMath, Jun 30 '19 at 14:37

Scala Pattern type is incompatible with expected type

1 Answers1