Developer notes: April 2019

Some of these days I had fun with Haskell. I tried to write Hoare's sort in Haskell. For my implementation I used list's filtering by the element that was in the middle of the list:


qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort xs = partitions (xs !! (div ((length xs) - 1) 2)) xs where
  partitions x' xs' =
    qsort (filter (< x') xs') ++ (filter (== x') xs') ++ qsort (filter (> x') xs')

What is the most interesting that using of this kind of filtering allows to write a more intuitive algorithm than a variant with an imperative implementation. For comparison, below we can see implementations in Ruby.

This is a variant of imperative implementation:


def hoaresort(array, first, last)
  i, j = first, last
  x  = array[(i + j) / 2]

  begin
    i += 1 while array[i] < x
    j -= 1 while array[j] > x

    if i <= j
      array[i], array[j] = array[j], array[i] if i < j
      i += 1
      j -= 1
    end
  end while (i <= j)

  hoaresort(array, i, last) if i < last
  hoaresort(array, first, j) if first < j

  # Uncomment next line if you want to return sorted array as result
  # array
end

And next is a variant of functional implementation:


def hoaresort(array)
  return [] if array.length == 0
  
  x = array[(0 + (array.length - 1)) / 2]
  
  hoaresort(array.filter { |v| v < x }) +
    array.filter { |v| v == x } +
      hoaresort(array.filter { |v| v > x })
end

In my opinion the comparison obviously shows us that the functional approach is more clear and understandable.

Developer notes

Ruby/Haskell. Hoare's partition sort or quick sort. Imperative or functional approach?

curl. Basic authentication