1
\$\begingroup\$

Yes, I know we have a lot of these.

I'm new to Clojure, but not to lisps. After the recent (javascript?) parentheses-balancing Q, I decided to do an implementation in Clojure for practice with the language. (It also happened to make a nice accompaniment to my rant about students learning what is and isn't possible with regular expressions.)

I chose to use (reduce) over recursion mostly because I am a fan of letting functions do the work of creating loops and recursion for me, but in this case I am not sure how "elegant" I consider the :false handling.

Code

(ns parens)

(def str->chars (partial map identity))

(defn mk-balanced?
  "makes a balanced? checker from table, which maps closing characters to
  opening characters.

  see also: balanced?"
  [table]
  (fn [s]
    (let [opens (set (vals table))
          closes (set (keys table))]
      (empty?
        (reduce
          (fn [stack cur]
            (if (not= (peek stack) :false)
              (condp contains? cur
                opens (conj stack cur)
                closes (if (and (seq stack)
                                (= (peek stack) (table cur)))
                         (pop stack)
                         [:false])
                stack)
              [:false]))
          []
          (str->chars s))))))

(def balanced?
  (mk-balanced? {\) \(
                 \] \[
                 \} \{}))
\$\endgroup\$
  • \$\begingroup\$ For str->chars just use (vec some-str). \$\endgroup\$ – Alan Thompson Jan 16 at 0:32
  • \$\begingroup\$ @AlanThompson (seq s) is nicer to me, but thanks, that was helpful to learn (I was frustrated not to find an idiomatic version of it on my own!) \$\endgroup\$ – D. Ben Knoble Jan 16 at 0:35
3
\$\begingroup\$

I'd never thought of using reduce for this. Neat! However, you can simplify mk-balanced? a little.

  • str->chars is redundant: reduce and the other sequence functions accept strings as such.
  • You can use reduced to short circuit a reduce.
  • The reduced can return any non-empty sequence: no need for [:false].

The simplified version is ...

(defn mk-balanced? [table]
  (fn [s]
    (let [opens (set (vals table))
          closes (set (keys table))]
      (empty?
        (reduce
          (fn [stack cur]
            (condp contains? cur
              opens (conj stack cur)
              closes (if (and (seq stack)
                              (= (peek stack) (table cur)))
                       (pop stack)
                       (reduced [nil]))
              stack))
          []
          s)))))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the comments :) I actually updated the gist (linked in the Q) several days ago with this approach when I discovered reduced. \$\endgroup\$ – D. Ben Knoble Feb 20 at 2:39
  • \$\begingroup\$ I missed your gist. it's OK around here to answer your own question. However, I enjoyed your code. First convincing example of condp I've seen. \$\endgroup\$ – Thumbnail Feb 20 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.