PurelyFunctional.tv Newsletter 387: to stack or not to stack

Issue 387 - July 20, 2020 · Archives · Subscribe

Clojure Tip 💡

to stack or not to stack

One of the cool things about recursion in functional languages is that you get an implicit stack for free. It's just the regular call stack. But sometimes you will want to use your own stack.

Here's an example of depth-first search over a tree.

Well, let's define the tree first.

A node in the tree is a sequence. Each node has one value and zero or more children.

[value child1 child2 child3 ...]

Of course, this data structure is recursive. The children are defined in the same way. The leaves of the tree are a sequence with just a value and no children.

[10]

Okay, now that that's out of the way, how can we do a depth-first search over this tree? Depth-first search means we need to follow a branch to the end before we "backtrack" and search the next branch. That's easily coded in a recursive function. This function returns true if it finds the value in the tree.

(defn dfs [value node]
  (or (= value (first node))              ;; check current node
      (some #(dfs value %) (rest node)))) ;; recurse down each child

The classic formulation of depth-first search uses a stack to keep track of branches to visit next. Because recursion uses the stack, we get a stack for free.

But there's a problem. If your tree is really deep, it could blow the stack. The call stack is big but you might have trees bigger than it. The solution is to use an explicit stack.

Here's how you'd do that.

(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)))))))))

Notice that it's tail-recursive (with loop recur) so it won't consume the call stack. We're using a list as a stack, and calling it branches. We're also reversing the children so that they are traversed left-first.

This implementation can traverse trees of any depth because the stack is not limited. But the important thing to take away is that you can use the call stack you get with recursion (which is often good enough) or your own stack if you want. You can always convert between them.

Next week, we'll see how this relates to the strategy opposite depth-first search, which is breadth-first search.

Podcast episode🎙

My new episode about the classic paper Why Functional Programming Matters by John Hughes is out. In it, we try to understand this paper's answer to the question of why functional programming is powerful.

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 386 was to write a function to find the indexes of a particular value in a sequence. You can find the submissions here.

Very nice variety of answers in this one. I think it's great when I do an easy one and there are so many different ways to do it.

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

This week's challenge

textual bleeping

Let's say you run a big website for kids and you want to prevent your young users from reading certain naughty words. (Note: it's just a silly example, please don't email me about kids, language, and censorship.) Write a function that takes uncleaned text and a list of naughty words, replaces naughty words found in the text with an equivalent number of asterisks.

Here's an example:

(clean "You are a farty pants." ["fart" "poop"]) ;=> "You are a ****y
pants."
(clean "Curse this site!" ["jinx" "curse"]) ;=> "**** this site!"

Bonus: write the reverse function. It takes text and replaces *'s with naughty words of the same length.

Thanks to this site for the challenge idea where it is considered Hard 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 want me to share your submission, let me know.

Rock on!
Eric Normand