Текст ниже взят из лекций "Кафедра Кибернетики МИФИ: Функциональное программирование, группы К7-222 и К7-223. В настоящем варианте читаются с 2001 года.".
Пример 1. Быстрая сортировка Хоара на C.
void quickSort (int a[], int l, int r)
{
int i = l;
int j = r;
int x = a[(l + r) / 2];
do
{
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j);
if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}
Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.
quickSort ([]) = []
quickSort ([h : t]) = quickSort (n | n ∈ t, n <= h) + [h] + quickSort (n | n ∈ t, n > h)
Пример 2 следует читать так:
1. Если список пуст, то результатом также будет пустой список.
2. Иначе (если список не пуст) выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста, которые меньше либо равны голове, списка из самой головы и списка из всех элементов хвоста, которые больше головы.
Пример 3. Быстрая сортировка Хоара на языке Haskell.
quickSort [] = []
quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
Как видно, даже на таком простом примере функциональный стиль программирования выигрывает и по количеству написанного кода и по его элегантности.
Вы согласны с тем, что пример на Haskell действительно лучше?
Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Сделана человеческая разметка. Не забывайте делать предпросмотр!!! — Кодт
Здравствуйте, md03t4, Вы писали:
M>Обращу внимание на то, что код на С понятен почти любому программисту
Мне не понятен. Не потрудитесь в двух словах рассказать, что там происходит? Ну, кроме того, что сортировка.
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++.
Неверно.
M>И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Бездоказательно. Более того, он изобилует деталями реализации, которые затрудняют понимание алгоритма. На хаскелле код — именно то, что он делает. Пояснений не читал.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Да, хорош. Хоть и не самый эффективный вариант. Эффективная реализация этого алгоритма будет менее лаконичной, конечно.
Но квиксорт — это все мелочи. Вот есть два языка — Boo и Haxe. Оба — высокоуровневые языки со статической типизацией и
выводом типов. Компилятор одного реализован на C#, компилятор второго — частично на OCaml. Можете попробовать сравнить,
например, как там и там реализована система типов, и в коде на каком языке быстрее разберетесь.
Здравствуйте, md03t4, Вы писали:
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет
Это неверно. Не путай знание синтаксиса с понятностью. Пояснение к примеру на хаскель дается потому что читатель не знает, что означают эти значки. Если б читатель не знал и Cи, ему б потребовалось объяснение и для первого примера. Переведи оба примера на чисто русский язык, и сам всё увидишь.
Re: Простая и короткая программа на Haskell
От:
Аноним
Дата:
14.05.09 08:44
Оценка:
Здравствуйте, md03t4, Вы писали:
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Да.
M>Обращу внимание на то, что код на С понятен почти любому программисту,
Не понятен совершенно. Много букав. Алгоритм в голове прокручивать приходится.
M> А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Не требуется — классическая запись для множеств, любому математику понятная.
M>void quickSort (int a[], int l, int r)
M>{
M> int i = l;
M> int j = r;
M> int x = a[(l + r) / 2];
M> do
M> {
M> while (a[i] < x) i++;
M> while (x < a[j]) j--;
M> if (i <= j)
M> {
M> int temp = a[i];
M> a[i++] = a[j];
M> a[j--] = temp;
M> }
M> }
M> while (i <= j);
M> if (l < j) quickSort (a, l, j);
M> if (i < r) quickSort (a, i, r);
M>}
M>
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен.
Это все потому что Вы умеете программировать на императивном языке, умеете работать с массивами и наработан опыт:
Взгляните на код — разгадываем ребус:
//от работы с элементами списка перешли к работе
// с индексами (хотя в описании алгоритма про индексы ни слова)int i = l; int j = r;
// да это же обмен значениями! ну и конечно очевидно,
// что вместе с обменом значениями передвигаются и указатели int temp = a[i]; a[i++] = a[j]; a[j--] = temp; на элементы (индексы)
// легко! поиск элемента (<x)while (a[i] < x) i++;
// легко! поиск элемента (>x) while (x < a[j]) j--;
// а точно! мы же просматриваем массив сразу с двух сторон,
// а это условие завершенияdo ... while (i <= j);
Это все у Вас происходит в голове.
M>Пример 3. Быстрая сортировка Хоара на языке Haskell. M>
M>quickSort [] = []
M>quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
M>
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Конечно, да!
Вы пытались разобраться в этом коде? Я попробую рассказать, как прочитать этот код, чтобы было понятно.
Изменим названия переменных немного, т.к. обычно в haskell краткие названия списков заканчиваются на s, так привычнее.
quickSort (x:xs) = quickSort [y | y <- xs, y < x] ++ [x] ++ quickSort [y | y <- xs, y >= x]
Рассмотрим определение функции "quickSort ps = ...", здесь описывается функция quickSort с одним параметром — списком. Чтобы получить голову списка мы можем использовать функцию head (например, head ps), а для получения хвоста списка можем использовать функцию tail (например, tail ps). А можем просто указать haskell, что мы хотим рассматривать данный параметр в виде пары (голова:хвост). Поэтому выражение "quickSort (x:xs) = ..." обозначает функцию quickSort с одним параметром (списком), голову которого назовем x, а хвост xs. Теперь нам не нужно писать в тексте head и tail для получения головы и хвоста, эти переменные у нас уже есть.
Выражение "... ++ ... ++ ..." обозначает соединение списков. Например [1,2] ++ [3,4] = [1,2,3,4]. Однако, мы не можем написать [1,2] ++ 3, т.к. "3" не является списком. Зато мы можем легко превратить число 3 в список содержащий число 3, заключив его в квадратные скобки — [3]. По этой причине у нас присутствует выражение "... ++ [x] ++ ...".
Еще есть у нас выражения вот такие: [y | y <- xs, y < x]. Общий вид их такой:
[ что_хотим_получить(элем1,элем2,..) | элем1 <- список1, элем2 <- список2, ..., условие1, условие2, ...]
Работает это так:
foreach(элем1:список1)
foreach(элем2:список2)
..
if (условие1 и условие2 и ...)
посчитать что_хотим_получить и включить это значение в результат
end
end
end
Т.е. для [y | y <- xs, y < x] можно просто сказать так: для всех y из xs, таких что y < x, вернуть y (не забываем, что х — голова параметра, xs — хвост). Для [y | y <- xs, y >= x] аналогично. Вообще-то эти выражения можно было бы записать и на основе функции filter: filter (<x) xs и filter (>=x) xs соответственно.
Все, что я описал выше никакого отношения к задаче фактически не имеет. Это принципы программирования на haskell. Например, pattern-matching, когда мы представляли параметр в виде (x:xs). И list comprehension [y | y <- xs, y < x]. Эти вещи изучаются один раз и через некоторое время при чтении на этом даже не заостряется внимание.
M>А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Толмач должен выглядеть так: Мы выделили один элемент из списка (x), а осташиеся элементы (xs) разделили на две группы (<x) и (>=x), каждую группу отсортировали и потом все это дело соединили.
Я бы вообще пример написал так:
Б> Т.е. для [y | y <- xs, y < x] можно просто сказать так: для всех y из xs, таких что y < x, вернуть y (не забываем, что х — голова параметра, xs — хвост).
Можно то представить в математической нотации:
{y | y ∈ xs, y < x}
То есть множество y, где y ∈ xs и y < x В общем, list comprehensions, в принципе, это и описывают
Здравствуйте, md03t4, Вы писали:
M>Вы согласны с тем, что пример на Haskell действительно лучше?
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Э!!! Ты привёл два разных алгоритма — разрушающий (на Си) и неразрушающий (на Хаскелле), и пытаешься их сравнивать на понятность.
Если для тебя этот факт ускользнул, то значит, что код на Си оказался кое в чём непонятен
Код на Си требует комментариев, и довольно тщательных.
В частности, там заинлайнен алгоритм разбиения массива (std::partition).
Хорошо известно из горького опыта, что написание таких очевидных вещей сопровождается детскими граблями — плюс-минус единичками на границах диапазонов, например.
void quickSort (int a[], int l, int r)
{
// Вопрос: мы работаем с полуоткрытым интервалом или с закрытым? [l..r) или [l..r] ?
// Ладно, обозначим правую границу загадочным }int i = l;
int j = r;
int x = a[(l + r) / 2];
// почему в роли медианы взяли значение из середины массива?
// при каких условиях здесь произойдёт вылет за границы?
// инвариант цикла: a[l..i} < x < [j..r}
// на каждой итерации диапазон [i..j} сужается
// постусловие - a[i..j} == x (причём очевидно, что этот интервал не пуст, ведь ему принадлежит медиана)do
{
while (a[i] < x) i++; // кажется, всё-таки работаем с закрытыми интерваламиwhile (x < a[j]) j--;
// замечательный сплав swap() и автоинкрементов, очень "интуитивно"if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j); // Зачем проверку диапазона делаем только после первой итерации? Она что, раньше нам не нужна?if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}
Чем обусловлен выбор закрытых интервалов, хотя бОльшая часть стандартных алгоритмов работает с полуоткрытыми?
Ну что, самодостаточен код, говоришь? Передай преподу из МИФИ, что он или халтурщик, или провокатор (в злом или добром смысле этого слова).
И ещё раз возвращаясь к алгоритмам на Си и Хаскелле.
Попробуй объяснить, почему на Си медиану дёрнули из середины массива, а на Хаскелле — из головы?
На что это влияет?
Если бы мы писали не на ленивом Хаскелле, а на энергичном ML, например — что изменилось бы?
Этюд для тестеров: сгенерировать такой массив, который обрушил бы сишный квиксорт в том виде, какой он есть у тебя.
Какая природа этого обрушения?
То же самое касается и Хаскелла.
Здравствуйте, eao197, Вы писали:
E>Оссмысленное название переменной y все еще подчеркивает мощность программиста на Haskell.
Это ирония?
1. Сравни области действия переменной i в С и переменной y в Haskell.
2. Сравнив, можно сделать вывод, что в некоторых случаях (а там именно такой)
удобнее написать f(x) = x*x
чем f(value) = value * value
Обзывать переменные цикла именами i и j имеет очень и очень давние корни. Которые можно наблюдать в высшей математике. Наверное, даже запись вида A0,A1,...,Ai,...,An уже демонстрирует убогость математического аппарата.
Б>1. Сравни области действия переменной i в С и переменной y в Haskell.
Это ирония?
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Это — классический пример, его где хочешь можно найти.
А сравнивать деструктивный алгоритм и недеструктивный, кстати, неумно.
Да и вариант на Хаскелле, хоть и проще для понимания, по скорости явно будет сливать. На каждом шагу два раза проходить один и тот же список и два раза делать ++. Мрак как "красиво".
Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
Здравствуйте, Rtveliashvili Denys, Вы писали: RD>Это — классический пример, его где хочешь можно найти.
Ага.
RD>А сравнивать деструктивный алгоритм и недеструктивный, кстати, неумно.
+1
RD>Да и вариант на Хаскелле, хоть и проще для понимания, по скорости явно будет сливать. На каждом шагу два раза проходить один и тот же список и два раза делать ++. Мрак как "красиво".
Таки не забывай что это учебный курс.
Стало быть приводятся примеры именно алгоритмов а не их оптимозированных реализаций.
Так что оба варианта вполне выполняют в данном контексте свои функции.
RD>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
Опять же посмотри "хороший" промышленный вариант быстрой сортировки на С/С++ в любой реализации STL-я. Сложность будет изрядно выше приведённой здесь реализации.
Здравствуйте, md03t4, Вы писали:
M>Текст ниже взят из лекций "Кафедра Кибернетики МИФИ: Функциональное программирование, группы К7-222 и К7-223. В настоящем варианте читаются с 2001 года.".
Текст ниже на самом деле практически без изменений выдран из FAQ конференции comp.lang.functional. Лекция МИФИ не является первоисточником.
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Конечно.
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен.
Человек, который не знает алгоритма quicksort, данный код будет расшифровывать достаточно долго, потому что в варианте на С записан не просто quicksort, а оптимизированный quicksort в варианте Хоара.
Вариант на Хаскеле как слышытся так и пишется — и он читается прямолинейно.
M>А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Обратите внимание, что смысл фразы "против этого нечего возразить; что правда, то правда" пояснять не надо, он самодостаточен, а для ее почти копии "dagegen ist nichts zu machen" требуется толмач.
Язык программирования надо все-таки изучать, чтобы понимать смысл программ, написанных на нем.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
RD>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
T>Докажиземлюешь.
Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности.
Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
T>>Докажиземлюешь.
RD>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности.
RD>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Этот вариант, в целом, не надо оптимизировать. Из-за ленивых вычислений он гораздо оптималенее, чем кажется на первый вгляд (выполняется он _совсем_ не так, как кажется на первый взгляд, например, операция ++ дается почти бесплатно, а вовсе не стоит O(N)) и вычисляется с разумной производительностью.
Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.