haskell quick sort, почему первый let использует <= вместо <?

Question

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerOrEqual = [a | a <- xs, a <= x] 
     larger = [a | a <- xs, a > x] 
    in quicksort smallerOrEqual ++ [x] ++ larger 

main = do 
    let a = [ 5, 1, 9, 4, 6, 7, 3] 
    print $ quicksort a 

в Haskell быстрая сортировка, почему первый let использует <= вместо <? Я думаю, <= будет дублировать это x много раз. Почему нет?

Answer 1

< Я думаю = дублирует что х много раз

Нет, это не будет. Давайте поймем, что именно происходит здесь. Вы в основном разбиваете свой список на три части.

1. Список чисел, меньших или равных поворотного элемента (за исключением первого элемента, так что поворотный элемент)

2. Сам (первый элемент в списке) поворотный элемент

3. Список номеров больше, чем поворотного элемента

Таким образом, в вашем случае, распределяли список становится так

[1, 4, 3] ++ [5] ++ [9, 6, 7] 

Рассмотрите такой случай, quicksort [5, 1, 5, 9, 8, 5, 3, 6, 4]. Затем, ваша программа будет разделить его на что-то вроде этого

smallerOrEqual ++ [x] ++ larger 

smallerOrEqual Так и larger работы с xs, которые не имеют x, нет никакого дублирования как таковой. Теперь секционированный список после фильтрации становится

[1, 5, 5, 3, 4] ++ [5] ++ [9, 8, 6] 

См.? Нет дублирования, просто разделение.

Примечание: У вашей программы серьезная ошибка. Проверьте эту линию

quicksort smallerOrEqual ++ [x] ++ larger 

Это в основном работает как этот

(quicksort smallerOrEqual) ++ [x] ++ larger 

Итак, то larger список никогда не отсортирован. Вы рекурсивно должны сортировать как меньший список, так и больший список и, наконец, объединить их в один. Таким образом, это должно было быть

(quicksort smallerOrEqual) ++ [x] ++ (quicksort larger) 

, которые могут быть записаны без скобок, как этот

quicksort smallerOrEqual ++ [x] ++ quicksort larger