Skip to content

Instantly share code, notes, and snippets.

@nblumoe

nblumoe/core.clj

Last active September 21, 2015 18:44
Show Gist options
  • Save nblumoe/227e64483a5033c55e14 to your computer and use it in GitHub Desktop.
Save nblumoe/227e64483a5033c55e14 to your computer and use it in GitHub Desktop.
Download ZIP
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
Raw
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) %)))))
Raw
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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment