destructuring/multimethods vs. pattern matching

[Stuart Halloway]

Hi all,

I seem to recall Rich saying "I like the destructuring part of pattern
matching." In my efforts to appreciate that statement, I am playing
around with porting simple Haskell examples to Clojure, trying to use
destructuring (and multimethods) where the Haskell does pattern matches.

For example:

-- Haskell
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort bigger
where smaller = filter (<x) xs
bigger = filter (>=x) xs

; Clojure, destructuring pivot and vals
(defn quicksort-1 [[pivot & vals]]
(if pivot
(let [smaller (partial filter #(< % pivot))
bigger (partial filter #(>= % pivot))]
(lazy-cat (quicksort-1 (smaller vals)) [pivot] (quicksort-1
(bigger vals))))
nil))

; Clojure again, using multimethod to separate base and recur
(defmulti quicksort-2 first)
(defmethod quicksort-2 nil [_] nil)
(defmethod quicksort-2 :default [[pivot & vals]]
(let [smaller (partial filter #(< % pivot))
bigger (partial filter #(>= % pivot))]
(lazy-cat (quicksort-2 (smaller vals)) [pivot] (quicksort-2
(bigger vals)))))

I am confident that the Clojure could be prettier, but not sure how.
Suggestions?

Cheers,
Stuart

[Stephen C. Gilardi]

On Oct 20, 2008, at 11:16 AM, Stuart Halloway wrote:

Hi all,

I seem to recall Rich saying "I like the destructuring part of pattern  
matching." In my efforts to appreciate that statement, I am playing  
around with porting simple Haskell examples to Clojure, trying to use  
destructuring (and multimethods) where the Haskell does pattern matches.

For example:

-- Haskell
qsort []     = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort bigger
    where smaller = filter (<x)  xs
          bigger = filter (>=x) xs

[...]

I am confident that the Clojure could be prettier, but not sure how.  
Suggestions?

Here are a couple of ideas:

The first is a more literal translation of the Haskell code with 'when providing the nil case:

(defn quicksort-3 [[x & xs]]

  (when x

    (let [smaller (filter #(< % x) xs)

          bigger (filter #(>= % x) xs)]

      (lazy-cat (quicksort-3 smaller)

                [x]

                (quicksort-3 bigger)))))

The second uses the filter/remove complementary pair so there's only one predicate:

(defn quicksort-4 [[x & xs]]

  (when x

    (let [smaller #(< % x)]

      (lazy-cat (quicksort-4 (filter smaller xs))

                [x]

                (quicksort-4 (remove smaller xs))))))

--Steve

[Achim Passen]

Hi!

Here's a variadic version:

(defn qsort
([] [])
([x & xs] (concat (apply qsort (filter #(< % x) xs))
(cons x (apply qsort (filter #(>= % x) xs))))))

user> (qsort 1234 56 789 0)
(0 56 789 1234)

Kind regards,
achim

--
http://rauschabstand.twoday.net

[Stuart Halloway]

Hi Steve,

Thanks! I like quicksort-4. It all fixes a problem that bugged me in
all the other examples, which is that "bigger" is a lie. The real
semantic is "not smaller", which quicksort-4 captures perfectly.

I will have to get used to thinking of "remove" as the opposite of
"filter." The English connotations of the former are too imperative
for me, but I don't know a better word for it.

Stuart

[Martin DeMello]

On Oct 20, 10:43 am, Stuart Halloway <stuart.hallo...@gmail.com>
wrote:

> Hi Steve,
>
> Thanks! I like quicksort-4. It all fixes a problem that bugged me in  
> all the other examples, which is that "bigger" is a lie. The real  
> semantic is "not smaller", which quicksort-4 captures perfectly.
>
> I will have to get used to thinking of "remove" as the opposite of  
> "filter." The English connotations of the former are too imperative  
> for me, but I don't know a better word for it.

I like ruby's "reject".

martin

[Stuart Halloway]

Hi Achim,

Nice--I like this one, except for needing to apply. What I really want
is arity overloading *within* the first argument, which is what led me
down the path to multimethods.

Is there a reason to prefer concat over lazy-cat here?

Cheers,
Stuart

[Achim Passen]

Hi Stuart,

Am 20.10.2008 um 20:00 schrieb Stuart Halloway:

> Nice--I like this one, except for needing to apply. What I really want
> is arity overloading *within* the first argument, which is what led me
> down the path to multimethods.

Yes, sadly arity matching is only available at the top level, so
applying was the only way to closely translate the Haskell version i
could see.

What are your concerns re: apply? Are there performance issues? Or is
it not being able to call qsort on a collection directly?

> Is there a reason to prefer concat over lazy-cat here?

No, that was entirely unintentional - sorry for the confusion.

Kind regards,
achim

--
http://rauschabstand.twoday.net

[Stuart Halloway]

> What are your concerns re: apply? Are there performance issues? Or is
> it not being able to call qsort on a collection directly?

I just want the code to look pretty, no deeper concerns than that. :-)