Функциональная альтернатива?

Question

Продолжая поиски функционального программирования, я пришел Интересно, могут ли быть альтернативы моему «процедурному» пути по умолчанию? мышления. Чтобы быть более конкретным, я смотрю на функцию, которую я написал. Вот что он делает:

Swap two elements of an unordered list of numbers, such that one of the elements  
 is now in the right place
Add the sum of the swapped values to an accumulated total   
Repeat until list is sorted

Итак, сейчас я использую стандартный цикл * с переменной AC выше. Работает нормально и все, и в этом нет ничего плохого с итерацией в реальной жизни, но как цель этого упражнения заключается в расширить свой образ мыслей, мне интересно, если есть более функциональный Подход к вышеуказанному алгоритму.

Спасибо!

* (На самом деле рекурсия, но что угодно)

Answer 1

С EigenClass :

Почтенный мастер Лерой гулял со своим учеником. Желая начать обсуждение со своим учителем, ученик сказал: «Учитель, я слышал, что все циклы должны быть заменены хвостово-рекурсивными функциями. Это правда?» Лерой с сочувствием посмотрел на своего ученика и ответил: «Глупый ученик, многие хвостовые рекурсивные функции - просто неэффективные циклы».

Студент провел следующие несколько недель, заменяя хвостовые рекурсивные функции явными циклами. Наконец он показал свой код мастеру Леруа, ища его одобрения. Лерой ударил его палкой. «Когда ты научишься? Явные циклы - это хвостовые рекурсивные функции бедняков». В этот момент ученик стал просветленным.

Редактировать: Ссылаясь на Ксавье Лерой, основной разработчик OCaml

Поскольку я не могу увидеть вашу функцию, чтобы понять, насколько она функциональна *, я не знаю. Но похоже, что вы делаете правильно. Моим основным предложением было бы взглянуть на структуры данных, которые хорошо подходят для функционального программирования - но вы используете списки, так что это не так, хотя списки - не лучшая структура данных в этом случае. Как и алгоритм. Если вы используете голубую сортировку, то вы не сможете использовать сортировку слиянием или другие более эффективные методы.

Answer 2

Рекурсия - это в основном механизм функционального программирования. Я полагаю, вы могли бы заменить свою функцию подкачки на функцию, которая принимает список и возвращает список или что-то в этом роде глупо, но это было бы плохой идеей, если бы она не была написана на языке, который был действительно функциональным.

Попробуйте реализовать сортировку слиянием в Oz, SML, Prolog или Lisp. Например. что-то вроде этого псевдокода для слияния:

Merge(A,[])=A
Merge(H|T,H2|T2)=iif(H<H2,H|Merge(T,H2|T2),H2|Merge(H|T,T2)