Обход/поиск структуры данных Clojure

Я хотел бы иметь возможность сделать что-то вроде этого:

(search data 
  list?
  (fn [x] (and (list? x) (= 4 (first x))))
  (fn [x] (and (set? x) (contains x 3))))

И заставьте его рекурсивно искать вложенную структуру данных data:

  1. сначала для самых мелких списков (например, может быть в наборе наборов).
  2. затем в этих списках для самых мелких списков, первый элемент которых равен 4.
  3. затем в тех списках для самых мелких наборов, которые содержат 3.
  4. наконец, возвращает список элементов, найденных на шаге 3.

Прежде чем я изобрету велосипед, есть ли стандартный способ сделать это?


search clojure data-structures traversal
person z5h    schedule 08.12.2009    source источник

Ответы (1)


arrow_upward
6
arrow_downward

В Clojure есть стандартные способы обхода деревьев. Вам следует заглянуть в clojure.zip, а также в tree-seq.

(loop [loc dz] 
  (if (end? loc) 
    (root loc) 
    (recur (next (if (= '* (node loc)) 
                   (replace loc '/) loc))))) 

(loop [loc dz] 
  (if (end? loc) 
    (root loc) 
    (recur (next (if (= '* (node loc)) 
                   (remove loc) loc)))))

Эти два примера в конце clojure.zip ясно показывают, что вам не нужно знать, как выглядит структура данных. Использование цикла также показывает, что вы можете легко накапливать только интересующие вас значения по мере прохождения структуры данных.

person dnolen    schedule 08.12.2009
comment
zip кажется полезным, если вы уже знаете свою структуру данных и где в более крупной структуре вам следует искать. tree-seq немного контрпродуктивен, поскольку он маскирует рассматриваемую структуру данных и делает ее видимой в виде последовательности, поэтому вы даже не будете знать, находитесь ли вы в списке списка или в наборе набора. Я дал вам +1, так как они могут быть полезны при создании функции, которую я ищу. - person z5h; 08.12.2009
comment
Например, я мог бы настроить дочернюю функцию tree-seq для внедрения тегов, которые сообщают мне, когда я перемещаюсь в подструктуру или из нее. Затем потребляющая функция поиска может отслеживать глубину и то, где она находится в более крупной структуре. - person z5h; 08.12.2009