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

Механизм вывода типа 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 не такой мощной, как необходимо для этого случая? Или есть другие причины?

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

Рассмотрим

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

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

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

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

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

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

Ответ 3

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

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

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