Skip to content

Instantly share code, notes, and snippets.

@jesse-c jesse-c/counting-valleys.clj Secret
Last active Jun 4, 2019

Embed
What would you like to do?
(defn step [direction level]
(cond
(identical? direction \U) (+ level 1)
(identical? direction \D) (- level 1)
:else level))
(defn monitor [total direction level]
(if (and (zero? level) (identical? direction \U))
(+ total 1)
total))
(defn cv [n s total level]
(let [direction (first s)
level' (step direction level)]
(if (or (zero? n) (empty? s))
total
(cv (- n 1) (rest s) (monitor total direction level') level'))))
(defn countingValleys [n s]
(cv n s 0 0))
(-> (countingValleys 8 "UDDDUDUU")
(println)) ;; 1
(-> (countingValleys 12 "DDUUDDUDUUUD")
(println)) ;; 2
@Vaelatern

This comment has been minimized.

Copy link

commented Jun 3, 2019

First off, very cool! Welcome to the Clojure world!

Anti-patterns

I spotted one anti-pattern after a minute: you define a function with a useless name cv where you already have countingValleys. Let's condense these into the same function, using Clojure's support for multi-arity functions. Note the additional set of parens around each function body, that's all that's necessary!

(defn countingValleys
 ([n s]
  (countingValleys n s 0 0))
 ([n s total level]
  (let [direction (first s)
   level' (step direction level)]
   (if (or (zero? n) (empty? s))
    total
    ; I had to rename the function call in this next line to make sense with the change
    (countingValleys (- n 1) (rest s) (monitor total direction level') level')))))

A second note: I traced n through the function, and it seems to be a vestige from previous development. Let's get rid of it:

(defn countingValleys
 ([s]
  (countingValleys s 0 0))
 ([s total level]
  (let [direction (first s)
   level' (step direction level)]
   (if (empty? s)
    total
    (countingValleys (rest s) (monitor total direction level') level')))))

Notice that we only had to get rid of n, because it served no purpose whatsoever. If you ever need the number of remaining letters, by the way, just (count s).

Here, let's add n back in, but only to act as a "maximum number of characters processed" as before. To do this, we add another arity where we only take from s what we need:

(defn countingValleys
 ([s]
  (countingValleys s 0 0))
 ([n s]
  (countingValleys (take n s) 0 0))
 ([s total level]
  (let [direction (first s)
   level' (step direction level)]
   (if (empty? s)
    total
    (countingValleys (rest s) (monitor total direction level') level')))))

I added the above after I wrote the below, so please pardon n's sudden absence.

recur

One final nit in this function. If I make a lot of ups and downs, say... (expanded for readability)

(take 10000
 (repeatedly #(if (= (rand-int 2) 1)
	       \U
	       \D)))

then how would your (original) recursive function fare?

user=> (countingValleys 10000 (take 10000 (repeatedly #(if (= (rand-int 2) 1) \U \D))))
Execution error (StackOverflowError) at user/eval210$fn (REPL:1).
null
user=>

It's what happens when you get recursive enough, after all.

So let's make this slightly more efficient by making it not recursive! To do this, let's make the last call, instead of recursively countingValleys just to the Clojure-provided recur:

(defn countingValleys
 ([s]
  (countingValleys s 0 0))
 ([s total level]
  (let [direction (first s)
   level' (step direction level)]
   (if (empty? s)
    total
    (recur (rest s) (monitor total direction level') level')))))

For fun, let's bump this up to enough characters to take over a second on my computer:

user=> (countingValleys (take 10000000 (repeatedly #(if (= (rand-int 2) 1) \U \D))))
1274
user=> 

recur isn't a fit in all situations, but it works often enough to keep around.

Other things that stand out

Now, let's get on that use of identical?. While the function has its uses, it generally makes code harder to read than just using =, without benefits. Here is an adversarial example where identical? does not work as you'd hope, but = would:

user=> (-> (Character. \A)
		(identical? \A))
false
user=> (-> (Character. \A)
		(= \A))
true

If you need an explanation, it's that Java is good about constants, but sometimes people can manage to get different memory locations, and it's better to do simple comparisons if you can.

If this is something about optimization, I'd caution against premature optimization. If the comparisons are actually causing unacceptable losses, feel free to use whatever you must to get the job done.

As explained in #clojure on freenode:

<jeaye> identical? is faster, since it's basically just a pointer check. It's useful if you have a cached value and you want to see if the new value is exactly the same.
<jeaye> = is used for general equality and probably >90% of the time. However, good uses of identical? can mean that huge data structures can be compared with a single pointer check.

Finally, there is a function for the (+ 1) pattern: inc. There is also one for (- 1): dec. This is not strictly an anti-pattern, but it betrays the author as being new to the language.

All in all, fantastic program with only a few useful tweaks for readability and quality of life. Welcome to Clojure, I hope you'll stay a while!

Here is a cheatsheet for your future coding reference, in case you have not seen it yet: https://clojure.org/api/cheatsheet

@jesse-c

This comment has been minimized.

Copy link
Owner Author

commented Jun 3, 2019

That was a thorough review. I wouldn't mind more reviews like that at work. ;)

Some interesting points, and you were spot on on several things (like n being left over from development). recur is basically making it tail call optimised?

Ah that's interesting about identical? too and inc. Funnily, there seems to be a function for everything in Clojure (and seemingly Racket too, which I used for another problem).

I'm honestly sold on Lisp, and I'm glad I finally got around to trying it. There's definitely some mental models and other changes that I'll need to learn. Thank you again!

@Vaelatern

This comment has been minimized.

Copy link

commented Jun 4, 2019

I appreciate your kind words, thank you.

As the recur documentation says: Evaluates the exprs in order, then, in parallel, rebinds the bindings of the recursion point to the values of the exprs. So yes, it's tail-call optimization by effectively making it a loop instead of consuming stack. You can control where that binding begins with loop (which is basically let but says "A recur should come back to here").

As for a function for everything, it's really the most common patterns. Incrementing and decrementing happen to be quite useful patterns to understand at a glance. The function I most recently discovered was not=. Finally I could stop writing (not (= a b))! In short, the cheatsheet should stay open while you code: clojure documentation is brilliant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.