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

Question

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

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 

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

Спасибо!

* (На самом деле рекурсии, но безотносительно)

Answer 1

От EigenClass:

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

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

Edit: Со ссылкой на Xavier Leroy, первичный разработчик OCaml

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

Answer 2

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

Попробуйте реализовать mergesort в 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)