Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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 [[0] [2] [1 [2]]]) ;=> 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 [[1] [2] 3]))
(is= 3 (depth [[1] [2] [1 [2]]]))
(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 [[1] [2] 3])))
(is (= 3 (depth [[1] [2] [1 [2]]])))
(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 [2]])))
(is (= 2 (depth {:a [1]})))
(is (= 2 (depth {[:a] 1})))
(is (= 2 (depth {[:a] [1]})))
(is (= 2 (depth {{} [1]})))
(is (= 3 (depth {{[] 1} [1]})))
(is (= 3 (depth [[0] [2] [1 [2]]])))))
(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 [[0] [2] [1 [2]]])))
(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 #{[0]
{:a [1
(list 2
3
[4])]}}))))
@miner

This comment has been minimized.

Copy link

miner commented Mar 20, 2020

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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.