One tiny baby step towards functional programming in C++ is to avoid assignment ...

pmarreck · on Jan 23, 2019

There are some corner-cases where immutable data still fails algorithmically... for example I do not know of a performant quicksort that is written in an immutable language (but please, someone correct me if I'm wrong!). It's so wrong, too, because the code for functional quicksort is so beautiful... here it is in Haskell

    quicksort [] = []
    quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
        where (lesser, greater) = partition (< p) xs

and here it is in Elixir

    defmodule QuickSort do
      def qsort([]), do: []
      def qsort([pivot | rest]) do
        { left, right } = Enum.partition(rest, fn(x) -> x < pivot end)
        qsort(left) ++ [pivot] ++ qsort(right)
      end
    end

Tarean · on Jan 23, 2019

You can write the imperative quicksort in haskell and wrap the mutation so it can't escape.

This forces you to copy of the incoming array but optimizations can remove intermediate copies. This is similar to r-values in c++, for instance

    quicksort (fromList [10, 9..1])

would only do one allocation with optimizations.

    freeze . quicksortMutable . copy . new . New.unstream $ Bundle.fromList [10,9..1]
    new . modify quicksortMutable . New.unstream $ Bundle.enumFromStepN 10 (-1) 10

Also, what you posted is tree sort not quick sort.

pmarreck · on Jan 23, 2019

Isn't quicksort a type of tree sort? (having just googled both, but not finding said statement)

jcelerier · on Jan 23, 2019

The haskell quicksort is also wrong : https://stackoverflow.com/questions/7717691/why-is-the-minim...

Here's the correct version taken from one of the SO answers :

    import qualified Data.Vector.Generic as V 
    import qualified Data.Vector.Generic.Mutable as M 

    qsort :: (V.Vector v a, Ord a) => v a -> v a
    qsort = V.modify go where
    go xs | M.length xs < 2 = return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

pmarreck · on Jan 24, 2019

Well according to the reasoning here, no purely functional quicksort will ever be "true quicksort" due to the apparent requirement that the sort be done in-place (mutably). Haskell may have well-thought-out mechanisms in place to do mutation "purely" (which are quite admirable IMHO) but this won't be the case with something like Elixir (Erlang).

This code is also considerably more complex/less beautiful.

I don't know what to call non-in-place Quicksort, but it deserves a name; in the meantime I will simply put it in quotes.

It does seem possible to write an Elixir "quicksort" that does not consume gobs more space than "proper" quicksort, based on the comments there.

waynecochran · on Jan 25, 2019

The following algorithm does not need any mutations:

    quicksort (list)
      if null(list) or else length(list) <= 1
         return list
      else
         p = findpivot(list)
         (lo, hi) = split(p, list)
         return concat(quicksort(lo), quicksort(hi))

I still call it quicksort.

waynecochran · on Jan 23, 2019

I am not sure what you mean by "fails algorithmically," but I do know functional code that performs no (logical) mutations is often dependent on a really smart compiler to do "the right thing" (e.g. convert tail recursion to iteration, re-use memory, etc..).

A "functional" quick-sort in C++ that is also performant sounds like a hard challenge. In this case I am no purest -- I'll use a mutating version -- I suppose that is why Common Lisp provides a destructive version of sort.

If you do create a non-destructive quick sort, you get reentrancy for free so it is easily parallelizable. Writing concurrent routines using non-mutating code (as Carmack says) is much easier to get right.