4 ms·

Haskell's intro page starts with the infamous minimalist quicksort, which mishandles NaN! https://wiki.haskell.org/Introduction#Quicksort_in_Haskell https://wi

Haskell's intro page starts with the infamous minimalist quicksort, which mishandles NaN! https://wiki.haskell.org/Introduction#Quicksort_in_Haskell https://wiki.haskell.org/Introduction#Quicksort_in_Haskell

saagarjha 7y ago
How should it handle NaN? It's not clear where an incomparable value should go when sorting.
- ken 7y ago
  Why is NaN even a concept in modern languages? We don’t have a special “not a string” that all string functions return when they have no useful value to return.
  - saagarjha 7y ago
    Because it's part of IEEE 754.
    - ken 7y ago
      So? There’s lots of old standards that don’t fit well with modern programming languages, so we abandoned them, or only use the parts that still make sense.
      - saagarjha 7y ago
        IEEE 754 is one of the standards like two's complement arithmetic which are widely used and have a number of clear advantages, so we continue to use them.
  - mac01021 7y ago
    Because what is the CPU supposed to do if you divide zero by zero or take the square root of -1? It's actually not exactly a decision being made by the language designers. The IEEE standard governs the floating point logic embedded in ALU hardware. Programming languages tend to expose floating point math in its rawest form for performance reasons.
JoelMcCracken 7y ago
I mean, this is a whole different thing, and I legitimately hate that "algorithm". But you have to understand that the whole situation is a bit complicated. The thing though is that Haskell gives you possible ways to handle those complications.
GuB-42 7y ago
I tried it and indeed, the results involving NaN are... interesting quicksort :: Ord a => [a] -> [a] .. quicksort [] = [] .. quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) .. where .. lesser = filter (< p) xs .. greater = filter (>= p) xs quicksort([sqrt(i)|i<-[0 .. 3]]) => [0.0,1.0,1.4142135623730951,1.7320508075688772] quicksort([sqrt(i)|i<-[-3 .. 3]]) => [NaN] quicksort([sqrt(i)|i<-[3 .. -3]]) => [] Now, just for fun, let's reverse the condition... quicksort :: Ord a => [a] -> [a] .. quicksort [] = [] .. quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) .. where .. lesser = filter (\x -> not(x < p)) xs .. greater = filter (\x -> not(x >= p)) xs quicksort([sqrt(i)|i<-[0 .. 3]]) => [1.7320508075688772,1.4142135623730951,1.0,0.0] quicksort([sqrt(i)|i<-[-3 .. 3]]) => [1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0] The last example will explode with larger values, like [-100..100]. Note, it is actually the first time I tried Haskell. And no, I don't think the language is broken because of that. In fact, it is exactly the behavior I expected.

saagarjha 7y ago

How should it handle NaN? It's not clear where an incomparable value should go when sorting.

ken 7y ago
Why is NaN even a concept in modern languages? We don’t have a special “not a string” that all string functions return when they have no useful value to return.
- saagarjha 7y ago
  Because it's part of IEEE 754.
  - ken 7y ago
    So? There’s lots of old standards that don’t fit well with modern programming languages, so we abandoned them, or only use the parts that still make sense.
    - saagarjha 7y ago
      IEEE 754 is one of the standards like two's complement arithmetic which are widely used and have a number of clear advantages, so we continue to use them.
- mac01021 7y ago
  Because what is the CPU supposed to do if you divide zero by zero or take the square root of -1? It's actually not exactly a decision being made by the language designers. The IEEE standard governs the floating point logic embedded in ALU hardware. Programming languages tend to expose floating point math in its rawest form for performance reasons.

JoelMcCracken 7y ago

I mean, this is a whole different thing, and I legitimately hate that "algorithm". But you have to understand that the whole situation is a bit complicated. The thing though is that Haskell gives you possible ways to handle those complications.

GuB-42 7y ago

I tried it and indeed, the results involving NaN are... interesting quicksort :: Ord a => [a] -> [a] .. quicksort [] = [] .. quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) .. where .. lesser = filter (< p) xs .. greater = filter (>= p) xs quicksort([sqrt(i)|i<-[0 .. 3]]) => [0.0,1.0,1.4142135623730951,1.7320508075688772] quicksort([sqrt(i)|i<-[-3 .. 3]]) => [NaN] quicksort([sqrt(i)|i<-[3 .. -3]]) => [] Now, just for fun, let's reverse the condition... quicksort :: Ord a => [a] -> [a] .. quicksort [] = [] .. quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) .. where .. lesser = filter (\x -> not(x < p)) xs .. greater = filter (\x -> not(x >= p)) xs quicksort([sqrt(i)|i<-[0 .. 3]]) => [1.7320508075688772,1.4142135623730951,1.0,0.0] quicksort([sqrt(i)|i<-[-3 .. 3]]) => [1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0,NaN,1.7320508075688772,1.4142135623730951,1.0,0.0] The last example will explode with larger values, like [-100..100]. Note, it is actually the first time I tried Haskell. And no, I don't think the language is broken because of that. In fact, it is exactly the behavior I expected.