Не могу разобраться с примитивными определениями рекурсии в haskell

Question

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

Например, я не могуКажется, я объясняю себе, как сделать следующее (хотя я, кажется, могу это сделать):

Упражнение:

Определить функцию productIt :: [Int] -> Int, которая дает произведениесписок целых чисел и возвращает 1 для пустого списка;почему именно это значение выбрано в качестве результата для пустого списка?

Я (конечно) нашел решение:

productIt :: [Int] -> Int
productIt [] = 1
productIt (x:xs) = x * productIt xs

, которое отлично подходит для вопроса вупражнение.Тем не менее, мне все еще кажется, что я не могу разобраться с последней строкой.

Любые идеи о том, как обдумать это, были бы наиболее ценными.

Answer 1

На английском языке вы можете прочитать эту последнюю строку как:

Произведение списка чисел - это первое число, умноженное на произведение остальных чисел.А если цифр нет, то скажем, что продукт равен 1.

. Преобразование его в английский язык, как это обычно помогает мне понять, как и почему работает рекурсивная функция.Вы также можете оценить это с помощью интерпретатора Haskell внутри вашей головы:

  productIt [2,3,4]
= 2 * (productIt [3,4])
= 2 * (3 * (productIt [4]))
= 2 * (3 * (4 * (productIt [])))
= 2 * (3 * (4 * (1)))
= 2 * (3 * (4))
= 2 * (12)
= 24

Answer 2

Причина, по которой вы используете 1 для тривиального случая [], заключается в том, что он не меняет результат при умножении на него.

productIt (x:xs) = x * productIt xs

Предположим, например, что вы определили его так:

productIt [] = 2                      -- line 1
productIt (x:xs) = x * productIt xs   -- line 2

Затем рассмотрим:

productIt [1] = productIt (1:[])
              = 1 * productIt []    -- by line 2
              = 1 * 2               -- by line 1
              = 2                   -- WRONG!!!

Вы ищете произведение списка целых чисел, и для [1] ответ должен быть 1.

Answer 3

Прежде чем я объясню эту последнюю строку кода, позвольте мне кратко описать процесс решения этого типа проблемы. Есть два ключевых вопроса:

1. Какой самый простой случай?
2. Могу ли я выразить решение через следующее простейшее решение?

ОК, поэтому мы хотим написать функцию, которая вычисляет произведение всех чисел в списке.

По вопросу 1. Самый простой возможный случай: чисел нет. Если я впервые столкнулся с проблемой, для меня может быть неясно, каким должен быть ответ в этом случае, но давайте пока отложим это.

По вопросу 2. Если у меня есть список [n0, n1, n2, .. nk], и я каким-то образом знаю произведение (назовем его p) всех чисел, кроме первого, тогда ответ первый элемент умножить на это произведение, или n0 * p.

Первая строка кода позаботится о тривиальном случае:

productIt [] = 1

Это говорит о том, что функция productIt для аргумента пустого списка, [], имеет значение 1. (Я объяснил выше, почему ответ должен быть 1.) Это решает тривиальный случай. Теперь нам нужно определить productIt в случае, если список не пустой. Давайте посмотрим на эту последнюю строку кода:

productIt (x:xs) = ... something?

Левая сторона использует сопоставление с образцом. Шаблон (x: xs) будет соответствовать списку с одним или несколькими элементами. Когда это выражение совпадает, оно связывает x с первым элементом, а xs с остальной частью списка. Таким образом, мы не только сопоставляем шаблон, мы получаем x и xs, определенные как бонус. Вот что делает сопоставление с образцом действительно мощным в Haskell.

Итак, если первый элемент списка - x, а остальная часть списка (все, кроме первого элемента) - xs, то каков ответ? Мы уже решили, что это первый элемент (x), умноженный на произведение всех остальных элементов (xs). Итак ...

productIt (x:xs) = x * productIt xs

Кроме того, yjerem дал вам превосходное объяснение того, как Haskell оценит это.