Ответ 1

Что такое ограничение мономорфизма?

Ограничение мономорфизма, как заявлено в вики Haskell:

нелогичное правило в выводе типа Haskell. Если вы забыли предоставить сигнатуру типа, иногда это правило будет заполнять переменные свободного типа определенными типами, используя правила "тип по умолчанию".

Это означает, что в некоторых случаях, если ваш тип неоднозначный (то есть полиморфный), компилятор решит создать экземпляр этого типа для чего-то не двусмысленного.

Как мне это исправить?

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

plus :: Num a => a -> a -> a
plus = (+)    -- Okay!

-- Runs as:
Prelude> plus 1.0 1
2.0

В качестве альтернативы, если вы определяете функцию, вы можете избежать бессмысленного стиля и, например, написать:

plus x y = x + y

Выключить его

Можно просто отключить ограничение, чтобы вам не пришлось ничего делать со своим кодом, чтобы это исправить. Поведение контролируется двумя расширениями: MonomorphismRestriction включит его (по умолчанию), а NoMonomorphismRestriction отключит его.

Вы можете поместить следующую строку в самый верх вашего файла:

{-# LANGUAGE NoMonomorphismRestriction #-}

Если вы используете GHCi, вы можете включить расширение с помощью команды :set:

Prelude> :set -XNoMonomorphismRestriction

Вы также можете указать ghc включить расширение из командной строки:

ghc ... -XNoMonomorphismRestriction

Примечание: вы действительно должны предпочесть первый вариант, а не выбирать расширение с помощью параметров командной строки.

Обратитесь к странице GHC для объяснения этого и других расширений.

Полное объяснение

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

Пример

Примите следующее тривиальное определение:

plus = (+)

можно подумать, что можно заменить каждое вхождение + на plus. В частности, поскольку (+) :: Num a => a → a → a вы ожидаете также иметь plus :: Num a => a → a → a.

К сожалению, это не случай. Например, в GHCi мы попробуем следующее:

Prelude> let plus = (+)
Prelude> plus 1.0 1

Мы получаем следующий вывод:

<interactive>:4:6:
    No instance for (Fractional Integer) arising from the literal ‘1.0
    In the first argument of ‘plus, namely ‘1.0
    In the expression: plus 1.0 1
    In an equation for ‘it: it = plus 1.0 1

^{Вам может потребоваться :set -XMonomorphismRestriction в более новых версиях :set -XMonomorphismRestriction.}

И на самом деле мы видим, что тип plus не тот, который мы ожидаем:

Prelude> :t plus
plus :: Integer -> Integer -> Integer

Случилось так, что компилятор увидел, что plus имеет тип Num a => a → a → a, полиморфный тип. Более того, случается, что приведенное выше определение подпадает под правила, которые я объясню позже, и поэтому он решил сделать тип мономорфным, установив по умолчанию переменную типа a. По умолчанию это Integer как мы видим.

Обратите внимание, что если вы попытаетесь скомпилировать приведенный выше код, используя ghc вы не получите никаких ошибок. Это связано с тем, как ghci обрабатывает (и должен обрабатывать) интерактивные определения. По сути, каждый оператор, введенный в ghci должен быть полностью проверен на тип перед рассмотрением следующего; другими словами это как если бы каждое утверждение было в отдельном модуле. Позже я объясню, почему это так.

Какой-то другой пример

Рассмотрим следующие определения:

f1 x = show x

f2 = \x -> show x

f3 :: (Show a) => a -> String
f3 = \x -> show x

f4 = show

f5 :: (Show a) => a -> String
f5 = show

Мы ожидаем, что все эти функции будут вести себя одинаково и иметь одинаковый тип, то есть тип show: Show a => a → String.

Тем не менее при компиляции приведенных выше определений мы получаем следующие ошибки:

test.hs:3:12:
    No instance for (Show a1) arising from a use of ‘show
    The type variable ‘a1 is ambiguous
    Relevant bindings include
      x :: a1 (bound at blah.hs:3:7)
      f2 :: a1 -> String (bound at blah.hs:3:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float
      instance Show Float -- Defined in ‘GHC.Float
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real
      ...plus 24 others
    In the expression: show x
    In the expression: \ x -> show x
    In an equation for ‘f2: f2 = \ x -> show x

test.hs:8:6:
    No instance for (Show a0) arising from a use of ‘show
    The type variable ‘a0 is ambiguous
    Relevant bindings include f4 :: a0 -> String (bound at blah.hs:8:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float
      instance Show Float -- Defined in ‘GHC.Float
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real
      ...plus 24 others
    In the expression: show
    In an equation for ‘f4: f4 = show

Таким образом, f2 и f4 не компилируются. Более того, при попытке определить эти функции в GHCi мы не получаем ошибок, но тип для f2 и f4 - () → String !

Ограничение мономорфизма - это то, что заставляет f2 и f4 требовать мономорфного типа, а разное поведение между ghc и ghci обусловлено разными правилами по ghci.

Когда это происходит?

В Haskell, как определено в отчете, есть два разных типа привязок. Функциональные привязки и привязки к шаблону. Привязка функции - это не что иное, как определение функции:

f x = x + 1

Обратите внимание, что их синтаксис:

<identifier> arg1 arg2 ... argn = expr

^{По модулю охранники и where декларации.Но они на самом деле не имеют значения.}

где должен быть хотя бы один аргумент.

Привязка к шаблону - это объявление формы:

<pattern> = expr

^{Опять по модулю охранников.}

Обратите внимание, что переменные являются шаблонами, поэтому связывание:

plus = (+)

это шаблон привязки. Связывает шаблон plus (переменную) с выражением (+).

Когда привязка шаблона состоит только из имени переменной, это называется простой привязкой шаблона.

Ограничение мономорфизма применяется к простым привязкам к шаблону!

Ну, формально мы должны сказать, что:

Группа объявлений - это минимальный набор взаимозависимых привязок.

^{Раздел 4.5.1 отчета.}

А затем (раздел 4.5.5 отчета):

данная группа объявлений является неограниченной, если и только если:

1. каждая переменная в группе связана привязкой функции (например, fx = x) или простой привязкой к шаблону (например, plus = (+); раздел 4.4.3.2), и

2. явная сигнатура типа дается для каждой переменной в группе, которая связана простой привязкой к шаблону. (например, plus :: Num a => a → a → a; plus = (+)).

^{Примеры, добавленные мной.}

Таким образом, группа ограниченного объявления - это группа, в которой либо существуют непростые привязки к шаблону (например, (x:xs) = f something или (f, g) = ((+), (-))), либо есть несколько привязка к шаблону без сигнатуры типа (как в plus = (+)).

Ограничение мономорфизма влияет на ограниченные группы объявлений.

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

Что оно делает?

Ограничение мономорфизма описывается двумя правилами в разделе 4.5.5 отчета.

Первое правило

Обычное ограничение Хиндли-Милнера на полиморфизм состоит в том, что только переменные типа, которые не встречаются свободно в среде, могут быть обобщены. Кроме того, переменные ограниченного типа в группе ограниченного объявления не могут быть обобщены на этапе обобщения для этой группы. (Напомним, что переменная типа ограничена, если она должна принадлежать некоторому классу типа; см. Раздел 4.5.2.)

Выделенная часть - это то, что вводит ограничение мономорфизма. Это говорит о том, что если тип полиморфный (то есть содержит некоторую переменную типа) и эта переменная типа ограничена (то есть имеет ограничение класса: например, тип Num a => a → a → a является полиморфным, поскольку содержит a а также запрещено, потому что a имеет ограничение Num над ним.) тогда оно не может быть обобщено.

Проще говоря, не обобщение означает, что использование функции plus может изменить ее тип.

Если у вас были определения:

plus = (+)

x :: Integer
x = plus 1 2

y :: Double
y = plus 1.0 2

тогда вы получите ошибку типа. Потому что, когда компилятор видит, что plus вызывается через Integer в объявлении x он объединяет переменную типа a с Integer и, следовательно, тип plus становится:

Integer -> Integer -> Integer

но затем, когда он напечатает проверку определения y, он увидит, что plus применяется к аргументу Double, а типы не совпадают.

Обратите внимание, что вы все еще можете использовать plus без получения ошибки:

plus = (+)
x = plus 1.0 2

В этом случае тип plus сначала выводится как Num a => a → a → a но затем его использование в определении x, где 1.0 требует Fractional ограничения, изменит его на Fractional a => a → a → a.

обоснование

В отчете говорится:

Правило 1 требуется по двум причинам, обе из которых довольно тонкие.

• Правило 1 предотвращает неожиданное повторение вычислений. Например, genericLength - это стандартная функция (в библиотеке Data.List), тип которой определяется

  genericLength :: Num a => [b] -> a
  

  Теперь рассмотрим следующее выражение:

  let len = genericLength xs
  in (len, len)
  

  Похоже, что len должен быть вычислен только один раз, но без правила 1 он может быть вычислен дважды, один раз при каждой из двух разных перегрузок. Если программист действительно хочет, чтобы вычисление повторялось, можно добавить явную сигнатуру типа:

  let len :: Num a => a
      len = genericLength xs
  in (len, len)
  

На данный момент, пример из вики, на мой взгляд, более понятен. Рассмотрим функцию:

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

Если бы len было полиморфным, тип f был бы:

f :: Num a, Num b => [c] -> (a, b)

Таким образом, два элемента кортежа (len, len) могут фактически иметь разные значения! Но это означает, что вычисление, выполненное genericLength должно быть повторено, чтобы получить два разных значения.

Обоснование здесь таково: код содержит один вызов функции, но не введение этого правила может привести к двум вызовам скрытых функций, что противоречит интуиции.

С ограничением мономорфизма тип f становится:

f :: Num a => [b] -> (a, a)

Таким образом, нет необходимости выполнять вычисления несколько раз.

• Правило 1 предотвращает двусмысленность. Например, рассмотрим группу объявлений

  [(n, s)] = читает

  Напомним, что reads - это стандартная функция, тип которой определяется сигнатурой.

  читает :: (Читать a) => Строка → [(a, Строка)]

  Без правила 1 n был бы присвоен тип ∀ a. Read a ⇒ a ∀ a. Read a ⇒ a и s типа ∀ a. Read a ⇒ String ∀ a. Read a ⇒ String. Последний является недопустимым типом, потому что он по своей сути неоднозначен. Невозможно определить, для какой перегрузки использовать s, и это не может быть решено путем добавления сигнатуры типа для s. Следовательно, когда используются непростые привязки к шаблону (раздел 4.4.3.2), выведенные типы всегда мономорфны в своих переменных ограниченного типа, независимо от того, предоставляется ли сигнатура типа. В этом случае оба n и s мономорфны в a.

Ну, я считаю, что этот пример говорит сам за себя. Существуют ситуации, когда неприменение правила приводит к неоднозначности типа.

Если вы отключите расширение, как предложено выше, вы получите ошибку типа при попытке скомпилировать вышеуказанное объявление. Однако на самом деле это не проблема: вы уже знаете, что при использовании read вы должны как-то указать компилятору, какой тип он должен пытаться проанализировать...

Второе правило

2. Любые переменные мономорфного типа, которые остаются, когда вывод типа для всего модуля завершен, считаются неоднозначными и разрешаются к определенным типам с использованием правил по умолчанию (раздел 4.3.4).

Это означает, что. Если у вас есть обычное определение:

plus = (+)

Это будет иметь тип Num a => a → a → a где a - переменная мономорфного типа из-за правила 1, описанного выше. Как только весь модуль будет выведен, компилятор просто выберет тип, который заменит его a соответствии с правилами по умолчанию.

Окончательный результат: plus :: Integer → Integer → Integer.

Обратите внимание, что это делается после вывода всего модуля.

Это означает, что если у вас есть следующие объявления:

plus = (+)

x = plus 1.0 2.0

внутри модуля перед типом по умолчанию тип plus будет: Fractional a => a → a → a (см. правило 1, почему это происходит). На этом этапе, следуя правилам по умолчанию, a будет заменен на Double и поэтому у нас будет plus :: Double → Double → Double и x :: Double.

Дефолт

Как указывалось ранее, существуют некоторые правила по умолчанию, описанные в Разделе 4.3.4 Отчета, которые может принять эксперт, который заменит полиморфный тип на мономорфный. Это происходит всякий раз, когда тип неоднозначен.

Например, в выражении:

let x = read "<something>" in show x

здесь выражение неоднозначно, потому что типы для show и read:

show :: Show a => a -> String
read :: Read a => String -> a

Таким образом, x имеет тип Read a => a. Но это ограничение удовлетворяется многими типами: Int, Double или () например. Какой выбрать? Там нет ничего, что может сказать нам.

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

let x = read "<something>" :: Int in show x

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

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

show 1

Каким должен быть результат?

Как и раньше, 1 имеет тип Num a => a и существует множество типов чисел, которые можно использовать. Какой выбрать?

Наличие ошибки компилятора почти каждый раз, когда мы используем число, не очень хорошая вещь, и поэтому были введены правила по умолчанию. Правилами можно управлять с помощью декларации по default. Указав default (T1, T2, T3) мы можем изменить способ, используемый логическим выводом по умолчанию для различных типов.

Переменная неоднозначного типа v является неплатежеспособной, если:

• v появляется только в ограничениях типа C v C является классом (т.е. если он выглядит так же, как в: Monad (mv) то он не подлежит дефолту).
• по крайней мере, один из этих классов является Num или подклассом Num.
• все эти классы определены в Prelude или стандартной библиотеке.

Переменная типа по default заменяется первым типом в списке по default который является экземпляром всех классов неоднозначных переменных.

Декларация по default - по default (Integer, Double).

Например:

plus = (+)
minus = (-)

x = plus 1.0 1
y = minus 2 1

Предполагаемые типы будут:

plus :: Fractional a => a -> a -> a
minus :: Num a => a -> a -> a

которые по умолчанию нарушают правила:

plus :: Double -> Double -> Double
minus :: Integer -> Integer -> Integer

Обратите внимание, что это объясняет, почему в примере в вопросе только определение sort вызывает ошибку. Тип Ord a => [a] → [a] не может быть установлен по умолчанию, потому что Ord не является числовым классом.

Расширенные настройки по умолчанию

Обратите внимание, что GHCi поставляется с расширенными правилами по умолчанию (или здесь для GHC8), которые также можно включить в файлах, используя расширения ExtendedDefaultRules.

Переменные типа по умолчанию должны появляться не только в ограничениях, где все классы являются стандартными, и должен быть хотя бы один класс из Eq, Ord, Show или Num и его подклассов.

Кроме того, объявлением по умолчанию по default является default ((), Integer, Double).

Это может привести к странным результатам. Взяв пример из вопроса:

Prelude> :set -XMonomorphismRestriction
Prelude> import Data.List(sortBy)
Prelude Data.List> let sort = sortBy compare
Prelude Data.List> :t sort
sort :: [()] -> [()]

в ghci мы не получаем ошибку типа, но ограничение Ord a приводит к дефолту () который в значительной степени бесполезен.

Полезные ссылки

Есть много ресурсов и дискуссий об ограничении мономорфизма.

Вот некоторые ссылки, которые я считаю полезными и которые могут помочь вам понять или углубиться в тему:

• Вики-страница на Haskell: ограничение мономорфизма
• Отчет
• Доступный и красивый пост в блоге
• Разделы 6.2 и 6.3 " Истории Хаскелла: быть ленивым с классом" имеют дело с ограничением мономорфизма и типом по умолчанию