Как add1 используется в этой программе Racket?

Ради другого объяснения:

Здесь мы начинаем

(my-length '(a b c d))

Заполняя аргумент в функцию, это превращается в

(if (empty? '(a b c d))
  0
  (add1 (my-length (rest '(a b c d)))))

Очевидно, что '(a b c d) не пусто. Таким образом, оценивается "else" случай if:

(add1 (my-length (rest '(a b c d))))
(add1 (my-length '(b c d)))

Теперь, что означает (my-length '(b c d))? Что ж, если мы скопируем и вставим тело функции в нашу последнюю строку, мы получим:

(add1 (if (empty? '(b c d))
        0
        (add1 (my-length (rest '(b c d))))))

Продолжая...

(add1 (add1 (my-length (rest '(b c d)))))
(add1 (add1 (my-length '(c d))))

Так продолжается до тех пор, пока мы не получим пустой список:

(add1 (add1 (add1 (add1 (if (empty? '())
                              0
                              (add1 (my-length (rest '()))))))))

'() пусто, поэтому оператор if возвращает 0:

(add1 (add1 (add1 (add1 0))))
(add1 (add1 (add1 1)))
(add1 (add1 2))
(add1 3)
4

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

Чем это отличается от (add1 '(a b c d))? Из того, как проводилась оценка, видно, что add1 на самом деле никогда не применялось к a, b, c или d. Мы даже не проверили, что было в списке. У вас мог бы быть список из четырех списков, каждый из которых содержал бы списки списков, и он все равно оценивал бы.

В частности, сказать (add1 '(a b c d)) все равно, что сказать «Сколько будет 1 плюс клубника?», а ваша функция больше похожа на:

«Сколько вещей в этом списке?»

«Ну, если ты ничего не видишь сверху ((first my-list)), то точно ничего нет».

"Хорошо, хорошо... Я вижу "а" сверху!"

"Хорошо! Убери это. Это как минимум 1 в списке."

"Хорошо, но сколько в остальных?"

«Как насчет того, чтобы попробовать то же самое еще раз? Просто продолжайте вынимать элементы из верхней части списка, пока список не станет пустым. Затем мы соберем его обратно и будем считать по мере продвижения».

«Хорошо, я вынул их все. Теперь я собираюсь вставить их обратно: d — это 1, c — это 2, b — это 3 и a — это 4!»

"Ну вот, 4 в списке!"

Если ваша проблема связана с рекурсией, я предлагаю вам trace повторяющиеся вызовы my-length. Например в DrRacket пропишите в окне определения следующее:

#lang racket

(require racket/trace)

(define (my-length a-list)
  (if (empty? a-list)
      0
      (add1(my-length (rest a-list)))))

(trace my-length)
(my-length '(a b c d))

Нажмите Run и наблюдайте:

>(my-length '(a b c d))
> (my-length '(b c d))
> >(my-length '(c d))
> > (my-length '(d))
> > >(my-length '())
< < <0
< < 1
< <2
< 3
<4
4

Вы можете видеть, что (my-length '(a b c d)) вызывает (my-length '(b c d)) (потому что это и есть (rest '(a b c d))), который вызывает (my-length '(c d)) и так далее. Когда вызывается (my-length '()), он возвращает 0 (первая ветвь if). Это возвращаемое значение передается (возвращается) предыдущему вызову, (my-length '(d)), который add1s ему, и, таким образом, возвращает 1. Это последнее возвращаемое значение возвращается (my-length '(c d)), который возвращает 2, и так далее до (my-length '(a b c d)), который, наконец, возвращает 4.

Важным моментом здесь является то, что add1 применяется к возвращаемому значению рекурсивного вызова и, следовательно, должен дождаться возврата этого вызова, прежде чем сможет что-то сделать с этим возвращаемым значением. Другими словами, add1 применяются в обратном порядке по сравнению с тем, как обрабатывается список.

Дополнительную информацию и Примеры.

add1 добавляет 1 к своему аргументу и возвращает эту сумму. Таким образом, если длина остатка списка равна 3, (add1 (my-length (rest a-list))) добавит 1 к 3 и вернет 4.

В базовом случае пустого списка my-length возвращает 0.

(my-length '(4)) вызывает (my-length '()) в рекурсии, которая возвращает 0, затем вызывает add1 для возврата 1.

(my-length '(3 4)) вызывает (my-length '(4)) в рекурсии. Как указано выше, это возвращает 1, затем вызывает add1 для этого, которое возвращает 2.

и так далее.

Оценка выглядит следующим образом:

   (my-list '(1 2 3 4))
-> (add1 (my-list '(2 3 4)))
-> (add1 (add1 (my-list '(3 4))))
-> (add1 (add1 (add1 (my-list '(4)))))
-> (add1 (add1 (add1 (add1 (my-list '())))))
-> (add1 (add1 (add1 (add1 0))))
-> (add1 (add1 (add1 1)))
-> (add1 (add1 2))
-> (add1 3)
-> 4