Depth-first Search Non-Reursive Implementation in Clojure I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve readability, make the code more idiomatic, or improve performance would be very helpful. I'm aware there is already question about a recursive dfs implementation in Clojure, but I feel like this code is different enough to warrant a separate post. 

(def graph {'a '(b c e) 'b '(a d f) 'c '(a g) 'd '(b) 'e '(a f) 'f '(b e)})

(defn label
  [v discovered]
  (cons v discovered))

(defn get-edges
  [g v]
  (get g v))

(defn labeled?
 [v discovered]
  (cond
    (some #(= v %) discovered) true
    :else false))

(defn build-stack
 [S edges]
  (concat S edges))


(defn dfs
  [g v]
   (loop
    [discovered '() S (cons v ())]
     (cond
      (empty? S) (reverse discovered)
      (labeled? (last S) discovered) (recur discovered (butlast S))
      :else 
       (recur
         (label (last S) discovered) 
         (build-stack (butlast S) (get-edges g (last S)))))))
From the top ... 


The label function is a synonym for cons, as is build-stack for
concat. Drop them.
The get-edges function doesn't get edges. It gets the neighbouring
vertices. Call it neighbours, or some such.


The labeled? function:


It determines whether the first argument is a member of the
collection second argument. So call it something generic like
includes?.
Swap the arguments around, so that it reads more naturally.
Get rid of the explicit falses and trues. You usually can. 


We end up with

(defn includes?
  [coll x]
  (some #(= x %) coll))


Now for the dfs function itself. 


Your local S is, as its name suggests, a stack. Use the other end
of it - the front of the list. This gets rid of the slow last and
butlast. You can't use Clojure's stack lingo - peek, pop, and
conj - because there's a concat in there. So use first, next,
and cons instead.
If you use a vector instead of a list to accumulate discovered, you
don't need the final reverse.
(cons v ()) is just (list v)


The result is

(defn dfs
  [g v]
  (loop [discovered [], S (list v)]
    (cond
      (empty? S) discovered
      (includes? discovered (first S)) (recur discovered (rest S))
      :else (recur
              (conj discovered (first S))
              (concat (neighbours g (first S)) (rest S))))))




There's still a performance problem. Whenever it deals with a potentially new vertex, it uses includes? to do a linear search of discovered. For a graph of n vertices, this takes of the order of n^2 time. 

The answer is to hold the discovered data twice:


as a vector, for returning the answer; and
as a set, for testing for presence.


This roughly doubles the amount of memory required, but reduces time required enormously (roughly to order of n). 

I'll leave you to make the necessary changes to dfs.