My Clojure explained solutions to the s99 problems 4 to 7

In this post, I’ll continue presenting my solutions for the s99 problems in Clojure. As a reminder, I’ve already covered the first 3 problems in this post.

P04

Find the number of elements of a list.
Example:
user> (length ‘(1, 1, 2, 3, 5, 8))
6

My first solution relies on recursion to find out the length of a list:

  • The length of an empty list is zero
  • The length of a non-empty list is 1 plus the length of that list without its first element

The code shown below is a direct transcription of this:

(defn length "P04" [l]
  (if (empty? l) 0 (inc (length (rest l)))))

Another solution relying on reduce:

(defn length "P04" [xs]
  (reduce (fn [l x] (inc l)) 0 xs))

I’ve already described how reduce operates on a list, but in a nutshell, it’ll pick the first element of the list and feed it with the initial value (0 in this case) the the reduction function, which increments the 0 (representing the list’s length). The result of the reduction (1), along with the next element of the list will be fed again to the reduction function, and the whole process will be repeated until all the list elements are consumed, yielding the list’s length in the end.

You’ll notice that I used the fn form to define the reduction function instead of the shorthand notation (written with the # symbol). When I try to define a reduction function that doesn’t reference %2 (the second parameter) using the shorthand notation, reduce would throw a “Wrong number of parameters” exception:

(defn length "P04" [xs]
  (reduce (inc %1) 0 xs))

Wrong number of args passed to: user$eval–2528$fn
[Thrown class java.lang.IllegalArgumentException]

I’ll quote here a tweet from Michael Fogus, the Co-Author of “The joy of clojure” explaining why:

#() will not gen a 2-arg fn without a reference to %2. Use the (fn [x y] ..) form, or use a %2. Or (reduce #(apply + %&) [1 2 3])

P05

Reverse a list.
Example:
user> (reverse ‘(1 1 2 3 5 8))
(8 5 3 2 1 1)

My first solution relies on recursion to find out the length of a list:

  • The reverse of an empty list is an empty list
  • The reverse of a non-empty list xs is the list whose first element is xs’s last element and whose rest is the reverse of xs’s rest

The code shown below is a direct transcription of this:

(defn reverse-s99 "P05" [l]
  (if (empty? l)
    nil
    (cons
     (last l)
     (reverse-s99 (butlast l)))))

Again, another way to do it would be to use reduce:

(defn reverse-s99 "P05" [xs]
  (reduce (fn [r x] (cons x r)) '() xs))

Basically, this starts with an empty list r, and iterates over xs’s items adding each one of them to r’s beginning.

P06

Find out whether a list is a palindrome.
Example:
user> (palindrome? ‘(1 2 3 2 1))
true

(defn palyndrome? "P06" [l]
  (= l (reverse-99 l)))

No comment !

P07

Flatten a nested list structure.
Example:
user> (flatten ‘((1 1) 2 (3 (5 7))))
(1 1 2 3 5 7)

(defn flatten "P07" [l]
  (reduce
   #(concat %1 (if (list? %2) (flatten %2) (list %2)))
   '()
   l))

It’s getting a bit cryptic. What this does is:

  • Start with an empty result list
  • For every item of the list to flatten, if it’s (%2) a list, flatten it, otherwise create a list out of it. In both cases, add all of the resulting list items to the result list
About these ads

One Response to My Clojure explained solutions to the s99 problems 4 to 7

  1. Pingback: My Clojure explained solutions to the s99 problems 21 to 26 « Jawher's Blog

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: