2 ms·
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 immuta
by pmarreck 8y ago
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 8y agoYou 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 8y agoIsn't quicksort a type of tree sort? (having just googled both, but not finding said statement)
- jcelerier 8y agoThe haskell quicksort is also wrong : https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort 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 8y agoWell 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 8y agoThe 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 8y agoI 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.