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 a previous 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

Tags: clojure, s99

Cet article a été publié le Lundi 26 juillet 2010 à 18:24 et est classé dans Java, Technique. Vous pouvez en suivre les commentaires par le biais du flux RSS 2.0. Vous pouvez laisser un commentaire, ou faire un trackback depuis votre propre site.