Декларативное мышление

Блин! Опять быстрая сортировка! Вы рискуете распугать тех, кто действительно заинтересован декларативным подходом и призвать троллей. Это, увы, не самый лучший пример. Дело в том, что хоаровский вариант реально быстр и сортирует на месте. Рекурсивный же только записывается красиво, но хоаровским, увы, не является. Это разные алгоритмы с разными свойствами. Об этом уже много раз писали на разных языках, статьи легко гуглятся. Главный аргумент троллей: евангелисты-декларативщики опять и опять приводят два-три примера неработающих алгоритмов! В хаскеллевском Data.List используется mergesort, поскольку сам по себе quicksort непрактичен и в функциональной реализации жаден до памяти. Декларативный подход серьезно играет в большем: в построении реактивных систем, в алгебраическом описании сложных архитектур, в принципиальной доказуемости декларативных утверждений. Я понимаю и полностью разделяю восхищение, испытываемое при первом знакомстве с ленивым "решетом Эратосфена" на Хаскеле (которое тоже вовсе не оно), или тем же рекурсивным quicksort, но прошу: не останавливайтесь на этом! Мы не должны выглядеть евангелистами с одними и теми же простыми притчами, у функционального и логического программирования есть гораздо больше классных результатов. Правда, они сложнее . А главное: не противопоставляйте парадигмы. Это мешает искусству владения ими всеми.

Может и правда хватит изучать императивные языки, а что для вас более привлекательно?

Мы как путешественники по своим мыслям, и анализаторы своего состояния, должны понимать где хорошо, а где иначе, где же именно мы находимся, вот к этому хочу привлечь внимание читателей.

Чтобы понимать, где хорошо, а где иначе, полезно бы уметь выражать свои мысли.

Как мы складываем цепочки мыслей,

По-разному. А вам это не очевидно?

выражать все последовательностью команд и переходов между ними, мне кажется архаичным и устаревшим

Рецепты вам тоже кажутся "архаичными и устаревшими"?

Мне кажется, если выражать программу логическим языком, она будет выглядеть понятнее

Вам кажется. Программы бывают разные, и для разных программ удобнее разные способы выражения.

При небольшой разнице в производительности

На глаз — qsort всего процентов на пятьдесят дольше выполняется. Совершенно небольшая разница. Незначительная.

Не буду сейчас щурить глаза и смотреть в нюансы реализаций квиксорта.
Тем более, что квиксорт на цепочках и квиксорт на массивах — это два разных квиксорта, как уже верно заметили товарищи.

===Мысль вслух.===

Декларативность может идти в разных направлениях:

1) Контрактное программирование.
Мы расписываем все предусловия, инварианты, постусловия до самых мелочей, — и вуаля, если у нас последнее постусловие — "набор состоит из тех же элементов, что были на входе, и упорядочен", — мы описали сортировку. Плюс, конечно, мы должны расписать проблему остановки, а потом напихать эвристик для выбора более-менее эффективной стратегии среди прочих равновозможных.

2) Наглядное программирование.
Мы декомпозируем задачу на детальки, каждая из которых очевидным образом решает свою подзадачу, — получаем самодокументируемый код.
Сводим к минимуму залезание в чужие зоны ответственности, — именно это ставится в упрёк императивному программированию, где практикуется переприсваивание значений, и пойди отследи кто что когда.

Иммутабельность — это не самоцель, а полезная фишечка. Так-то мы спокойно можем рассмотреть изменяемый массив как некую функцию от времени на массивы: в каждый отсчёт времени (после каждой правки) — новый массив.
А если потом завернём в какую нибудь идеологию CPS и/или STM, — получим мутабельность поверх иммутабельности (или просто мутабельность, но с битьём по пальцам при желании вспомнить ушедшее былое).

===Мысль вслух.===

Когда люди берут лучшие (а точнее, единственно доступные) практики программирования на лиспе и прологе, где циклы — это рекурсия, а концевая рекурсия — это избавление от всех бед,
и переносят слово в слово на языки с достаточно дорогой рекурсией (например, на питон), — получается фигня.

