Fork me on GitHub
#clojure-norway
<
2022-06-26
>
Ivar Refsdal10:06:28

ahh... langt mindre nøsting for denne kodebklokka med letr:

Fredrik11:06:13

Kan unfold gi deg "tilstandsløs" bredde-først-søk? En ganske vanlig måte å gjøre bfs og dfs er å bruke henholdsvis en queue eller en stack til å holde orden på de neste nodene du vil besøke. Ved å bruke reduce kan man gjøre dfs tilstandløs, f.eks.

(defn dfs [xs]
  (letfn [(kids [x] (when (sequential? x) (seq x)))
          (dfs-combine [acc x]
            (if-let [k (kids x)]
              (reduce dfs-combine acc k)
              (conj acc x)))]
    (reduce dfs-combine [] xs)))

Fredrik11:06:12

Siden du kan skrive bfs/dfs tilstandsfullt slike at eneste forskjellen er queue/stack,

(defn search [stattholder xs]
  (loop [to-visit (conj stattholder xs)
         res []]
    (if-let [x (peek to-visit)]
      (if-let [x-seq (and (sequential? x) (seq x))]
        (recur (into (pop to-visit) x-seq) res)
        (recur (pop to-visit) (conj res x)))
      res)))

(search clojure.lang.PersistentQueue/EMPTY '(1 (2 ((3) 4)) 10 12))
(search () '(1 (2 ((3) 4)) 10 12))
så kanskje kan man til og med kan skrive skjelettet til et tilstandsløst søk slik at unfold gir bfs, mens reduce gir dfs

Fredrik11:06:33

Har ikke klart å få det helt til enda, men det klarer kanskje noen andre? 🙂 Altså: Lag en funksjon (defn search [f xs] ...) slik at dfs = (partial search reduce) og bfs = (partial search unfold).

(defn unfold
  ([next seed] (unfold cons next seed))
  ([cf next seed]
   (lazy-seq
    (when-let [[val new-seed] (next seed)]
      (cf val (unfold cf next new-seed))))))

(defn bfs [xs]
  (letfn [(atoms [x] (when-not (sequential? x) x))
          (kids [x] (when (sequential? x) x))
          (bfs-next [x] (when (seq x)
                          [(keep atoms x) (mapcat kids x)]))]
    (unfold concat bfs-next xs)))

(bfs '(1 (2 ((3) 4)) 10 12))
;; => (1 10 12 2 4 3)