Почему идиома рекурсии в Haskell «n + 1» и «n», а не «n» и «n-1»?

Question

Я работаю над книгой Грэма Хаттона на Хаскелле, и в своей главе по рекурсии он часто сопоставляет паттерны по "n + 1", например:

myReplicate1 0 _ = []
myReplicate1 (n+1) x = x : myReplicate1 n x

Почему это, а не следующее, которое (1) кажется функционально идентичным и (2) более интуитивным с точки зрения понимания того, что происходит с рекурсией:

myReplicate2 0 _ = []
myReplicate2 n x = x : myReplicate2 (n-1) x

Есть ли что-то, что я здесь упускаю? Или это просто вопрос стиля?

Answer 1

Это n + k паттернов (которых следует избегать!) В первой функции. Обе функции выполняют одно и то же, , за исключением того, что n + k не соответствует отрицательным числам. Однако рекомендуется последняя, ​​, и ее можно использовать, если вы намеренно не хотите использовать отрицательные числа , потому что n + k шаблонов планируется удалить в любом случае .

Так что нет, вы ничего не упускаете, и это действительно вопрос стиля, но я редко вижу n + k паттернов в дикой природе.

Answer 2

Я думаю, что идея заключается в следующем: мы можем определить тип для натуральных чисел (0, 1, ...) следующим образом:

data Natural = Z -- zero
             | S Natural -- one plus a number; the next number; the "successor"

0 = Z, 1 = S Z,и так далее.Эта система называется арифметикой Пеано и является в значительной степени стандартом в математике как (отправная точка для) определения того, что на самом деле является «числом».Вы можете определить Integer s как пары (-ish) из Natural s и т. Д.

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

myReplicate1 Z _ = []
myReplicate1 (S n) x = x : myReplicate1 n x

Я думаю (и это только предположение), что идея шаблонов n+1 является машинной версией того, что я только что описал.Таким образом, n+1 следует рассматривать как образец S n.Если вы думаете так, шаблоны n+1 кажутся естественными.Это также проясняет, почему у нас есть побочное условие, что n >= 0.Мы можем только представить n >= 0 используя тип Natural.

Answer 3

Шаблоны

N + K также имеют различные значения строгости.

Например:

f (n+1) = Just n
g n = Just (n-1)

f строго по своему первому аргументу, g - нет. Это не является чем-то особенным для n + k шаблонов, но относится ко всем шаблонам.

Answer 4

n + k паттернов совпадают только когда n> = 0.Таким образом, в вашем myReplicate1 шаблон n + 1 будет соответствовать только положительным числам, а отрицательный n вызовет исключение неисчерпывающего шаблона.В myReplicate2 отрицательный n будет создавать бесконечный список.

Таким образом, другими словами, вы можете использовать n + k шаблонов, когда вы не хотите, чтобы шаблон совпадал с отрицательными числами, но вместо этого будет лучше использовать защитный элемент.

Answer 5

myReplicate n x = take n (repeat x)

Готово и сделано. : D