В этом нет никакой декларативности! Декларативно было бы — "здесь мы выполняем одну операцию над набором данных в цикле!", вот операция, вот набор, давай-мапь-редюсь!

У квиксорта есть две большие беды.

Первое: честная рекурсия, в силу того, что задача разбивается на две подзадачи. И если один из вызовов мы можем вывернуть мясом наружу и превратить в концевую рекурсию, то второй-то уж точно никак. Тут нам пригодится эвристика, говорящая о том, что — давайте будем проваливаться в более короткую подзадачу, а более длинную оставлять на десерт.

Второе: при неудачном стечении обстоятельств декомпозиция вырождается в линейную. Соответственно, N памяти (если только мы не исхитримся с концевыми рекурсиями) и N**2 времени.
Тут нам пригодится другая эвристика, говорящая следующее: нам, в общем-то, пофиг, как именно будут отсортированы подмассивы.

Код на псевдо-эрланге, не тестировал, не обессудьте. Чисто пруф оф концепт.

qsort([]) -> [];
qsort(Xs) ->
  {Ls, X, Rs} = partition(Xs),
  qsort(Ls) ++ [X] ++ qsort(Rs).

% переделаем на концевую

sort(Xs) -> qsort_tail([], Xs).  % голова - упорядочена и меньше хвоста

qsort_tail(Hs, []) -> Hs;
qsort_tail(Hs, [X]) -> Hs ++ [X];
qsort_tail(Hs, Xs) ->
  {Ls, X, Rs} = partition(Xs),
  qsort_tail(Hs ++ sort(Ls) ++ [X], Rs).

% переделаем на концевую с эвристикой - куда лучше сваливаться

sort(Xs) -> qsort_tail([], Xs, []). % голова и хвост упорядочены и меньше-больше середины

qsort_tail(Hs, [], Ts) -> Hs ++ Ts;
qsort_tail(Hs, [X], Ts) -> Hs ++ [X] ++ Ts;
qsort_tail(Hs, Xs, Ts) ->
  {Ls, X, Rs} = partition(Xs),
  if length(Ls) < length(Rs) ->
    qsort_tail(Hs ++ sort(Ls) ++ [X], Rs, Ts);
  true ->
    qsort_tail(Hs, Ls, [X] ++ sort(Rs) ++ Ts)
  end.

% напишем сортировку более тупую, но гарантирующую логлинейное время
heapsort(Xs) -> sort_heap(make_heap(Xs)).

% и более медленную (квадратичную) на больших наборах, но стремительную на маленьких
introsort(Xs) -> ?????. % лень выдумывать

sort(Xs) -> sort(Xs, 0).

sort(Xs, Depth) when length(Xs) < ThresholdOfIntrosort -> introsort(Xs);
sort(Xs, Depth) when Depth > ThresholdOfRecursion -> heapsort(Xs);
sort(Xs, Depth) -> qsort_tail([], Xs, [], Depth+1).

Примерно так работает std::sort в реализациях C++ для современных компиляторов — gcc, clang, VS. Ну, только с той разницей, что там всё inplace.

Кстати! Вы можете сказать: "зачем ты делаешь [X] ++ Ts, это же неэффективно? Почему не [X|Ts]?"
Да, неэффективно по скорости. Хотя и единообразно.
Но мы ведь можем сформулировать задачу сортировки так:

• разбить массив на кучу внутренне упорядоченных и взаимно упорядоченных массивов
• а потом склеить их одним махом

sort(Xs) -> flatten(sorted(Xs)).
sorted(Xs) -> qsort_tail([], Xs, []).

qsort_tail(Hs, [], Ts) -> [Hs, [], Ts];
qsort_tail(Hs, Xs, Ts) ->
  {Ls,X,Rs} = partition(Xs),
  if length(Ls) < length(Rs) ->
    qsort_tail( [Hs, sorted(Ls), [X]], Rs, Ts );
  true ->
    qsort_tail( Hs, Ls, [[X], sorted(Rs), Ts] ).

(вот это — вообще пруф оф концепт, тут я специально оставил за кадром ряд возникающих проблем, которые мне лень решать на псевдоэрланге)