Compress clojure data structure -- find common subtrees and move them into a lookup table.

tree.clj

(ns trees
  (:require [clojure.walk :as walk]))

(defonce id (atom 0))

(defrecord Ref [id])

(defn new-id! []
  (->Ref (swap! id inc)))

(defmethod print-method Ref [this ^java.io.Writer w]
  (.write w "#ref")
  (.write w " ")
  (print-method (:id this) w))

(defn hydrate
  [{:keys [tree lookup]}]
  (walk/prewalk-replace lookup tree))

(defn dehydrate
  [tree]
  (let [nodes  (tree-seq coll?
                         #(if (map? %) (vals %) (seq %))
                         tree)
        lookup (into {}
                     (->> nodes
                          frequencies
                          (remove #(<= (second %) 1))
                          #_ (remove #(<= (count (with-out-str (prn %)))
                                          100))
                          (map #(vector (first %) (new-id!)))))]

    {:tree   (walk/prewalk-replace lookup tree)
     :lookup (into {} (map (comp vec reverse) lookup))}))

#_ (prn (dehydrate {:a {:b 2} :x [{:b 2}]}))
#_ (prn (hydrate (dehydrate {:a {:b 2} :x [{:b 2}]})))