Блог

Мне нужна помощь, чтобы понять мой код теоретически. Вот моя программа на лиспе:

 (defun depth (lst)

  (if (or (null lst) (atom lst)) 0 

    (  1 (apply 'max (mapcar #'depth lst)))

  ))
 

Я знаю, что это работает с этим примером:

 (write (depth '((a (b c) d r ((t))))) -> 3
 

Я просто не могу понять утверждение » еще IF » в заявлении, которое я пробовал.

Если вы сможете мне помочь, я буду вам очень признателен. Заранее спасибо.

Вот ваш код, слегка переформатированный:

 (defun depth (value)
  (if (or (null value) (atom value))
      0
      (  1 (apply 'max (mapcar #'depth value)))))
 

Я переименовал lst (кстати , вы могли бы написать это list ) в value , потому что название сбивает с толку, поскольку предполагает, что переменная всегда является списком, что неверно. Функция depth может быть вызвана при любом значении:

 (depth "hello")
=> 0

(depth 100)
=> 0
 

Затем ветвь if вычисляется, когда value равно НУЛЮ или любому atom . Поскольку NIL также является atom , тестовое выражение может быть упрощено как (atom value) . Когда значение равно атому, глубина равна нулю.

Ветвь else if оценивается, когда value не является атомом, что по определению atom означает value здесь a cons . Функция также предполагает, что это правильный список, а не какой-то круговой список.

Поскольку value в этой ветви есть список, мы можем вызвать mapcar его: (mapcar #'depth value) ; здесь функция предполагает, что список является правильным. Это вычисляется (depth v) для каждого v входа value . Точнее, если value это список длины n, то этот вызов mapcar оценивается как список чисел (D1 ... Dn) , где Di (depth Vi) для всех i от 1 до n .

Итак, мы знаем, что (apply 'max (mapcar ...)) это (apply 'max depths) для некоторого списка depths номеров. В общем:

 (apply fn v1 ... vn list)
 

… является способом вызова объекта функции, обозначаемого fn выражением, по крайней мере n , с элементами ( v1 to vn ), а также произвольным количеством дополнительных элементов, хранящихся в list . Когда вы цитируете функцию, как 'max или когда вы пишете #'max , вы ссылаетесь на функцию по ее имени в пространстве имен функций.

Сравните это с обычным способом вызова функции:

 (f x y z)
 

Имя функции и количество передаваемых аргументов фиксированы: как только форма прочитана, мы знаем, что есть вызов f с 3 аргументами.

apply Функция является встроенной, которая позволяет передавать дополнительные аргументы в списке в последнем аргументе вызова. Вышеуказанный вызов может быть написан:

 (apply #'f x y z ()) ;; note the empty list as a last argument
 

Это также можно было бы написать:

 (apply #'f (list x y z)) ;; all arguments in the last list
 

Единственное различие, вероятно, заключается в эффективности выполнения (а с хорошими компиляторами, возможно, разницы нет).

В вашем примере вы делаете:

 (apply max depths)
 

Что было бы то же самое, что писать (псевдокод):

 (max d1 d2 d3 ... dn)
 

… где depths находится список (list d1 d2 ... dn) .
Но мы не можем буквально записать их все напрямую, так как содержимое списка известно только во время выполнения.

Таким образом, вызов apply вычисляет максимальную глубину среди всех глубин, вычисленных рекурсивно. Обратите внимание , что вышеизложенное является несколько неправильным использованием apply , так apply как не следует вызывать списки произвольного размера: в названном стандарте есть ограничение CALL-ARGUMENTS-LIMIT , теоретически допустимое до 50, максимальный размер такого списка (мы увидим альтернативу ниже).

Наконец, depth оценивает ( 1 ...) этот результат. Другими словами, все выражение можно резюмировать следующим образом: глубина списка равна 1, добавленной к максимальной глубине всех его элементов.

С помощью reduce

Вместо apply этого вы можете использовать REDUCE для max последовательных вычислений по списку. Это предпочтительнее apply , чем потому, что:

• нет никаких ограничений на количество элементов, таких как apply

   (reduce 'max depths) ;; works the same, but more reliably
   

• нет необходимости создавать промежуточный список глубин, вы перебираете список значений, вызываете depth и напрямую используете результат для вычисления максимума. Скелет-это:

   (reduce (lambda (max-so-far item) ...)
          value
          :initial-value 0)
   

Декларативный подход

Вместо reduce loop этого макрос можно использовать в качестве более удобочитаемой альтернативы для выражения тех же вычислений. Я также использую typecase то, что, на мой взгляд, делает намерение более ясным:

 (defun depth (value)
  (typecase value
    (atom 0)
    (cons (1  (loop for v in value maximize (depth v))))))