Почему идиома рекурсии в Haskell “'n+1' и 'n'” и не “'n' и 'n-1'”?
Я прокладываю себе путь через книгу Haskell Graham Hutton, и в его главе рекурсии, он часто соответствия шаблона на "n+1", как в:
myReplicate1 0 _ = []
myReplicate1 (n+1) x = x : myReplicate1 n x
Почему это а не следующее, которое (1) кажется функционально идентичным и (2) более интуитивный с точки зрения понимания, что происходит с рекурсией:
myReplicate2 0 _ = []
myReplicate2 n x = x : myReplicate2 (n-1) x
Есть ли что-то, что я пропускаю здесь? Или это - просто вопрос стиля?
5 ответов
Это n + k шаблонов (которых следует избегать!) В первой функции. Обе функции делают то же самое, за исключением того, что n + k не соответствует отрицательным числам. Последний вариант, однако, рекомендуется, и может быть принят, если вы не хотите намеренно отрицательные числа , потому что n + k шаблонов планируется удалить в любом случае .
Так что нет, вы ничего не упускаете, и это действительно вопрос стиля, но я редко вижу n + k шаблонов в природе.
myReplicate n x = take n (repeat x)
Сделано и сделано. :D
шаблоны n+k соответствуют только тогда, когда n>=0. Поэтому в вашем myReplicate1 шаблон n+1 будет соответствовать только положительным числам, а отрицательное n приведет к исключению неисчерпывающего шаблона. В myReplicate2 отрицательное n создаст бесконечный список.
Другими словами, вы можете использовать n+k шаблоны, если не хотите, чтобы шаблон совпадал с отрицательными числами, но использование защиты вместо этого будет более понятным.
Шаблоны N + K также имеют разные значения строгости.
Например:
f (n+1) = Just n
g n = Just (n-1)
f строго по своему первому аргументу, g - нет. В этом нет ничего особенного для n + k шаблонов, но это применимо ко всем шаблонам.
Я думаю, что идея заключается в следующем: мы можем определить тип для натуральных чисел (0, 1, ...) следующим образом:
data Natural = Z -- zero
| S Natural -- one plus a number; the next number; the "successor"
0 = Z , 1 = SZ и так далее. Эта система называется арифметикой Пеано и в значительной степени является стандартом в математике как (отправная точка для) определения того, что на самом деле представляет собой «число». Вы можете определить Integer как пары (-ish) чисел Natural и так далее.
Когда вы делаете это, становится естественным использовать сопоставление с образцом следующим образом:
myReplicate1 Z _ = []
myReplicate1 (S n) x = x : myReplicate1 n x
Я думаю (и это всего лишь предположение), что идея, лежащая в основе n + 1 шаблонов, является машинной версией того, что Я только что описал. Итак, n + 1 следует рассматривать как образец S n . Если вы так думаете, паттерны n + 1 кажутся естественными. Это также проясняет, почему у нас есть побочное условие n> = 0 . Мы можем только представить n> = 0 , используя тип Natural .