PurelyFunctional.tv Newsletter 378: Clojure nudges us to constant-time operations

Issue 378 - May 18, 2020 · Archives · Subscribe

Clojure Tip 💡

Clojure nudges us to constant-time operations

I recently received a question about why Clojure has contains? (which is really contains-key?) and not a contains-value?. It seems like such a common thing to want to do, shouldn't Clojure give it to us? I mean, without it, you have to do something like this over a vector or a list:

(some #(= needle-value %) haystack-collection)

That's not as nice or as clear.

Well, there's a good reason. Calling some is a linear operation. The number of steps it takes grows with the length of the collection you are looking through. Clojure really prefers constant-time operations, so it's not going to try to make this linear one easy to do.

I don't know if this is really what Rich Hickey was thinking, but I like Clojure's preference and I'll explain why.

If you're doing the linear search over the collection one time, there's no problem. But that also means it's not that inconvenient to write out the code above.

If you're doing a linear search a lot, then you're probably using the wrong data structure. Sets have constant-time lookup of value containment. You should probably dump your linear vector into a set in linear time once, then do lots of lookups on it in constant time.

(into #{} haystack-collection)
;; OR
(set haystack-collection)

Linear searches are often fine, but they are so easy to accidentally become quadratic. In fact, there's a whole blog dedicated to quadratic algorithms in the wild called Accidentally Quadratic. If you do a linear search inside of a linear loop, that's quadratic. It's best to do as much in constant time as possible.

Clojure is nudging you toward choosing the right data structure for the job by making less time-efficient operations slightly less convenient. I appreciate that help because it has actually taught me to think better about my algorithms and data structures.

Follow-up 🙃

Awesome reader Drew Verlee reminded me that it's not great to cram nils into your maps. That's true! I should have mentioned that. Avoid nils in your maps if you can. Still, sometimes you get a map from somewhere else.

Another awesome reader, Stuart Campbell, shared his pattern for distinguishing the three cases:

(let [value (get some-map key ::missing)]
  (if-not (= ::missing value) …))

A third awesome reader, Jeff Gortatowsky, let me know that my code could be clearer with better names. I wrote:

(if (contains? mp k)
  (let [v (get mp k)]
    (println "It's in there:" v)) ;; sometimes v is nil
  (println "It's not in there."))

I used mp to name a hash map, k to name the key, and v to name the value. Especially for code that's meant to be instructive, I should have used more explanatory names. My apologies! Names are important.

PurelyFunctional.tv Update 💥

Just before the quarantine, I enacted plans to discontinue new memberships to PurelyFunctional.tv. However, the timing was terrible! I planned to make individual course sales much more interesting, but I have not gotten to them yet.

I've reopened memberships to anyone who wants them. I'll discontinue them again later, with the same policy of allowing existing memberships to continue.

If you would like a membership, check out the Register page. Memberships give you access to 100 hours of video courses on Clojure, ClojureScript, and tooling.

Book update 📖

Chapter 8 was just released as part of the Manning Early Access Program. Chapter 8 is all about Stratified Design, where we learn to organize our code into layers. This chapter took me a long time. It was hard for me to boil down this design skill.

You can buy the book and use the coupon code TSSIMPLICITY for 50% off.

I'm currently working on Chapter 11, which is going pretty smoothly. Chapter 11 is all about chaining maps, filters, and reduces. A very important skill!

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 377 was to validate finished sudoku boards. You can see the submissions here.

You can leave comments on these submissions in the gist itself. Please leave comments! There are lots of great discussions in there. You can also hit the Subscribe button to keep abreast of the comments. We're all here to learn.

And I must say that I am so happy with the discussions happening in the gist comments. People are getting fast feedback from each other and trying out multiple implementations. Check it.

This week's challenge

Symmetry

We need to classify patterns into four different categories:

1. horizontally symmetrical
2. vertically symmetrical
3. perfect (both vertically and horizontally symmetrical)
4. imperfect (neither vertically nor horizontally symmetrical)

Patterns are two-dimmensional. We will represent them with vectors of vectors. Each inner vector is a row.

Write a function classify that takes a pattern and returns one of :vertical, :horizontal, :perfect, or :imperfect.

Examples

(classify [["a" "b" "a"]
           ["x" "y" "x"]]) ;=> :horizontal
(classify [["a" "b" "c"]]) ;=> 

:vertical ;; trivially so
(classify [["a" "b" "a"]
           ["y" "X" "y"]
           ["a" "b" "a"]]) ;=> :perfect

Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.

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