Почему Haskell не может избежать повторной оценки без ограничения мономорфизма?

14

Я только что закончил учить вас на днях, и я пытался разобраться в ограничении мономорфизма, как описано в Haskell Wiki . Я думаю, что понимаю, как MR может предотвратить повторные оценки, но я не понимаю, почему этих повторных оценок нельзя избежать гораздо более простыми способами.

Я имею в виду конкретный пример, используемый вики:

f xs = (len,len)
  where
    len = genericLength xs

где genericLengthтипа Num a => [b] -> a.

Очевидно, что genericLength xsдля вычисления необходимо вычислить только один раз (len,len), поскольку это одна и та же функция с одинаковыми аргументами. И нам не нужно видеть никаких призывов, fчтобы знать это. Так почему же Haskell не может выполнить эту оптимизацию без введения правила, подобного MR?

Обсуждение на этой вики-странице говорит мне, что это как-то связано с тем, что Numэто класс типов, а не конкретный тип, но даже в этом случае, если во время компиляции не должно быть очевидным, что чистая функция будет возвращать то же значение, и, следовательно, тот же конкретный тип Num - когда приводятся одни и те же аргументы дважды?

Ixrec
источник

Ответы:

11

Это то же имя функции, с теми же аргументами, но потенциально разными типами возвращаемых значений и реализациями, потому что это полиморфно. Это означает, что если он (Int, MyWeirdCustomNumType)вызывается в контексте, ожидающем возвращаемый тип, он должен оценить его дважды, поскольку реализация (+)in Intполностью отличается от реализации (+)in MyWeirdCustomNumType. Вам нужно запустить физически другой код в какой-то момент.

Вот почему важно, чтобы Numэто был класс типов. Это означает, что у вас есть разные реализации для разных типов. Это также означает, что если он fнаходится в библиотеке, он не знает во время компиляции обо всех комбинациях типов, которые он может возвращать.

Итак, да, вам нужно увидеть вызовы, fчтобы узнать, какие типы возвращаемых значений использовать. В большинстве случаев можно ожидать, что они будут одинаковыми, поэтому по умолчанию они вводят ограничение мономорфизма. Его можно отключить в тех редких случаях, когда вы этого не сделаете. На практике программисты в любом случае не склонны оставлять подобные ситуации вплоть до вывода типа.

Карл Билефельдт
источник
Я не рассматривал возможность f [] :: (Int, Float). Теперь это имеет смысл. Спасибо.
Ixrec
1
It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic.Я думаю, что лучший способ взглянуть на это состоит в том, что экземпляр класса типов является фактически дополнительным аргументом, genericLengthи компилятор не уверен, что это одни и те же аргументы в обоих вызовах.
Довал
Быстрый побочный вопрос. Если MonomorphismRestriction отключен, но позже вы сделали что-то вроде: a = uncurry (==) $ f [1, 2, 3]сможет ли он оптимизировать этот сайт вызовов, чтобы проверять только длину [1, 2, 3]один раз? Если так, то я действительно смущен тем, что ограничение мономорфизма действительно покупает вас, если нет, то почему нет?
точка с запятой