Haskell (n + 1) в сопоставлении с образцом - PullRequest
Новая
       0

Haskell (n + 1) в сопоставлении с образцом

20 голосов
/ 06 февраля 2011

Я делал 99 Проблемы в Haskell , когда я столкнулся с решением до Проблема 19 , которую я не полностью понял.

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

*Main> rotate ['a','b','c','d','e','f','g','h'] 3
"defghabc"

*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)
"ghabcdef"

Одно из предоставленных решений - 

rotate [] _ = []
rotate l 0 = l
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n
rotate l n = rotate l (length l + n)

Я не понимаю, как сопоставление с образцом может когда-либо достигать четвертой строки. Кажется, это связано с (n+1), так что когда n отрицателен, третья строка не совпадает и, следовательно, берется четвертая строка. Если это так, то почему обозначение (n+1) работает именно так? Разве это не произвольно или это соглашение (в математике?), о котором я не знаю?

Потому что, насколько я понимаю, вращение вызывается рекурсивно в третьей строке с аргументом n, уменьшенным на единицу. Так что я думаю, что 

rotate [] _ = []
rotate l 0 = l
rotate (x:xs) n = rotate (xs ++ [x]) (n-1)
rotate l n = rotate l (length l + n)

эквивалентно. Однако это не так. Это определение дает следующее предупреждение 

Warning: Pattern match(es) are overlapped
         In the definition of `rotate': rotate l n = ...

тогда как предыдущее определение прекрасно компилируется.

1 Ответ

27 голосов
/ 06 февраля 2011

Это особый случай того, что называется «n + k шаблонов», которое обычно не нравится, и будет удалено из языка . См. здесь для получения дополнительной информации.

Здесь - хорошее примечание по n + k шаблонам, которое цитирует следующее из отчета Haskell 98 (выделено мной):

Соответствует шаблону n + k (где n - это переменная и k является положительным целым числом буквально) против значения v успешно, если x> = k , что приводит к связыванию n к х - к, и не в противном случае. Снова, функции> = и - перегружены, в зависимости от типа рисунка. Совпадение расходится, если сравнение расходится.

Интерпретация литерала k так же, как в числовом литерале шаблоны, кроме того, что только целое число допускаются литералы.

Таким образом, n+1 соответствует, только если n равно как минимум 1, как вы и предполагали. Ваш альтернативный код снимает это ограничение, что приводит к совпадению шаблонов.

...