Почему вывод типа Scala не такой мощный, как у Haskell?

Question

Механизм логического вывода в Haskell намного мощнее, чем в Scala. В Haskell мне редко приходится явно писать типы, тогда как в Scala типы можно выводить только в выражениях, но не в определениях методов.

Например, см. Следующий фрагмент кода на Haskell:

size xs = loop xs 0
  where
    loop [] acc = acc
    loop (_ : xs) acc = loop xs (acc+1)

Возвращает размер списка. Компилятор Haskell может распознать, какие типы используются и каково определение функции. Эквивалентный код Scala:

def size[A]: List[A] => Int = xs => {
  def loop: (List[A], Int) => Int = {
    case (Nil, acc) => acc
    case (_ :: xs, acc) => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Или с определениями метода:

def size[A](xs: List[A]) = {
  def loop(xs: List[A], acc: Int): Int = xs match {
    case Nil => acc
    case _ :: xs => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Мой вопрос: почему я не могу написать их следующим образом?

def size = xs => {
  def loop = {
    case (Nil, acc) => acc
    case (_ :: xs, acc) => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Еще раз с определениями методов:

def size(xs) = {
  def loop(xs, acc) = xs match {
    case Nil => acc
    case _ :: xs => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Это потому, что никто еще не реализовал это? Разве система типов Scala не настолько мощна, как это необходимо для этого случая? Или есть другие причины?

Answer 1

Основная причина в том, что система типов Scala допускает подтипирование, которое не поддерживается алгоритмом вывода типов Хиндли-Милнера.

В Haskell нет подтипов, поэтому алгоритм работает там гораздо лучше, хотя многие популярные расширения системы типов, поддерживаемые GHC, приводят к тому, что вывод типов снова завершается ошибкой, вынуждая вас предоставлять явные сигнатуры типов для некоторых выражений.

В конце концов, это компромисс между мощью системы типов и количеством выводов типов, которые могут быть сделаны. Scala и Haskell просто сделали разные компромиссы.

Answer 2

Я думаю, что основные причины уже были приведены, но я нахожу эту цитату создателя Scala Мартина Одерского особенно информативной,

Причина, по которой Scala не имеет логического вывода типа Хиндли / Милнера, заключается в том, что его очень трудно комбинировать с такими функциями, как перегрузка (специальный вариант, не классы типов), выбор записей и подтипирование. Я не говорю невозможное - существует ряд расширений, которые включают эти функции; На самом деле, я сам был в отношении некоторых из них. Я просто говорю, что очень трудно заставить это работать хорошо на практике, где нужно иметь небольшие шрифтовые выражения и хорошие сообщения об ошибках. Это также не закрытый случай - многие исследователи работают над расширением границ (посмотрите, например, на MLF Реми). Но сейчас это компромисс между лучшим выводом типа и лучшей поддержкой этих функций. Вы можете сделать компромисс в обоих направлениях. Тот факт, что мы хотели интегрироваться с Java, склонял чашу весов в пользу подтипов и далек от Хиндли / Милнера.

Источник: комментарий под постом. Универсальный вывод типа - плохая вещь.

Answer 3

Хаммар дал самую большую причину. Вот два других:

• Scala использует типы для разрешения имен

Рассматривать

def foo(x) = x.a + x.b

Как мог Scala определить тип аргумента? Должен ли он искать каждый класс с a а также b поле? Что делать, если их больше 1? В хаскеле

foo x = (a x) + (b x)

Имена записей уникальны, что создает свои собственные проблемы, но означает, что вы всегда можете сделать вывод, к какой записи относится ссылка.

• Для вашего примера: case выражения в Scala могут быть неоднородными

В Scala тип сопоставляемого объекта можно использовать либо как часть сопоставления, либо чтобы решить, как сопоставление должно быть выполнено. Так что даже если все конструкторы в case для List, вы можете захотеть передать ему что-то кроме списка и потерпеть неудачу.

Answer 4

Еще одна вещь, которая не очень хорошо работает с выводом типа Хиндли-Милнера, - это перегрузка методов и связанные с ними функции, такие как аргументы по умолчанию и переменные. Вот почему так сложно писать такие вещи, как zipWithN в Haskell (что тривиально в Scala).

Answer 5

Я читал некоторые ответы выше, однако некоторые из таких выводов могут быть поставлены под сомнение, когда вы понимаете, что F# включает в себя полное подтипирование с ООП в рамках вывода типа Хиндли-Милнера с 2006 года.

4. Добавление разрешения перегрузки методов и объектных выражений для взаимодействия с .NET (2004 г.)

6. Добавление конструкций класса/интерфейса для объектного программирования (2005 г.)

5. Добавление «статически разрешенных параметров типа» для обработки перегруженных арифметических операций в соответствии с выводом типа Хиндли-Милнера (2005 г.)

9. Добавление обработки подтипов в вывод типа Хиндли-Милнера (2006 г.)

Исходная история F#