Comments by "LoneTech" (@0LoneTech) on "Quicksort Algorithm in Five Lines of Code! - Computerphile" video.

  1. C supports recursion. It does not guarantee tail call optimization, but that's insignificant in a branching recursion like quicksort (which is in the C standard library).
    7
  2.  @R.B.  Without filter: qsort list = case list of { [] -> [] ; (b:xs) -> qsort [a | a<-xs, a<b] ++ [b] ++ qsort [c | c<-xs, b<=c] } Of course, : [] ++ < >= are also from Prelude (the default library), as is the Bool type used in the guards. partition is a better choice than filter, but that's in Data.List. Normally I'd use two function cases, but I figured I'd one-line it for fun. I'd argue there is a difference between naming and defining an algorithm.
    4
  3. There's nothing specific to numbers in this implementation.
    4
  4. Very easily: qsort [] = [] qsort (x:xs) = lows `par` highs `par` lows++[x]++highs where lows = qsort (filter (<x) xs) highs = qsort (filter (>=x) xs)
    3
  5. (x:xs) means a list that begins with x (known as the head) and continues with xs (the tail), so it's simply the first element in the list. Other implementations often do something like median of 3 to avoid inefficient edge cases.
    3
  6. Preemptively shunning it is one way to maintain your unfamiliarity.
    2
  7. It's not merge sort.
    2
  8. Very much so. That's why we have types like Data.Vector.Unboxed, and strictness annotation in data constructors. Massiv contains a parallel quicksort with median of 3 pivot selection.
    2
  9. merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x<y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys Can you not tell the difference between that and concatenation?
    2
  10. Yep. Insert, select and bubble sort are the same thing evaluated in different orders; and Haskell evaluates in the order required to produce output.
    2
  11. Minor places like Facebook and Google. Did you know all languages are made up?
    1
  12. @ As a physicist writing in English, you already have the two languages Haskell is based on. All two of the terms that might have been a surprise were explained. Would you be as quick to shun an explanation that stated they used pseudocode, such as Knuth's MIX?
    1
  13. @ So, since pseudocode is simply code that doesn't work, your objection is that this code does work?
    1
  14. ... and decided to be snide about it rather than of any use.
    1
  15.  @sdasda7777  FWIW, a filter in Haskell is typically fused into some other operation and reads only what's needed. E.g. «print . take 5 . filter odd $ [1..]» performs 9 odd checks, even though both sides of the filter are infinite.
    1
  16. Persecution by prejudice.
    1
  17. Merge sort is a distinct algorithm that also subdivides the work. The core distinction is that quicksort uses the comparison to define its partitions (so they do not overlap), while mergesort compares while rejoining them (a step in place quicksort makes null). Both of them exploit transitive comparisons. mergesort :: Ord a => [a] -> [a] mergesort [ ] = [ ] mergesort [x] = [x] mergesort list = let (as,bs) = split list in merge (mergesort as) (mergesort bs) where merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x<=y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys split list = splitAt (length list ˋdivˋ 2) list As for "monadal jiggery pokery", it doesn't typically require making things longer. Working in small sequential steps, particularly on nested structures, often does. Lenses can help a bit with that.
    1
  18. In contrast to you who decide to insult "all Haskell people" repeatedly?
    1
  19. Haskell does not use "the stack" in the way you're thinking of, and it's a very fast structure anyhow.
    1
  20. That's not quicksort, and what's that del for? {⍵[⍋⍵]} will do.
    1
  21. It is the nub of quicksort. Merge sort merges overlapping lists, where this has partitions in order.
    1
  22. For people so stuck up on particular parts of quicksort implementation, those mergesort comparisons are sure hypocritical as there's no merge time reordering being done. The data structure used in this example is a list, which cannot do mutation. Haskell is quite capable of that though, I wrote a 20 line in place quicksort with vector and lens for practice.
    1
  23. ​ @liobello3141  He meant exactly what he wrote. The return stack need not be the only stack (or even exist).
    1