Как система типов Scala узнает, что cons + Nil является исчерпывающим?

Я просто написал эту функцию, гадая, что произойдет, если я пропущу регистр Nil, и заметил, что scalac выдает предупреждение:

def printList[String](list: List[String]) {
    list match {
        case head :: tail => {
            println(head)
            printList(tail)
        }
        //case Nil => println("Done")
    }
}

Warning: match may not be exhaustive. It would fail on the following input: Nil

У меня проблемы с точным определением того, что здесь происходит. Я получаю общее представление о сопоставлении с образцом в рекурсивном типе данных, пока вы не исчерпываете все случаи, но мне не ясно, как это соотносится с системой типов Scala. В частности, я смотрю на исходный код стандартной библиотеки Scala и задаюсь вопросом:

  1. Где именно в коде Scala понимает, что для выполнения оператора соответствия для экземпляра класса List требуется базовый случай? Конечно, можно представить себе алгебраический тип данных, который «просто продолжает работать» без базового случая.
  2. Где именно в коде scala.collection.immutable.Nil, в частности, обозначен как базовый вариант для класса List?

scala type-systems algebraic-data-types
person Brian Gordon    schedule 05.05.2015    source источник
comment
Кровавые подробности реализации сопоставления типов в Scala приведены здесь: lampwww.epfl.ch / ~ эмир / написано /   -  person BadZen    schedule 05.05.2015
comment
Для Nil речь идет не о базовом случае. List запечатан, поэтому компилятор знает, какие типы искать в совпадении, а именно :: и Nil. Когда один из них отсутствует, это довольно хороший намек на то, что это не исчерпывающий матч.   -  person Michael Zajac    schedule 05.05.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете увидеть исходный код для List здесь. С базовыми случаями нет ничего особенного, просто List объявлен как sealed, а затем есть только два класса, расширяющих его:

sealed abstract class List[+A] ...
case object Nil extends List[Nothing] { ... }
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] { ... }

Компилятор Scala может довольно легко определить, соответствует ли запечатанный типаж или абстрактный класс исчерпывающим образом, поскольку он может определить совокупность возможных совпадений в одном файле. Раздел 8.4 Scala спецификация говорит:

Если селектор сопоставления с образцом является экземпляром запечатанного класса, компиляция сопоставления с образцом может выдавать предупреждения, которые диагностируют, что данный набор образцов не является исчерпывающим, т. Е. Существует вероятность возникновения MatchError во время выполнения. .

person Ben Reich    schedule 05.05.2015
comment
Какое разочарование. Я думал, что он творит какую-то магию разложения, как OCaml. Спасибо, что процитировали соответствующий абзац из спецификации. - person Brian Gordon; 05.05.2015

arrow_upward
7
arrow_downward

На самом деле это не так сложно, как вы думаете. List - это sealed abstract class с двумя реализациями, Nil и :: (да, это имя класса). Важная часть здесь - модификатор sealed. Это просто приводит к тому, что любой класс, реализующий List должен находиться в том же исходном файле, что и сам List.

Важность sealed заключается в том, что теперь компилятор наверняка знает всех возможных разработчиков List, поэтому, если вы сопоставите шаблон со списком, компилятор сможет выяснить, является ли ваш блок сопоставления шаблонов исчерпывающим.

И последнее, что нужно понять, это то, что с :: происходит некоторый синтаксический сахар. Обычно, если у вас есть класс case:

case class Foo(a: String, b: Int)

вы бы сопоставили это как таковое

x match {
  case Foo(a, b) => //...
}

Однако, если у вас есть класс case ровно с двумя членами, вы также можете написать его как таковой:

x match {
  case a Foo b => //...
}

Итак, в вашем операторе сопоставления с образцом вы действительно делаете:

list match {
        case ::(head, tail) => {

так что на самом деле все, что вы делаете, это проверяете, является ли список экземпляром ::. Таким образом, компилятор видит, что вы никогда не проверяете, является ли список экземпляром Nil, и предупреждает вас.

person Dan Simon    schedule 05.05.2015