На этом шаге мы рассмотрим эту функцию.
Функция, производящая сортировку элементов целочисленного списка в возрастающем порядке имеет следующий синтаксис:
sort lst
> sort [1] > sort [-2,-4,3,-5,12] [1] [-5,-4,-2,3,12]
Замечание (важное). Для работы с функцией требуется подключить модуль List:
> :load List
Приведем несколько демонстрационных примеров.
-- Демонстрация реализации быстрой сортировки (по А.Хоару) -- элементов одноуровневого списка -- ******************************* quickSort:: Ord a => [a] -> [a] quickSort [] = [] quickSort (x:xs) = quickSort [y|y <- xs, y<x] ++ [x] ++ quickSort [y|y <- xs, y>=x] -- ********************************************** -- Неудачные тестовые примеры: -------------------------------------------------- test1 = quickSort (reverse [1..400]) == [1..400] && quickSort [6,5,4,3,2,1] == [1,2,3,4,5,6] && quickSort [6,2,4,4,2,6] == [2,2,4,4,6,6] && quickSort [1,2,3,4,5,6] == [1,2,3,4,5,6] && quickSort [0] == [0] --------------------------------------------- test2 = quickSort (map (\x -> sin x) [1..10])
import List ------------------------------------------------------------ -- Функция, добавляющая элементы числового списка lst в упо- -- рядоченный список lst1 без нарушения упорядоченности ------------------------------------------------------- rasst:: [Int] -> [Int] -> [Int] rasst lst lst1 | null lst = lst1 | True = insert' (head lst) (rasst (tail lst) lst1) ----------------------------------------------------------- -- Функция insert' добавляет элемент x в упорядоченный -- список lst с сохранением упорядоченности ------------------------------------------- insert':: Int -> [Int] -> [Int] insert' x lst | null lst = [x] | x<=head lst = x : lst | True = head lst : insert' x (tail lst) -- ********************************************************** -- Неудачные тестовые примеры: ---------------------------------------------- test1 = rasst [] [] == [] && rasst [] [3,4,5] == [3,4,5] && rasst [4,3,2] [] == [2,3,4] && rasst [1,5,3,7] [2,4,6,8] == [1,2,3,4,5,6,7,8] && rasst [41,31,21,11] [1,56,67] == [1,11,21,31,41,56,67] && rasst [4,3,1] [1,2,5,6] == [1,1,2,3,4,5,6] ----------------------------------------------------------- test2 = insert 3 (sort [41,31,21,11]) == [3,11,21,31,41] && insert 34 (sort [1,32,21,13]) == [1,13,21,32,34]
На следующем шаге мы приведем перечень задач для самостоятельного решения.
