Читая блог Вада, заметил, что его в последнее время тянет на функциональный подход и Haskell. Возможно потому, что этот подход ближе к чистой математике, нежели к жутким реалиями разных сырых SDK. Так сказать, горний мир и пища духовная для программиста и прикладного математика
Посему ставлю вопрос ребром.
В лямбда-исчислении Чёрча любая функция от N аргументов разлагается на композицию функционалов. Т.е., например, f(x, y) = (g(x))(y), где g - не функция, а функционал - т.е. такое особое выражение, результатом вычисления которого является функция или другой функционал (как, например, неопределённые римановы интегралы в математике).
В связи с этим возникают широкие возможности для организации ленивых вычислений. Общая суть подхода сводится к тому, чтобы в некоторой точке древовидного вычислительного процесса наметить ответвление, но не углубляться в эту ветвь до тех пор, пока не потребуется результат её исполнения. Чем-то это похоже на шаблоны C++ и generic-типы в других языках, только они обрабатываются компилятором, а в функциональных языках такие подстановки происходят прямо во время исполнения.
Возьмём простую задачу поиска минимума в списке чисел.
Алгоритмический подход в лоб известен, думаю, всем (а те, кому он не известен, уже закрыли эту тему, придя в полное уныние от предыдущих абзацев) - это перебор списка с запоминанием лучшего решения из уже перебранной части.
const N = 100;
type
ArrayRangeType = 1..N;
ArrayItemType = Real;
ArrayType = array [ArrayRangeType] of ArrayItemType;
function Min(a: ArrayType): ArrayItemType;
var
i: Integer;
result: ArrayItemType;
begin
result := High(ArrayItemType);
for i := Low(ArrayRangeType) to High(ArrayRangeType) do
if a[i] < result then
result := a[i];
Min := result;
end;
Другой подход (кстати, будто бы упомивашийся у кого-то из классиков - то ли Кнута, то ли Дейкстры) связан с богатством средств языка. Т.е. если в языке есть встроенная сортировка, то гораздо компактнее (но зато хуже по объёму вычислений) использовать её:
function min(array)
{
if(array instanceof Array && array.length > 0)
return array.sort()[0];
else
return NaN;
}
Второй вариант более близок к идеям функционального подхода, но нет предела совершенству.
Без сортировки просто найти минимум достаточно просто через рекурсию:
(defun mmin(l) (if l ((lambda(h t) (if t ((lambda(x y) (if (< x y) x y)) head (mmin t)) h)) (car l) (cdr l)) nil))
(Чёрт, совсем забыл, как можно внятно форматировать код на Lisp
.)
Вопрос: можно ли тот же алгоритм быстрой сортировки Хоара таким образом представить в виде композции функционалов и функций, чтобы избавиться от
последовательности операций: сортировка списка, взятия i-го элемента. Т.е. составить такую функцию от двух аргументов: списка и номера элемента в списке f(a, i), которая бы обеспечивала возврат i-го в порядке возрастания элемента списка, при этом рассматривая сортировку не как операцию над всем списком, а как операцию доступа к элементу списка, возможно, выполняясь частично - лишь по мере необходимости доступа к i-му элементу?
