PurelyFunctional.tv Newsletter 388: further down (or is it up?) the stack

Written by Eric Normand. Published: July 27, 2020.

Eric Normand's Newsletter

Software design, functional programming, and software engineering practices

Over 5,000 subscribers

Issue 388 - July 27, 2020 · Archives · Subscribe

Clojure Tip 💡

further down (or it is up?) the stack

Last week we wrote a function for doing a depth-first search using our own stack. Here is the code.

(defn dfs-stack [value node]
  (loop [branches (list node)] ;; lists act like stacks
    (if (empty? branches)
      false ;; no more branches, so fail
      (let [node               (peek branches)
            remaining-branches (pop  branches)]
        (or (= value (first node))
            (recur (into remaining-branches (reverse (rest
node)))))))))

Remember, our node is a sequence that looks like:

[value child1 child2 child3 ...]

This week, we are going to look at depth-first search's mirror image, the breadth-first search.

Depth-first search is called that because it recurses all the way down one branch before trying other branches. It uses a stack, which has a last-in-first-out discipline. That means as you add branches to explore, you'll explore the deeper branches first.

Breadth-first search is called that because it search all nodes at the same level before proceeding into the nodes at the next level. Instead of a stack, it uses a queue, which has a first-in-first-out discipline. That means that as you add branches to explore, you'll explore the shallower branches first.

Since we aren't using a stack, we can't do the recursive version. But we can write a version that uses its own queue. Let's write it.

(defn bfs-queue [value node]
  (loop [branches (conj (clojure.lang.PersistentQueue/EMPTY) node)]
    (if (empty? branches)
      false ;; no more branches, so fail
      (let [node               (peek branches)
            remaining-branches (pop  branches)]
        (or (= value (first node))
            (recur (into remaining-branches (rest node))))))))

This function uses a PersistentQueue, using into to add the children to the end, but using peek to get the next branch to process from the front.

So, now that we've got that, we see some striking similarities between our BFS and DFS implementations. One might want to get rid of the duplication by passing in some functions. There are two differences: 1. the construction of the data structure (list or queue) and 2. the order of the nodes being inserted (reverse in the case of dfs). We could pass in functions to represent the differences.

(defn search [value node construct order]
  (loop [branches (construct node)]
    (if (empty? branches)
      false ;; no more branches, so fail
      (let [node               (peek branches)
            remaining-branches (pop  branches)]
        (or (= value (first node))
            (recur (into remaining-branches (order (rest node)))))))))

(defn dfs [value node]
  (search value node list reverse))

(defn bfs [value node]
  (search value node #(conj (clojure.lang.PersistentQueue/EMPTY) %)
identity))

And that would work. It factors out the differences quite nicely.

But I think there's a better way, having to do with the fact that data structures already carry all of the information we are passing in as functions. We just have to think in terms of always operating on a queue or stack of nodes, not just on an individual node. As a first step, let's handle stack vs queue.

(defn search [value branches]
  (if (empty? branches)
    false
    (let [node (peek branches)
          remaining-branches (pop branches)]
      (or (= value (first node))
          (recur value (into remaining-branches (rest node)))))))

(defn dfs [value node]
  (search value (list node)))

(defn bfs [value node]
  (search value (conj (clojure.lang.PersistentQueue/EMPTY) node)))

That looks nice. We still need to handle reversal. The reason we need to reverse in the case of a stack is that we want to handle the left branch first, so we need to add it last. Luckily, the list data structure encodes that.

(defn search [value branches]
  (if (empty? branches)
    false
    (let [node (peek branches)
          remaining-branches (pop branches)]
      (or (= value (first node))
          (recur value
                 (into remaining-branches
                   (into (empty branches) (rest node))))))))

(defn dfs [value node]
  (search value (list node)))

(defn bfs [value node]
  (search value (conj (clojure.lang.PersistentQueue/EMPTY) node)))

