Functional quicksort in JS

test.clj

;; QuickSort in Clojure

;; quicksort :: Ord a => [a] -> [a]
(defn quicksort [seq]
  (if (emtpy? seq) []
    (let [x  (first seq)
          xs (rest seq)]
      (concat (quicksort (filter (fn [v] (<= v x)) xs))
              [x]
              (quicksort (filter (fn [v] (> v x)) xs))))))

test.coffee

# QuickSort in CoffeeScript

# Helpers
empty_p = (seq)    -> !seq.length
concat  = (seq...) -> seq.reduce (l,r) -> l.concat r
first   = (seq)    -> seq[0]
rest    = (seq)    -> seq.slice 1

# quicksort :: Ord a => [a] -> [a]
quicksort = (seq) ->
  sort = (x, xs) ->
    left  = () -> xs.filter (v) -> v <= x
    right = () -> xs.filter (v) -> v > x

    concat (quicksort left())
         , [x]
         , (quicksort right())

  # Result
  if empty_p seq then []
  else                sort (first seq), (rest seq)



# Tests
console.log quicksort [4,2,3,0,1]

test.hs

-- QuickSort in Haskell
-- LE PERFECTION <3

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort l ++ [x] ++ quicksort r
                   where
                     l = [a | a <- xs, a <= x]
                     r = [b | b <- xs, b > x]

test.js

// QuickSort in JavaScript

// quicksort :: Ord a => [a] -> [a]
function quicksort(sequence) {
  return empty_p(sequence)?  []
  :                          sort( first(sequence)
                                 , rest(sequence))

  function sort(x, xs) {
    return concat( quicksort(left(x, xs))
                 , [x]
                 , quicksort(right(x, xs))) }

  function left(x, xs) {
    return xs.filter(function(val) {
      return val <= x })}

  function right(x, xs) {
    return xs.filter(function(val) {
      return val > x })}}


// Helper functions
function slice(sequence) {
  return [].slice.call(sequence) }

function empty_p(sequence) {
  return !sequence.length }

function concat() {
  return slice(arguments).reduce(function(acc, val) {
    return acc.concat(val) }, [])}

function first(sequence) {
  return sequence[0] }

function rest(sequence) {
  return sequence.slice(1) }


// Tests
console.log(quicksort([3,5,8,1,2,0,4,9,6,7]))
console.log(quicksort(Array(100).join(0)
                                .split(0)
                                .map(function(){
                                  return Math.random() * 100 >>> 0 })))

test.ls

# QuickSort in LiveScript

{empty, partition} = require \prelude-ls

# quick-sort :: Ord a => [a] -> [a]
quick-sort = ([x, ...xs]:list) ->
  return [] if empty list
  [left, right] = partition (<= x), xs
  (quick-sort left) +++ [x] +++ (quick-sort right)

console.log (quick-sort [4 2 4 0 1])

Haskell version doesn't use partition. I propose to make 1:1 analog:

quick-sort = ([x, ...xs]:list) ->
  return [] if empty list
  left  = [a for a in xs when a <= x]
  right = [b for b in xs when b > x]
  (quick-sort left) +++ [x] +++ (quick-sort right)

or change haskell version to use one pass too