Блог

В настоящее время я пытаюсь изучить Clojure. Но у меня возникли проблемы с созданием функции, которая рекурсивно выполняет поиск по каждому элементу списка и возвращает количество элементов «a», присутствующих в списке.

Я уже выяснил, как выполнять это итеративно, но у меня возникают проблемы с рекурсивным выполнением. Я пытался изменить «seq» на «пустой»? но это тоже не сработало.

 (defn recursive-a [amp; lst]
 (if (seq lst)
     (if (= (first lst) "a")
         (  1 (recursive-a (pop (lst))))
         (  0 (recursive-a (pop (lst)))))
     0))
  

Добро пожаловать в сообщество stack overflow.

Ваш код в порядке, за исключением того, что вы допустили несколько незначительных ошибок.

Во-первых, есть одна дополнительная пара фигурных скобок вокруг вашего lst параметра, который вы пересылаете рекурсивной функции. В языках LISP фигурные скобки означают вычисление функции. Итак, сначала вы должны удалить их.

Вторая вещь — это amp; синтаксический сахар параметра. Вы не хотите использовать это, пока не будете уверены, как это влияет на ваш код.

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

   (defn recursive-a [lst]
 (if (seq lst)
     (if (= (first lst) "a")
         (  1 (recursive-a (pop lst)))
         (  0 (recursive-a (pop lst))))
     0))


(recursive-a (list "a" "b" "c"))
  

Вы можете запустить его в веб-среде:https://repl.it/languages/clojure

Добро пожаловать в Stack Overflow.

При recursive-a явном вызове исходная реализация потребляет стек при каждой рекурсии. Если в качестве входных данных предоставлен достаточно большой список, эта функция в конечном итоге исчерпает стек и произойдет сбой. Есть несколько способов обойти это.

Один из классических методов Lisp-y для обработки ситуаций, подобных этой, заключается в предоставлении второй реализации функции, которая передает счетчик выполнения в качестве входного аргумента «внутренней» функции:

 (defn recursive-a-inner [cnt lst]
  (cond
    (seq lst) (cond
                (= (first lst) "a") (recur (inc cnt) (rest lst))
                :else               (recur cnt (rest lst)))
    :else cnt))

(defn recursive-a [amp; lst]
  (recursive-a-inner 0 lst))
  

Делая это, «внутренняя» версия позволяет перевести рекурсию в конечное положение, чтобы можно было использовать recur ключевое слово Clojure. Это не совсем такая чистая реализация, как оригинал, но у нее есть то преимущество, что она не будет взрывать стек.

Другой способ справиться с этим — использовать loop -ing от Clojure, который допускает рекурсию внутри тела функции. Результат почти такой же, как у «внутренней» функции выше:

 (defn recursive-a [amp; lp]
  (loop [cnt  0
         lst  lp]
    (cond
      (seq lst) (cond
                  (= (first lst) "a") (recur (inc cnt) (rest lst))
                  :else               (recur cnt (rest lst)))
      :else cnt)))
  

И если мы откажемся от требования явной рекурсии, мы можем сделать это немного проще:

 (defn not-recursive-a [amp; lst]
  (apply   (map #(if (= % "a") 1 0) lst)))
  

Желаю удачи.

В духе обучения:

Вы можете использовать amp; или нет. Оба в порядке. Разница в том, как вы затем будете вызывать свою функцию, и вам придется не забывать использовать apply при повторении.

Кроме того, просто используйте first и rest . Они оба безопасны и будут работать как с нулевым, так и с пустым списками, возвращая nil и пустой список соответственно:

 (first [])  ;; -> nil
(first nil) ;; -> nil
(rest [])   ;; -> ()
(rest nil)  ;; -> ()
  

Итак, вот как я бы переработал вашу идею:

 ;; With 'amp;'
(defn count-a [amp; lst]
  (if-let [a (first lst)]
    (  (if (= a "a") 1 0)
       (apply count-a (rest lst)))  ;; use 'apply' here
    0))
;; call with variable args, *not* a list
(count-a "a" "b" "a" "c") 

;; Without 'amp;'
(defn count-a [lst]
  (if-let [a (first lst)]
    (  (if (= a "a") 1 0)
       (count-a (rest lst)))
    0))
;; call with a single arg: a vector (could be a list or other )
(count-a ["a" "b" "a" "c"])  
  

Однако это небезопасно, потому что они не используют хвостовую рекурсию, и поэтому, если ваш список большой, вы взорвете свой стек!

Итак, мы используем recur . Но если вы не хотите определять дополнительную «вспомогательную» функцию, вы можете вместо этого использовать loop в качестве целевого объекта «recur»:

 ;; With 'amp;'
(defn count-a [amp; lst]
  (loop [c 0  lst lst] ;; 'recur' will loop back to this point
    (if-let [a (first lst)]
      (recur (if (= a "a") (inc c) c) (rest lst))
      c)))
(count-a "a" "b" "a" "c")

;; Without 'amp;'
(defn count-a [lst]
  (loop [c 0  lst lst]
    (if-let [a (first lst)]
      (recur (if (= a "a") (inc c) c) (rest lst))
      c)))
(count-a ["a" "b" "a" "c"])

  

При всем сказанном, это тот, который я бы тоже использовал:

 ;; With 'amp;'
(defn count-a [amp; lst]
  (count (filter #(= % "a") lst)))
(count-a "a" "b" "a" "c")

;; Without 'amp;'
(defn count-a [lst]
  (count (filter #(= % "a") lst)))
(count-a ["a" "b" "a" "c"])