Avoiding repetition while still using 'recur'

[Botond Balázs]

Hi,

Here is my solution to 4clojure problem #177:

Write a function that takes in a string and returns truthy if all square [ ] round ( ) and curly { } brackets are properly paired and legally nested, or returns falsey otherwise.

(defn valid-parens?

  [s]

  (loop [[ch & chs] s stack []]

    (if (nil? ch)

      (empty? stack)

      (case ch

        (\( \[ \{) (recur chs (conj stack ch))

        \) (if (= (peek stack) \()

             (recur chs (pop stack))

             false)

        \] (if (= (peek stack) \[)

             (recur chs (pop stack))

             false)

        \} (if (= (peek stack) \{)

             (recur chs (pop stack))

             false)

        (recur chs stack)))))

This works but I don't like the repetition in the case branches. But the repeated code contains a recur call so I can't simply refactor it into a helper function. How can I achieves something like the following, but without consuming the stack?

(defn valid-parens?

  ([s]

   (valid-parens? s []))

  ([[ch & chs] stack]

   (if (nil? ch)

     (empty? stack)

     (letfn [(match? [p]

               (if (= (peek stack) p)

                 (valid-parens? chs (pop stack))

                 false))]

       (case ch

         (\( \[ \{) (valid-parens? chs (conj stack ch))

         \) (match? \()

         \] (match? \[)

         \} (match? \{)

         (valid-parens? chs stack))))))

Thanks!

Botond

[Colin Yates]

Skimming through but that `case` resolves to either false or a recur
so sure you can move that case to an helper fn which returns true or
false. If false then `return` else `recur`?

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[James Reeves]

The easiest way would be to factor out the bracket matching code, since that's the only thing that changes between your different case statements. For instance:

  (defn valid-parens? [s]

    (let [opening-brackets {\( \), \[ \], \{ \}}

          closing-brackets (clojure.set/map-invert opening-brackets)]

      (loop [cs (seq s), stack []]

        (if-not cs

          (empty? stack)

          (let [c (first cs), cs (next cs)]

            (if (opening-brackets c)

              (recur cs (conj stack c))

              (if-let [b (closing-brackets c)]

                (if (= (peek stack) b)

                  (recur cs (pop stack))

                  false)

                (recur cs stack)))))))

Another way you could do it is to replace your recursive call with a continuation.

- James

On 26 June 2016 at 13:43, Botond Balázs <balazs...@gmail.com> wrote:

--

[Botond Balázs]

Thanks guys.

Very nice and simple solution, James.

[Andy-]

To add a little variant of James Reeve's code: You can avoid the loop/recur by using reduce:

(defn valid-parens? [s]
  (let [opening-brackets {\( \), \[ \], \{ \}}
        closing-brackets (clojure.set/map-invert opening-brackets)]

    (empty?
      (reduce
        (fn [stack c]
          (if (opening-brackets c)
            (conj stack c)

            (if-let [b (closing-brackets c)]
              (if (= (peek stack) b)

                (pop stack)
                (reduced [false]))
              stack)))
        []
        (seq s)))))

HTH

[Botond Balázs]

I didn't know that reduction can be stopped with reduced. Thanks Andy!