369 - PurelyFunctional.tv Newsletter - https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-369-refactoring-replace-body-with-callback/

00 depth nested structure.md

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.

Alan Thompson.clj

(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"}})]})) )

Arnout Roemers.clj

(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))))))

Eric Normand.clj

(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))

Eric.clj

(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"}})]}))))

Jeroen van Wijgerden.clj

(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]]])))))

Mark Champine.clj

(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)))

Steve Miner.clj

(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)))

Viktor P.clj

(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])]}}))))

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)))