Реализация haskell "zip" странная ошибка

Question

У меня есть следующая реализация функции zip в haskell

myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a,z) : myzip b g

Когда я загружаю его в ghci, я получаю следующую ошибку

No instance for (Eq b)
  arising from a use of `=='
In the expression: g == []
In a stmt of a pattern guard for
               an equation for `myzip':
  g == []
In an equation for `myzip':
    myzip (a : b) (z : g)
      | b == [] = []
      | g == [] = []
      | otherwise = (a, z) : myzip b g

Сбой, загруженные модули: нет.

Я действительно не уверен, почему это не работает. Кто-нибудь может мне помочь?

Answer 1

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

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a, z) : myzip b g

С явной подписью типа, говорящей, что myzip работает над списком любых типов a а также b, Но вы использовали b == [] а также g == [], Оператор равенства не определен ни для одного типа, а только для типов, которые являются членами Eq type class, поэтому код, который вы написали, не соответствует типу, который вы дали.

Это то, о чем прямо говорится в сообщении об ошибке, но если вы только учитесь и еще не освоили классы, то это немного неясно.

Если вы измените тип подписи для myzip чтобы сказать это a а также b должны быть членами Eq введите class, тогда код, который вы дали, будет работать:

myzip :: (Eq a, Eq b) => [a] -> [b] -> [(a, b)]

Или, если вы полностью отключите сигнатуру типа (как вы делали в вопросе), GHC фактически выведет этот тип из того факта, что вы использовали == оператор, и код просто компилируется как есть.

Однако проверить, является ли список пустым, можно без использования == оператор, так что вы можете написать myzip так что он действительно работает на любых типах a а также b, Одним из способов является использование null функция:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | null b = []
    | null g = []
    | otherwise = (a, z) : myzip b g

Но гораздо более распространенным способом является использование нескольких уравнений для определения myzip с базовыми случаями, совпадающими с шаблоном [] и основной случай, в котором предполагается, что списки не пусты:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:[]) _ = []
myzip _ (z:[]) = []
myzip (a:b) (z:g) = (a, z) : myzip b g

Обратите внимание, что этот стиль также сделал очевидным, что в вашей реализации есть ошибка. Ты выбрасываешь последний a или же z и не бывает случаев, когда списки полностью пусты!

Когда ваше уравнение говорит myzip (a:b) (z:g) а потом проверил b а также g против пустого списка, он на самом деле проверял не то, что слишком поздно. Вам не нужно проверять, если b является [] необходимо проверить, был ли весь список пуст. Но вы уже предположили, что он не пустой, и разложили его на a:b, Это приводит к тому, что ваш код (а) возвращает неправильный результат, поскольку он отбрасывает последнюю пару элементов, которые он должен заархивировать, и (б) выдает ошибку, когда одним из аргументов является пустой список.

Рекурсия в списках обычно выглядит примерно так:

myzip :: [a] -> [b] -> [(a, b)]
myzip [] _ = []
myzip _ [] = []
myzip (a:b) (z:g) = (a, z) : myzip b g

Это ведет себя правильно.