Example code for the problem of removing items from lazy sequences nested in a large Clojure tree and related issues. See http://stackoverflow.com/questions/32667778/removing-elements-from-lazy-sequences-in-a-large-clojure-tree-structure-avoidin for details

core.clj

(ns large-tree.core
  "Working example, also using XML."
  (require [clojure.data.xml :as xml]))

(defn root' [content]
  (fn []
    (xml/map->Element {:tag :root :content (content)})))

(defn lazy-elements' [n tag content]
  (repeatedly n (fn [] (xml/map->Element {:tag tag :content (content)}))))

(defn level-1' [content]
  (fn []
    (lazy-elements' 3 :A content)))

(defn level-2' [n]
  (fn []
    (concat (lazy-elements' 10 :X (fn [] '(:leaf)))
            (lazy-elements' n :Y (fn [] (lazy-elements' (* 1000 n) :Y (fn [] '(:leaf)
                                                                        )))))))

(defn remove-nodes [node]
  (remove #(= (:tag %) :Y) node))

(defn run [size]
  (let [root-builder (root' (level-1' (level-2' size)))
        update-contents (fn [f node] (update-in node [:content] f))]
    (-> (root-builder)
        (update-in [:content] #(map (partial update-contents remove-nodes) %)))))

lazily_remove_from_large_tree.clj

  ;; Generating example data
  ;;;;;;;;;;;;;;;;;;;;;;;;;;

  (defn root [content]
    {:tag :root :content content})

  (defn lazy-elements [n tag content]
    (lazy-seq (repeat n {:tag tag :content content})))

  (defn level-1 [content]
    (lazy-elements 3 :A content))

  (defn level-2 [n]
    (concat (lazy-elements 10 :X '(:leaf))
            (lazy-elements n :Y '(:leaf))))

  (defn remove-nodes [node]
    (remove #(= (:tag %) :Y) node))


  ;; Illustrating usage
  ;;;;;;;;;;;;;;;;;;;;;

  ;; runs and runs and runs... and eventually returns correctly
  (defn valid-run []
    (->> (root (level-1 (level-2 1e8)))
         :content
         first
         :content
         remove-nodes))

  ;; Does not terminate properly, runs out of memory
  (defn invalid-run []
    (->> (root (level-1 (level-2 1e8)))
         :content
         (map :content)       ; source of head retention
         (map remove-nodes)))