А как на Haskell реализуется сортировка списка?
Там же вроде нет "рандомного" доступа к элементу. Учитывая наличие map и filter.
Или я чего-то не понимаю?
Интересует конечно не встроенная функция api, а как это написать самому руками. С указанием собственной функции сравнения элементов.
Видимо, вот из этой реалализации очевидно, как передать ф-ю сравнения:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
так?
Кстати при "детальном рассмотрении" - даже понятнее, чем qsort на императивных языках. Влево отбираем элементы < x, вправо > x, а x - "посерединке". ;) Ясно и просто ;)
РЕАЛЬНО ПОНЯТНЕЕ, чем qsort на Pascal. Я НАКОНЕЦ реально ПОНЯЛ, как qsort работает.
Да. Да. Реально понятнее.
Декларатив.
?
А что такое <- ?
И что такое in ?
Там же вроде нет "рандомного" доступа к элементу. Учитывая наличие map и filter.
Или я чего-то не понимаю?
Интересует конечно не встроенная функция api, а как это написать самому руками. С указанием собственной функции сравнения элементов.
| HaskellВыделить код | ||
| ||
Видимо, вот из этой реалализации очевидно, как передать ф-ю сравнения:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
так?
Кстати при "детальном рассмотрении" - даже понятнее, чем qsort на императивных языках. Влево отбираем элементы < x, вправо > x, а x - "посерединке". ;) Ясно и просто ;)
РЕАЛЬНО ПОНЯТНЕЕ, чем qsort на Pascal. Я НАКОНЕЦ реально ПОНЯЛ, как qsort работает.
Да. Да. Реально понятнее.
Декларатив.
?
А что такое <- ?
И что такое in ?
Рандомный доступ есть, но он медленный(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 имеют своё специальное значение в монадической записи
Понял.
УдалитьОгромное спасибо за разьяснения.
То что есть списки с рандомным доступом я конечно ни сколько не сомневался.
УдалитьНо мне интересно было в минимальном ADT. List = Null | List a ( List a )