This interesting bit of code (into (empty branches) (rest node)) is using an empty version of the data structure we pass in. conjing to a list reverses the order, but conjing to a queue does not. This way, we get the reverse without explicitly specifying it.

Is this a hack? Have I gone too far? I think so. It's too clever. But exploring these extremes is fun and educational.

Now, here's a question for you: what happens if I use a vector as my data structure?

Clojure news 🗞️

Folks, huge news this week: Nubank bought Cognitect.

Cognitect are the stewards of the Clojure language and the owners of Datomic. They also run many of the Clojure conferences around the world.

Nubank is a Brazilian bank built primarily using Clojure(Script) and Datomic. They are very successful financially. They have been active at Clojure conferences (even running one of their own) and have a serious presence in the community.

Some links:

I think this is a good thing for Clojure. Many successful languages we rely on eventually get support from large companies. It's a proven model that helps guarantee stability and prosperity in the maintainers' lives while they work on open source projects. Nubank is communicating that they understand that.

For Datomic, it's also good. C ognitect will be focusing more on Datomic clients while winding down more general services. That can only mean Datomic will get better faster. And while Datomic remains a commercial product, it's still a pillar of the Clojure ecosystem.

I also believe that this will help the conference scene as well. I'm not sure if Clojure's conferences were ever profitable (or even break-even). Deep pockets to pull from, along with more staff working on them, can only make the conferences better and more accessible. We'll have to wait and see how this develops.

Podcast episode🎙

I have a new episode out asking What is software design?. I've never been very satisfied with the term, but I think I've come up with a definition that eases my discomfort.

Quarantine update 😷

I know a lot of people are going through tougher times than I am. If you, for any reason, can't afford my courses, and you think the courses will help you, please hit reply and I will set you up. It's a small gesture I can make, but it might help.

I don't want to shame you or anybody that we should be using this time to work on our skills. The number one priority is your health and safety. I know I haven't been able to work very much, let alone learn some new skill. But if learning Clojure is important to you, and you can't afford it, just hit reply and I'll set you up. Keeping busy can keep us sane.

Stay healthy. Wash your hands. Stay at home. Wear a mask. Take care of loved ones.

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 387 was to censor naughty words. You can find the submissions here.

Please do participate in the discussion on the gist where the submissions are hosted. It's active and it's a great way to get comments on your code.

This week's challenge

Title Case*

In English, titles of books get their own type of capitalization called title case. In title case, major words are capitalized and minor words are in lower case. Most words are major words. Minor words are:

three letters or shorter AND
conjunctions, articles, or prepositions

And, finally, the first word of a title is always capitalized, even if it is a minor word.

For a better, and more complete, summary of the nuances of title case, see the APA guide here: https://apastyle.apa.org/style-grammar-guidelines/capitalization/title-case

Your task is to write a function that implements title case. The string you get will already have proper nouns capitalized, and you can otherwise assume you only need to capitalize words, not lowercase them.

Here's an example:

(title-case "the hobbit") ;=> "The Hobbit"
(title-case "the fellowship of the ring") ;=> "The Fellowship of the
Ring"
(title-case "the two towers") ;=> "The Two Towers"
(title-case "the return of the king") ;=> "The Return of the King"

Here is a list of minor words you can use:

["and" "as" "but" "for" "if" "nor" "or" "so" "yet" "a" "an" "the" "as" "at" "by"
"for" "in" "of" "off" "on" "per" "to" "up" "via"]

There are probably more minor words, but that's a good list to start with.

Also, please take this function as far as you'd like, using any title case rules as you see fit. The English language has no definitive standard, so many places define their own rules that may differ.

Thanks to this site for the challenge idea where it is considered Medium level in Python.

You can also find these same instructions here. I might update them to correct errors and clarify the descriptions. That's also where submissions will be posted. And there's a great discussion!

As usual, please reply to this email and let me know what you tried. I'll collect them up and share them in the next issue. If you don't w ant me to share your submission, let me know.

Rock on!
Eric Normand