Clojure depth first search maze problem from Classic CS Problems in Python Book

Question

I am an experienced self-taught professional Python programmer working my way through the book Classic Computer Science Problems in Python to try to catch myself up on some of the things I missed by not going to school for this. I am also currently trying to learn Clojure, and I thought why not kill two birds with one stone by using this book to practice writing Clojure as well. So, I'm using Python as a reference in order to port solutions to Clojure. I have never professionally written code with a lisp or functional programming language. I am new to the Clojure and JVM ecosystems. For all these reasons I feel I would greatly benefit from submitting my early Clojure code up for peer review from more experienced Clojure developers.

What I'm primarily looking to get out of this review:

• Call me out where I'm doing something Pythonic but not Lispy/Functional.
• Point me in the direction of useful Clojure core functions that I may just not know about.
• Guide me to use common Clojure developer conventions. How should I write doc comments? How should I name my variables?
• Tell me when something I've done just looks weird to an experienced Clojure developer.
• I'd really be interested in a lazy solution to my dfs algorithm that could produce all the possible solutions rather than just the first solution.

Okay here's the code.

generic_search.clj

(ns cs-clj.ch2.generic-search)
(defn dfs
 [start is-goal? get-successors]
 (loop [frontier (list [start, []])
 explored #{start}]
 (let [[cur-loc cur-path] (peek frontier)
 next-path (conj cur-path cur-loc)]
 (cond
 (empty? frontier) nil
 (is-goal? cur-loc) next-path
 :else (let [successors (remove explored (get-successors cur-loc))
 new-frontier (map (fn [loc] [loc next-path]) successors)
 next-frontier (apply conj (pop frontier) new-frontier)
 next-explored (apply conj explored successors)]
 (recur next-frontier next-explored))))))

maze.clj

(ns cs-clj.ch2.maze
 (:require [clojure.string :as string]
 [cs-clj.ch2.generic-search :refer [dfs]]))
;; TODO: Seems like a fine way to represent an Enum, but...is there a better way?
(def cells {:empty " "
 :blocked "X"
 :start "S"
 :goal "G"
 :path "*"})
(defn random-cell-value
 [sparsity]
 (if (< (rand) sparsity)
 (:blocked cells)
 (:empty cells)))
(defn create-2d-grid
 [x y val-fn]
 ;; TODO: Is this idiomatic clojure? I'm trying to express a way to take either a
 ;; function or a value, and if it's a value wrap it in a function? Am I missing
 ;; the use of `identity` here in some way? Or perhaps an opportunity to use spec?
 ;; If spec, how?
 (let [val-fn (if (fn? val-fn) val-fn (fn [] val-fn))]
 ;; TODO: Wanted to represent grid as vectors, hence the `mapv`. With my use
 ;; of `assoc-in` to set values in the grid later I'm not certain it would have
 ;; worked with normal `map` returning sequences.
 (mapv (fn [_]
 (mapv (fn [_] (val-fn)) (range x)))
 (range y))))
(defn mark-grid-with
 [grid coord-vals]
 (reduce (fn [res-grid [coord val]]
 (assoc-in res-grid coord val))
 grid
 coord-vals))
;; TODO: use spec to validate that the start/goal are inbounds of rows and cols
;; TODO: think about whether maze "objects" could be a record.
;; TODO: Is there a good Protocol opportunity here?
;; mark-path, is-in-bounds?, is-blocked?, display-maze, get-successors, and mark-path
(defn create-maze
 "Creates randomly generated maze map."
 [& {:keys [rows cols sparsity start provided-goal]
 :or {rows 10
 cols 10
 sparsity 0.2
 start {:row 0 :col 0}
 provided-goal nil}}]
 (let [goal (if (nil? provided-goal)
 {:row (dec rows) :col (dec cols)}
 provided-goal)
 val-fn (partial random-cell-value sparsity)
 rand-grid (create-2d-grid rows cols val-fn)
 grid (mark-grid-with rand-grid [[[(:row start) (:col start)] (:start cells)]
 [[(:row goal) (:col goal)] (:goal cells)]])]
 {:rows rows
 :start start
 :goal goal
 :cols cols
 :grid grid}))
(defn is-in-bounds?
 "Checks if a location is inside the bounds of the maze."
 [maze loc]
 (let [{:keys [rows cols]} maze
 {:keys [row col]} loc]
 (and (<= 0 row)
 (< row rows)
 (<= 0 col)
 (< col cols))))
;; TODO Is it okay to use `backticks` in comments and doc strings to refer to
;; code vars and such? Is there a clojure docstrings and comments standard I should
;; know about? Like what if I wanted to autogen some API docs to a static site? Is
;; there a standard or at least popular tool like python's sphinx and restructured text?
(defn is-blocked?
 "Is the location at `loc` occupied in the `maze` by a wall character?"
 [maze loc]
 (let [grid (:grid maze)
 {:keys [row col]} loc
 cell-value (get-in grid [row col])]
 (= cell-value (:blocked cells))))
;; TODO: How do I get a doc comment on this function?
(def is-open? (complement is-blocked?))
(defn display-maze
 "Formats the maze grid to a legible string value."
 [{:keys [grid]}]
 (->> grid
 ;; TODO: Use (map #(string/join "" %)) here or is that too terse?
 ;; I feel like maybe the var name "row" helps clarity slightly.
 (map (fn [row] (string/join "" row)))
 (string/join "\n")))
(defn get-successors
 "Gets sequence of valid moves from the given location in the maze."
 [maze loc]
 (let [{:keys [rows cols]} maze
 {:keys [row col]} loc
 candidates [{:row (inc row) :col col}
 {:row (dec row) :col col}
 {:row row :col (inc col)}
 {:row row :col (dec col)}]]
 (->> candidates
 (filter (partial is-in-bounds? maze))
 (filter (partial is-open? maze)))))
(defn mark-path
 "Mark the path through the maze with * characters. Returns altered maze."
 [maze path]
 ;; TODO: Is this call to subvec an idiomatic clojure way to slice a vector?
 ;; I'm trying to do here what I would do in python as `path_locs = path[1:-1]`
 (let [path-locs (subvec path 1 (dec (count path)))
 cell-val (:path cells)
 coord-vals (map (fn [{x :row y :col}]
 [[x y] cell-val])
 path-locs)]
 (assoc maze
 :grid (mark-grid-with (:grid maze) coord-vals))))
(defn -main []
 (let [maze (create-maze)
 is-goal? (partial = (:goal maze))
 get-suc (partial get-successors maze)
 path (dfs (:start maze) is-goal? get-suc)]
 (if (nil? path)
 (do
 (println (display-maze maze))
 (println "Could not solve."))
 (println (display-maze (mark-path maze path))))))

Produces output like this when run:

S******X
 X ****
 X *
X*********
** X X
* XXX XX
****X X
 *X X
 *******
 X G

Also, here is the python maze.py

Answer 1

Initial comments for only the dfs function:

Variable names

• start makes sense for the initial point.
• is-goal? is- is not necessary, the question marks already indicates that it's a predicate function, so name it goal?.
• get-successors is a pure function that will return the same answer given the same point, pure functions don't need a verb. Verbs are to indicate side effects. successors is fine.

For later two points I followed Stuart Sierra's How to Name Clojure Functions.

I would skip the intermediate variables names like new-frontier and next-frontier since I think they are more confusing than just chaining the function calls in a thread-last, it is implied in a recur that they will be the next. And in same fashion I think the cur- prefix is redundant since it is clear they belong to the current round in the recursion.

Data representation

I noticed points are represented as {:row x, :col y}, I would see if you can use [x y] and refactor to a map or even priority-map with points as keys and values the paths (you could then sort by for example shorter length of path being higher priority).

Also (bit outside dfs) I would try to skip the cells map and only use it for printing because the conversions (e.g., cell-val (:path cells)) clutter up the code. I would use the :empty, :blocked and so on directly.

The use of the set as a function to find the new successors in (remove explored (get-successors cur-loc)) is idiomatic.

nil-punning instead of empty? check

nil-punning is the use of (when (seq coll) ..) instead of (if (empty? coll) nil ..). When calling seq on an empty coll it will return nil, and nil is falsy, and the falsy clause of when is nil. So that leads to the same behaviour as returning nil when the coll is empty.

Destructuring an empty value like you do in [cur-loc cur-path] (peek frontier) will also lead to two nils for cur-loc and cur-path and an nil for the overall vector, so you could achieve nil-punning using (when-let [[cur-loc cur-path] (peek frontier)] ..), now if the frontier is empty you will return the false clause and thus nil.

New code with the above points addressed

(defn dfs
 [start goal? successors]
 (loop [frontier (list [start, []])
 explored #{start}]
 (when-let [[loc path] (peek frontier)]
 (let [next-path (conj path loc)]
 (if (goal? loc)
 next-path
 (recur (->> (successors loc)
 (remove explored)
 (map (fn [l] [l next-path]))
 (apply conj (pop frontier)))
 (apply conj explored (successors loc))))))))

Final remarks

Overall, if I spend more time on this I would start looking at the representation of the maze and how to walk over it with bfs. I'd try to find a shorter representation of the point and also the maze, starting with trying to encode a point as [x y]. Then the associative destructuring later on can be changed to sequential (e.g., (let [[x y]] loc] ...) instead of (let [{:keys [row col]} loc] ...)) and I think the code will become more concise and readable.

Hope this helps!

PS For the nested mapv I would try to use a for comprehension. Note:

(mapcat (fn [x]
 (mapv (fn [y] [x y]) (range 4 6)))
 (range 3))
;; => ([0 4] [0 5] [1 4] [1 5] [2 4] [2 5])
(for [x (range 3)
 y (range 4 6)]
 [x y])
;; => ([0 4] [0 5] [1 4] [1 5] [2 4] [2 5])

• user5293: Thank you so much for your thoughtful response! This is incredibly helpful to me and I greatly appreciate you taking the time to look through this. Soon I'm going to have a go at incorporating your suggestions.
• user5293: Thanks again! I got around to applying yours and others feedback. Here is a diff of them. gitlab.com/willvaughn/classic-cs/-/merge_requests/1
• Thumbnail: A couple of tweaks : 1. You evaluate (successors loc) twice. Extract it to a let binding. 2. Replace the two instances of (reduce conj ...) with (into ...).