Получение самого вложенного списка в Clojure

Question

Я переношу некоторые функции LISP в Clojure. У меня есть проблемы с StackOverflow сообщение для следующих функций:

(defn m 
    [list depth] 
    (cond 
     (= list nil) depth 
     (atom (first list)) (m (rest list) depth) 
     (> (m (first list) (+ depth 1)) (m (rest list) depth)) (m (first list) (+ depth 1)) 
     :default (m (rest list) depth)) 
    ) 

(defn n 
    [list depth maxdepth] 
    (cond 
     (= list nil) nil 
     (= depth maxdepth) list 
     (atom (first list)) (n (rest list) depth maxdepth) 
     (= 0 (n (first list) (+ depth 1) maxdepth)) (n (last list) depth maxdepth) 
     :default (n (first list) (+ depth 1) maxdepth)) 
    ) 

(defn myfind[mylist] 
    (n mylist 0 (m mylist 0)) 
) 

То, что я в принципе хочу это выход наиболее вложенного списка, например:

(myfind '(1 2 3 (4 5) 6 ((7 8) 9))) 
=> (7 8) 

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

Что не так в этом случае?

Answer 1

(defn- deepest-with-depth [depth s] 
    (let [nested-colls (filter coll? s)] 
    (if (seq nested-colls) 
     (mapcat (partial deepest-with-depth (inc depth)) nested-colls) 
     [[depth s]]))) 

(defn deepest [s] 
    (->> (deepest-with-depth 0 s) 
     (apply max-key first) 
     second)) 

> (deepest '(1 2 3 (4 5) 6 ((7 8) 9))) 
(7 8) 

Смело subsitute некоторые вызовы функций (например max-key, partial) их реализации, если они вступают в противоречие с вашими требованиями.

Answer 2

(defn- max-depth-entry [a-list] 
    (let [sub-lists (filter coll? a-list) 
     [depth list] (if (empty? sub-lists) 
          [0 a-list] 
          (apply max-key first (map max-depth-entry sub-lists)))] 
    [(inc depth) list])) 

(max-depth-entry '(1 2 3 (4 5) 6 ((7 8) 9))) 
;[3 (7 8)] 

Тогда

(def max-depth-sublist (comp second max-depth-entry)) 

(max-depth-sublist '(1 2 3 (4 5) 6 ((7 8) 9))) 
;(7 8) 

---

я обязан идею использования max-key в OlegTheCat's answer. Я первоначально трикотажное самостоятельно, используя reduce:

(defn- max-depth-entry [a-list] 
    (let [sub-lists (filter coll? a-list) 
     [a-list a-depth] (reduce 
          (fn ([] [a-list 0]) 
          ([[as an :as asn] [s n :as sn]] (if (> n an) sn asn))) 
          (map max-depth-entry sub-lists))] 
    [a-list (inc a-depth)])) 

Тогда

(def max-depth-sublist (comp first max-depth-entry)) 

---

Теперь я готов вернуться к Sequs Horribilis on 4Clojure, который не загнаны в угол меня до сих пор.

Answer 3

вот еще один вариант, только с классическим старым раствором школы, и никаких конкретных функций последовательности Clojure на всех:

(defn deepest [items depth] 
    (if (sequential? items) 
    (let [[it1 d1 :as res1] (deepest (first items) (inc depth)) 
      [it2 d2 :as res2] (deepest (next items) depth)] 
     (cond (>= depth (max d1 d2)) [items depth] 
      (>= d1 d2) res1 
      :else res2)) 
    [items -1])) 

также примечательны это классический подход к рекурсии вложенных списков: сначала повторялись на car, затем на cdr, а затем объедините эти результаты.

user> (deepest '(1 2 3 (4 5) 6 ((7 8) 9)) 0) 
[(7 8) 2] 

user> (deepest '(1 2 3 (4 5) 6) 0) 
[(4 5) 1] 

user> (deepest '(1 2 3 (x ((y (z)))) (4 5) 6) 0) 
[(z) 4] 

user> (deepest '(1 2 3 (x ((y (z)))) (4 5 ((((((:xxx)))))))) 0) 
[(:xxx) 7] 

user> (deepest '(1 2 3 ((((((((nil)))))))) (x ((y (z)))) (4 5) 6) 0) 
[(nil) 8] 

user> (deepest '(1 2 3) 0) 
[(1 2 3) 0]