Selecting HTML nodes
First things first: any time you find yourself using letfn, you should strongly consider simply breaking those functions out into their own defns. In this case, node-matches is large enough and decoupled enough to make that clearly the right choice.

One way you can make your code more concise is to take advantage of the fact that you can do destructuring directly in function arguments:

(defn node-matches [[tag attrs] [node-tag node-attrs]]
  (and (= node-tag tag)
       (every? (fn [[key val]]
                 (= (key node-attrs) val))
               (seq attrs))))


If you want to make clear what it is that you're destructuring, you could add :as prototype and :as node to your parameters.

When you think about it, though, that every? expression is really just trying to determine if attrs is a subset of node-attrs. In Clojure, you can use the subset? function to do that. So, assuming that you've already required [clojure.set :as set]:

(set/subset? (set attrs) (set node-attrs))


A lot of the complexity in the rest of find-nodes comes from the fact that you're complecting the logic that traverses the HTML tree and the logic that uses node-matches to do the matching and assemble the final result.

The best way to improve find-nodes, then, is to break it apart. Actually, traversing a Hiccup-style HTML tree is incredibly easy in Clojure using the tree-seq function:

(tree-seq vector? tagsoup/children (tagsoup/parse "test.html"))


This will give you a sequence of all the nodes in the HTML tree:

([:html {}
  [:head {}
   [:title {} "This is a test page"]]
  [:body {}
   [:div {:id "something-important"}
    [:p {:class "alert"}
     "\n        ...\n      "]]
   [:div {:id "something-else"}
    [:p {:class "message"}
     "\n        Hello World.\n      "]]]]
 [:head {}
  [:title {} "This is a test page"]]
 [:title {} "This is a test page"]
 "This is a test page"
 [:body {}
  [:div {:id "something-important"}
   [:p {:class "alert"}
    "\n        ...\n      "]]
  [:div {:id "something-else"}
   [:p {:class "message"}
    "\n        Hello World.\n      "]]]
 [:div {:id "something-important"}
  [:p {:class "alert"}
   "\n        ...\n      "]]
 [:p {:class "alert"}
  "\n        ...\n      "]
 "\n        ...\n      "
 [:div {:id "something-else"}
  [:p {:class "message"}
   "\n        Hello World.\n      "]]
 [:p {:class "message"}
  "\n        Hello World.\n      "]
 "\n        Hello World.\n      ")


And at this point, you're pretty much done. You just need to filter this sequence using the shortened version of node-matches that we wrote above:

(defn find-nodes [[tag attrs] root]
  (filter (fn [[node-tag node-attrs]]
            (and (= tag node-tag) (set/subset? (set attrs) (set node-attrs))))
          (tree-seq vector? tagsoup/children root)))