среда, 1 ноября 2017 г.

Haskell. Вопрос. Сортировка

А как на Haskell реализуется сортировка списка?

Там же вроде нет "рандомного" доступа к элементу. Учитывая наличие map и filter.

Или я чего-то не понимаю?

Интересует конечно не встроенная функция api, а как это написать самому руками. С указанием собственной функции сравнения элементов.

HaskellВыделить код
1
2
3
4
5
6
quicksort [] = ([]++[])
quicksort (h:t) = 
    let
       left = quicksort [x | x<-(h:t), x<h]
       right = quicksort [x | x<-(h:t), x>h]
    in left++[h]++right

Видимо, вот из этой реалализации очевидно, как передать ф-ю сравнения:

qsort []     = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

так?

Кстати при "детальном рассмотрении" - даже понятнее, чем qsort на императивных языках. Влево отбираем элементы < x, вправо > x, а x - "посерединке". ;) Ясно и просто ;)

РЕАЛЬНО ПОНЯТНЕЕ, чем qsort на Pascal. Я НАКОНЕЦ реально ПОНЯЛ, как qsort работает.

Да. Да. Реально понятнее.

Декларатив.

?

А что такое <- ?
И что такое in ?

3 комментария:

  1. Рандомный доступ есть, но он медленный(Data.List.!!). Впрочем как любой рандомный доступ к (одно)связанному списку(И да, здесь есть массивы с быстрым произвольным доступом).

    Так не интересно, вы сами на все вопросы почти ответили..
    Ваш qsort правильный, только если нужно передать функцию сравнения, можно сделать так(т.к. ваш вариант не отличается от приведенного в примере, хоть и написан красивше):
    qs _ [] = []
    qs f (x:xs) = qs f (filter (f x) xs) ++ x : qs f (filter (not . f x) xs)
    Использование:
    qs (>) [3,4,7,3,1] --> [1,3,3,4,7]
    qs (<) [3,4,7,3,1] --> [7,4,3,3,1]

    Далее:
    (<-) в данном случае имеет отношение к специальному синтаксису объявления списков.
    Например
    [x | x <- [1..1000], even x] --> [2,4,6,8,10]
    [x + y | x <- [1..10], y <- [10,20,30], even x] --> [12,22,32,14,24,34,16,26,36,18,28,38,20,30,40]

    in относится к блоку объявления констант let. Например let x = 1; y = 2 in x + y --> 3
    Для объявлений констант есть дополнительный синтаксис where; Например n = t where t = 3. (но блок where относится к самой декларации 'n = t', а не к выражению 't'. Его можно использовать в декларациях, но не в других блоках, как let. Можно написать print (let t = 10 in t), но нельзя print (t where t = 10).

    (<-) и let имеют своё специальное значение в монадической записи

    ОтветитьУдалить
    Ответы
    1. Понял.
      Огромное спасибо за разьяснения.

      Удалить
    2. То что есть списки с рандомным доступом я конечно ни сколько не сомневался.

      Но мне интересно было в минимальном ADT. List = Null | List a ( List a )

      Удалить