G>int sum = 0;
G>for(int i=0; i<N; i++)
G>{
G>   sum += list[i];
G>}
G>

G>fold (+) list
G>

G>>fold (+) list
G>>

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

G>fold (+) list
G>

G>>fold (+) list
G>>

ТЗИ>x = sum of all items in list
ТЗИ>

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

N>быстрая сортировка пустого списка = пустой список
N>быстрая сортировка списка, первый элемент которого x, а хвост списка xs = 
N>  конкатенация 3 списков:
N>    быстрой сортировки xs, из которого отфильтрованы элементы, меньшие x
N>    списка из одного элемента x
N>    быстрой сортировки xs, из которого отфильтрованы элементы, большие или равные x
N>

N>>быстрая сортировка пустого списка = пустой список
N>>быстрая сортировка списка, первый элемент которого x, а хвост списка xs = 
N>>  конкатенация 3 списков:
N>>    быстрой сортировки xs, из которого отфильтрованы элементы, меньшие x
N>>    списка из одного элемента x
N>>    быстрой сортировки xs, из которого отфильтрованы элементы, большие или равные x
N>>

ТЗИ>Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

ТЗИ>Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.

ТЗИ>Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

N>>быстрая сортировка пустого списка = пустой список
N>>быстрая сортировка списка, первый элемент которого x, а хвост списка xs = 
N>>  конкатенация 3 списков:
N>>    быстрой сортировки xs, из которого отфильтрованы элементы, меньшие x
N>>    списка из одного элемента x
N>>    быстрой сортировки xs, из которого отфильтрованы элементы, большие или равные x
N>>

ТЗИ>Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
ТЗИ>Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
ТЗИ>Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
ТЗИ>Вычисляется индекс опорного элемента m.
ТЗИ>Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
ТЗИ>Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше опорного.
ТЗИ>Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
ТЗИ>Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
ТЗИ>Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
ТЗИ>Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

G>Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату

G>>Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату

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

N>быстрая сортировка пустого списка = пустой список
N>быстрая сортировка списка, первый элемент которого x, а хвост списка xs = 
N>  конкатенация 3 списков:
N>    быстрой сортировки xs, из которого отфильтрованы элементы, меньшие x
N>    списка из одного элемента x
N>    быстрой сортировки xs, из которого отфильтрованы элементы, большие или равные x
N>

G>let sum = fold (+) 0
G>

G>>fold (+) list
G>>

ТЗИ>x = sum of all items in list
ТЗИ>

lidfulj3*)(##*&kd*97

VD>def quickSort(lst)
VD>{
VD>  | [] => [];
VD>  | x :: xs  => qs($[ y | y in xs, y < x ]) + [x] + qs($[y | y in xs, y >= x]);
VD>}
VD>