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

Question

Я работаю свой путь через Haskell книгу Грэма Хаттона, и в его рекуррентной главе, он часто модельные матчи на «п + 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 шаблонов задано как removed anyways.

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

Answer 2

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

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

Answer 3

myReplicate n x = take n (repeat x) 

Выполнено и сделано. : D

Answer 4

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

Например:

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

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

Answer 5

Я думаю, что идея позади этого заключается в следующем: Мы можем определить (медленный) вид натурального типа номера, как это:

data Natural = Zero | S Integer 

Так 0 == Zero, 1 == S Zero и так далее.

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

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

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

Это также дает понять, почему у нас есть боковое условие, которое n>=0. Мы можем представить только n>=0, используя тип Natural.