Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 depth nested structure.md

Last active Mar 26, 2020

Depth of a nested structure

Clojure code often deals with deeply nested collections. Your task is to write a function that finds the maximum depth of any given value.

Examples:

```(depth 0) ;=> 0
(depth []) ;=> 1
(depth [  [1 ]]) ;=> 3```

Don't forget the collections include lists, vectors, maps, and sets.

 (ns tst.demo.core (:use tupelo.core tupelo.test )) (defn depth [arg] (let [max-depth (atom 0)] (walk-with-parents-readonly arg {:enter (fn [parents -item-] (swap! max-depth max (count parents)))}) @max-depth)) (dotest (is= 0 (depth 0)) (is= 0 (depth [])) (is= 2 (depth [  3])) (is= 3 (depth [  [1 ]])) (is= 4 (depth '(1 (2 3 (4 5 6 (7 8 9 10)))))) (is= 3 (depth #{1 #{2 3 #{4}}})) (is= 2 (depth {:foo {:bar 1}})) (is= 5 (depth {:a [1 2 '(3 4 #{5 {:z "baz"}})]})) )
 (defn depth ([x] ;; Kickstart with an accumulator (depth [x] 0)) ([xs d] ;; Check if there are collections left (let [colls (filter coll? xs)] (if (empty? colls) ;; No collections left, thus deepest collection was found. d ;; Tail-call to avoid stack overflows and memory hogging. (recur ;; Concatenate all found collections together, handling maps a ;; tad special, as it may have collections as well, both in ;; its keys and values. (mapcat (fn [coll] (if (map? coll) (concat (keys coll) (vals coll)) coll)) colls) ;; Increase depth by 1 (inc d))))))
 (defn depth [v] (cond (map? v) (recur (concat (keys v) (vals v))) (coll? v) (inc (reduce max 0 (map depth v))) :else 0)) (defn depth2 ;; where empty collections are depth 0 [v] (cond (map? v) (recur (concat (keys v) (vals v))) (coll? v) (inc (reduce max -1 (map depth v))) :else 0))
 (ns depth (:require [clojure.test :refer :all])) (defn- coll->seq [coll] (cond (map? coll) (first (seq coll)) :else (seq coll))) (defn- expr->depths "Translates an expression to a collection of depth values. Scalar values are wrapped in a collection so that the result can be treated as a sequence." [sexp depth] (if (coll? sexp) (if-let [seq (coll->seq sexp)] (flatten (map #(expr->depths % (inc depth)) seq)) [(inc depth)]) [depth])) (defn depth [expr] (apply max (expr->depths expr 0))) ;TESTS (deftest max-depth-test (is (= 0 (depth 0))) (is (= 1 (depth []))) (is (= 2 (depth [  3]))) (is (= 3 (depth [  [1 ]]))) (is (= 4 (depth '(1 (2 3 (4 5 6 (7 8 9 10 ))))))) (is (= 3 (depth #{1 #{2 3 #{4}}}))) (is (= 2 (depth {:foo {:bar 1}}))) (is (= 5 (depth {:a [1 2 '(3 4 #{5 {:z "baz"}})]}))))
 (ns jvw.depth (:require [clojure.test :refer [deftest testing is]])) (defn depth "Returns the maximum depth of `x`. The depth of a non-collection value is 0. Maps are not regarded as a collection of key-value collections (which would result in any non-empty map having a depth of at least 2). Instead, the maximum depth of a map is calculated by using the maximum depth of each key and each value." [x] (loop [max-depth 0 to-process (list [0 x])] (if (empty? to-process) max-depth (let [[depth x] (peek to-process) next-depth (inc depth)] (if (coll? x) (let [xs (if (map? x) (concat (keys x) (vals x)) x)] (recur (max max-depth next-depth) (-> (pop to-process) (into (map (fn [x] [next-depth x]) xs))))) (recur max-depth (pop to-process))))))) ;; Tests (deftest depth-test (testing "non-collection" (is (= 0 (depth 0))) (is (= 0 (depth nil))) (is (= 0 (depth "string")))) (testing "unnested collection" (is (= 1 (depth '(1 2)))) (is (= 1 (depth []))) (is (= 1 (depth {:a :b}))) (is (= 1 (depth #{\a \b}))) (is (= 1 (depth (seq "string"))))) (testing "nested collection" (is (= 2 (depth [1 ]))) (is (= 2 (depth {:a }))) (is (= 2 (depth {[:a] 1}))) (is (= 2 (depth {[:a] }))) (is (= 2 (depth {{} }))) (is (= 3 (depth {{[] 1} }))) (is (= 3 (depth [  [1 ]])))))
 (defn flatten-one [coll] (mapcat #(if (sequential? %) % [%]) coll)) ;; count the single-level flattenings needed to reach a fixed point ;; works on vectors and lists, not sets and maps (defn _depth [c] (if (not (sequential? c)) 0 (loop [ct 1 fc c] (let [nl (flatten-one fc)] (if (= nl fc) ct (recur (inc ct) nl)))))) ;; this gross hack smashes sets and maps into vectors of the same nesting depth (defn txmanip-coll [c] (-> (str c) (clojure.string/replace \# \space) (clojure.string/replace \{ \[) (clojure.string/replace \} \]) read-string)) (defn depth [c] (_depth (txmanip-coll c)))
 (defn depth ([val] (depth val 0)) ([val d] (if (coll? val) (reduce (fn [r x] (max r (depth x (inc d)))) (inc d) val) d)))
 (ns purelyfunctional-newsletters.issue-369 (:require [clojure.test :refer :all])) (defn depth [coll] (cond (or (vector? coll) (seq? coll) (set? coll)) (+ 1 (apply max 0 (map depth coll))) (map? coll) (+ 1 (apply max 0 (concat (map depth (keys coll)) (map depth (vals coll))))) :else 0)) (deftest depth-tests (is (= 0 (depth 0))) (is (= 1 (depth []))) (is (= 2 (depth [ [] ]))) (is (= 3 (depth [  [1 ]]))) (is (= 1 (depth (list)))) (is (= 2 (depth (list (list)) ))) (is (= 3 (depth (list (list 0) (list 2) (list 1 (list 2)))))) (is (= 1 (depth #{}))) (is (= 2 (depth #{ #{} }))) (is (= 3 (depth #{#{0} #{2} #{1 #{2}}}))) (is (= 1 (depth {}))) (is (= 2 (depth {:a {}}))) (is (= 4 (depth {:a {:a 0 :b {:a 2} :c {:a 1 :b {:a 2}}}}))) (is (= 5 (depth #{ {:a [1 (list 2 3 )]}}))))

### miner commented Mar 20, 2020 • edited

 Steve Miner solution missed special case for maps. Here's a revision: ``````(defn depth ([val] (depth val 0)) ([val d] (if (coll? val) (let [d2 (if (map? val) d (inc d))] (reduce (fn [r x] (max r (depth x d2))) (inc d) val)) d))) ``````
to join this conversation on GitHub. Already have an account? Sign in to comment