Переменная неоднозначного типа в тесте на пустой список

Рассмотрим следующий фрагмент кода, определяющий функцию foo, которая принимает список и выполняет с ним некоторые операции (например, сортировку). Я попытался загрузить фрагмент в ghci:

-- a function which consumes lists and produces lists
foo :: Ord a => [a] -> [a]
foo [] = []
foo (x:xs) = xs

test1 = foo [1, 2, 3] == [2, 3]
test2 = null $ foo []

но возникает следующая ошибка:

No instance for (Ord a0) arising from a use of ‘foo’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance (Ord a, Ord b) => Ord (Either a b)
        -- Defined in ‘Data.Either’
      instance forall (k :: BOX) (s :: k). Ord (Data.Proxy.Proxy s)
        -- Defined in ‘Data.Proxy’
      instance (GHC.Arr.Ix i, Ord e) => Ord (GHC.Arr.Array i e)
        -- Defined in ‘GHC.Arr’
      ...plus 26 others
    In the second argument of ‘($)’, namely ‘foo []’
    In the expression: null $ foo []
    In an equation for ‘test2’: test2 = null $ foo []

Проблема в выражении test2 = null $ foo []. Более того, удаление ограничения Ord a из определения типа foo решит проблему. Как ни странно, ввод null $ foo [] в интерактивном режиме (после загрузки определения для foo) работает правильно и выдает ожидаемое true.

Мне нужно четкое объяснение такого поведения.


empty-list haskell
person AlQuemist    schedule 17.03.2018    source источник
comment
Возможный дубликат переменной неоднозначного типа, но не в ghci?   -  person jberryman    schedule 17.03.2018
comment
@WillNess: Спасибо. Тем не менее, как вы можете видеть, этот тест бессмысленен, потому что он уже находится в определении функции. Мне нужно только понять, почему возникает эта ошибка.   -  person AlQuemist    schedule 17.03.2018

Ответы (1)


arrow_upward
6
arrow_downward

Мне нравится думать о классах типов в «стиле передачи словаря». Подпись

foo :: Ord a => [a] -> [a]

говорит, что foo берет словарь методов для Ord a, по существу, в качестве параметра, и список as, и возвращает список as. В словаре есть такие вещи, как (<) :: a -> a -> Bool и его кузены. Когда мы вызываем foo, нам нужно предоставить такой словарь. Это делается неявно компилятором. Так

foo [1,2,3]

будет использовать словарь Ord Integer, потому что мы знаем, что a это Integer.

Однако в foo [] список может быть списком чего угодно — нет информации для определения типа. Но нам еще нужно найти словарь Ord для передачи в foo (хотя ваш foo его вообще не использует, в подписи написано, что может, и только это имеет значение). Вот почему возникает ошибка неоднозначного типа. Вы можете указать тип вручную, что даст достаточно информации для заполнения словаря, например

null (foo ([] :: [Integer]))

или с новым расширением TypeApplications

null (foo @Integer [])

Если вы удалите ограничение Ord, оно сработает, как вы заметили, и это только потому, что нам больше не нужно предоставлять словарь. Нам больше не нужно знать, какой конкретный тип a должен вызывать foo (мне это кажется немного волшебным :-).

Обратите внимание, что foo ([] :: Ord a => [a]) не устраняет двусмысленность, потому что неизвестно, какой конкретный Ord словарь вы хотите передать; это Ord Int или Ord (Maybe String) и т. д.? нет универсального словаря Ord, поэтому нам нужно выбрать, и нет правила, какой тип выбрать в этом случае. Принимая во внимание, что когда вы говорите (Ord a, Num a) => [a], тогда значение по умолчанию указывает способ выбора, и мы выбираем Integer, так как это частный случай класса Num.

Тот факт, что foo [] работает в ghci, связан с ghci. " rel="nofollow noreferrer">расширенные правила по умолчанию. Возможно, стоит прочитать об типе по умолчанию в общем, это, конечно, не самая красивая часть Haskell, но она будет часто всплывать в тех крайних случаях, о которых вы спрашиваете.

person luqui    schedule 17.03.2018
comment
но почему тип списка должен иметь значение для null? и ясно, что foo создает список типа Ord a => [a]; разве этого недостаточно для компилятора? - person AlQuemist; 17.03.2018
comment
как ни странно, если войти в null $ foo [] в интерактивном режиме (после загрузки определения foo), он работает без проблем. - person AlQuemist; 17.03.2018
comment
@AlQuemist, это не имеет значения для null, это важно для foo. И foo использует словарь Ord a, в этом проблема (у нас его нет). - person luqui; 17.03.2018
comment
Тот факт, что он работает в ghci, связан с ghci. " rel="nofollow noreferrer">расширенные правила по умолчанию. Возможно, стоит прочитать об типе по умолчанию в общем, это, конечно, не самая красивая часть Haskell, но она будет часто всплывать в тех крайних случаях, о которых вы спрашиваете. - person luqui; 17.03.2018
comment
почему компилятор не может вывести тип [] в тестовом выражении? разве это не должно быть очевидно из определения foo; а именно foo :: Ord a => [a] -> [a]; foo [] = [] ? Я думаю, тип очевиден; нет необходимости в дальнейших церемониях. - person AlQuemist; 18.03.2018
comment
чтобы передать словарь вместе с пустым списком, можем ли мы использовать foo ([] :: Ord a => [a]) для устранения двусмысленности? - person AlQuemist; 18.03.2018
comment
Я обнаружил, что что-то из списка test3 = null $ foo ([] :: (Num a, Ord a) => [a]) решает проблему. - person AlQuemist; 18.03.2018
comment
@AlQuemist, это тоже из-за невыполнения обязательств. Этот тип по умолчанию будет просто [Integer], потому что он включает Num. Это немного окольным путем; Я бы просто использовал конкретный тип, такой как [Integer], напрямую, хотя на самом деле не имеет значения, какой тип вы используете, вы можете использовать что-то сумасшедшее, например null $ foo ([] :: [Either Integer String]). Для меня самый элегантный выбор — null $ foo ([] :: [Void]), потому что там прямо сказано, что список должен быть пустым (по модулю undefined). - person luqui; 19.03.2018
comment
не могли бы вы объяснить, что означает определяющая связь foo :: Ord a => [a] -> [a]; foo [] = [] для компилятора? Я полагаю, что этого было бы достаточно, чтобы компилятор правильно интерпретировал тип [] в таком выражении, как res = foo []. Почему компилятор не уменьшает полиморфный тип [] до правильного типа (например, [Void])? Такое сокращение происходит, например, когда кто-то вызывает функцию bar :: Float -> Float для «полиморфной константы», такой как 2 (выведенный тип будет Float, а не Integer). - person AlQuemist; 20.03.2018
comment
@AlQuemist вы читали о дефолте еще? - person luqui; 20.03.2018
comment
не могли бы вы объяснить, почему foo ([] :: Ord a => [a]) не устраняет двусмысленность при передаче необходимого «словаря»? - person AlQuemist; 28.03.2018
comment
@AlQuemist, потому что неизвестно, какой конкретный Ord словарь вы хотите передать. Это Ord Int или Ord (Maybe String) или как? Общего словаря Ord не существует, только для конкретных a, поэтому нам приходится выбирать, и нет правила, какой тип выбрать в этом случае. Принимая во внимание, что когда вы говорите (Ord a, Num a) => [a], тогда значение по умолчанию указывает способ выбора, и мы выбираем Integer. Это частный случай класса Num. - person luqui; 28.03.2018