Интересно, как реализовать быстрые сортировки (O(N log N)) массивов (списков) на функциональном языке программирования?

Немного знаком с Scheme, и признаюсь, не совсем понимаю как это сделать...

Ответ на »сообщение 2113« (Сергей Перовский)
___________________________
Я полагаю императивщиков сбивает с толку скрытое управление состоянием, которое возможно в ФЯ.
Они все тыкаются и ищут где же эти переменные в которые записывается промежуточный результат :))
Возьмем тот простенький интерактивный пример с мышкой и бегающим за ним квадратиком, который вы можете посмотреть по ссылке, который я только что привел.
Там в исходниках видно что координаты квадратика задаются как формула от координат мышки.
Но где хранятся координаты мышки ? кто их обновляет ? Кто дергает функцию чтобы пересчиталась ?
Ничего этого нет, все за сценой, все под капотом.
Конечно, существует и состояние, и переменные в которые промежуточное, то есть текущее состояние записывается, Конечно пересчитывать все с самого начала не надо, и ЯВНО в функцию весь огромный мир состояния каждый раз передавать не надо.
Все это для вас делает виртуальная машина, система функционального программирования, в которой живут ваши программы-функции.

В случае с программой бильярдом будет точно также как и в случае с мышкой, которую мы двигаем.
Состояние все время меняется, но функции, которые выполняют работу (двигают квадратик вслед за мышкой, или передвигают бильярдные шары как реакцию на удар) остаются чистыми, потому что за сценой, система постоянно передает им внутрь НОВЫЕ данные и дергая их для пересчета.
Сам программист этим не занимается. Он только задает взаимосвязи, и указывает точки входа (движение мышки, или нажатие кнопки "Удар")

Ответ на »сообщение 2113« (Сергей Перовский)
___________________________
Кстати Сергей, я ведь только что дал вам ссskre на http://www.flapjax-lang.org/
Ведь там даже не надо ничего скачивать. Все прямо в браузере работает, в javascript.

Там примеры с исходниками. Например двигаете курсор мышки, и черный квадратик бегает за курсором.
Следующий пример, тот же квадратик бегает за курсором с запаздыванием, то есть повторяет его траекторию.
Вот вам интерактивность, дальше некуда просто.
Ну хорошо, об ФЯ руки пачкать вы не будете, скачивать что то инсталировать, книжки читать. все это вы не будете.
Но черт возьми! Кликнуть на ссылку и просто ПОСМОТРЕТЬ, вы хоть можете ?

Ответ на »сообщение 2113« (Сергей Перовский)
___________________________
Состояние системы это список шаров и их координат.
Вы передаете функции список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
...
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
...
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
Функция возвращает вам НОВЫЙ список шаров с новыми координатами.
Вы вызываете эту же функцию ЕЩЕ раз передавая ей НОВЫЙ список шаров, номер шара, угол удара, силу удара.
...

Ответ на »сообщение 2112« (Jack Of Shadows)
___________________________
>>>Передавая функции параметры и получая результат разве вы не "интерактируете" с ней ? :))
Видите ли Jack, мы, ущербные императивщики, знаем два различных способа взаимодействия. Кроме упомянутого Вами прямого вызова функций, используется так-же обмен сообщениями. Мы уже давно интуитивно понимаем, в каких случаях удобно использовать вызовы функций, а в каких лучше пользоваться сообщениями. Например, если взаимодействие "один к многим", сообщения позволяют описать его заметно проще.
Давайте смоделируем относительно простой случай - игру в бильярд. Может быть Вам и удастся построить функцию, которая вычисляла бы конечное положение всех шаров по их положению до первого удара. Но допустим программа только предоставляет модель, а играют два человека, вводя номер шара, угол и силу удара. Как строить такую программу на основе функционального подхода мне не ясно. Поделитесь соображениями.

Ответ на »сообщение 2107« (Сергей Перовский)
___________________________

Проблемы у ФП возникают только когда задача существенно интерактивная.


Вот the heck does that mean ?
Передавая функции параметры и получая результат разве вы не "интерактируете" с ней ? :))

Я уже приводил примеры cell подобных библиотек которые позволяют взаимодействовать с пользователем в чисто функциональном стиле, безо всяких присваиваний и сохранений промежуточных результатов.
В хаскеле подобный подход называется FRP - functional reactional programming.

И пример который вы сами можете пощупать:
http://www.flapjax-lang.org/

javascript библиотека, с компилятором, написанным на хаскеле.
На сайте есть множество примеров с очень простыми (одна, две строчки) примерами, причем работающие прямо в в вашем браузере.

Посмотрите там на интерактивность. Включая и работу с мышкой.

Далее, подобный же подход например взят в набирающей популярность flash cреде Flex, кстати с самым обычным императивным ОО язком ActionScript (похож на javascript)

Посмотрите вот здесь http://examples.adobe.com/flex2/inproduct/sdk/explorer/explorer.html
Там примеры ВИЗУАЛЬНЫХ GUI компонент flex, где вся интерактивность написана при помощи взаимосвязей, без прямого сохранения результата в какие то переменные.

Я уже много раз говорил вам, что все эти "невозможно или трудно в ФЯ" существуют только у вас в голове, просто потому что по другому то вы и представить себе не можете.

Однако времена меняются. И точно также как индустрия в свое время перешла от консольных приложений к графическим GUI, так и сейчас происходит массовый переход от тяжелых в создании императивных GUI на декларативные.
Кстати и Sun в этом замечена: F3 - декларативный язык специально созданный для создания Swing GUI

Ответ на »сообщение 2109« (Сергей Перовский)
___________________________

Чем дальше мы обсуждаем модульное, объектное и функциональное программирование, тем больше мне кажется неразумным противопоставление этих подходов. Они относятся к разным уровням представления программной системы.

Так мы вроде бы не противопоставляем, а сопоставляем. Есть разница. И цель -- выявить границы применимости, а также плюсы и минусы парадигм. Честно говоря, у меня складывается ощущение, что мы еще находимся в самом начале пути. Вопрос на самом деле сложный и серьезный. Во многом "контекстно-зависимый" (от нюансов задачи и особенностей проекта).

Я не ставлю перед собой цель во что бы то ни стало отстоять модульное программирование (МП). Уже прогресс, что для тех, кто интересуется Обероном, в ходе обсуждения проявились плюсы МП (а не просто ООП-имитации).

Но с самими модулями и их использованием как в ФП, так и в ООП, по-моему еще большой туман. Как использовать ООП (классы) в МП на примере Оберонов мы прекрасно видели. Как там использовать ФП уже почти догадываемся. А вот каковы подводные камни ФП и ООП с включением полноценного МП не очень понятно.

Что касается разных уровней, то позвольте не согласиться. Я бы говорил скорее о разных аспектах (взглядах), но не уровнях.

Ответ на »сообщение 2109« (Сергей Перовский)
___________________________

Вы, видимо, очень узко понимаете интерактивность. Часто необходимо, чтобы программы, модули или объекты взаимодействовали с человеком, аппаратурой или между собой в процессе работы. GUI тут только наиболее ходовой пример.

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

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

Аналогично. :)
По крайней мере, пока я думаю так же.
Такое мнение у меня давно, как минимум -- со времен чтения книги Шлаер и Меллора.

Чем дальше мы обсуждаем модульное, объектное и функциональное программирование, тем больше мне кажется неразумным противопоставление этих подходов. Они относятся к разным уровням представления программной системы.

Похоже на правду.
Единственное, Руслан Богатырев все время пытается донести мысль, что далеко не все языки внятно поддерживают модульное программирование.

Ответ на »сообщение 2108« (AVC)
___________________________
>>>Сергей, можно ли Вас понять так, что Ваши задачи, если отвлечься от GUI, а сосредоточиться на предметной области, хорошо "лягут" на ФП?
Вы, видимо, очень узко понимаете интерактивность. Часто необходимо, чтобы программы, модули или объекты взаимодействовали с человеком, аппаратурой или между собой в процессе работы. GUI тут только наиболее ходовой пример.
Получается, что хорошо ложится на ФП самый нижний слой алгоритмов, я и стараюсь использовать функциональный подход вместо процедурного. Но там, где приходится описывать взаимодействие, я не вижу эффективного способа использования ФП.
Чем дальше мы обсуждаем модульное, объектное и функциональное программирование, тем больше мне кажется неразумным противопоставление этих подходов. Они относятся к разным уровням представления программной системы.

Ответ на »сообщение 2107« (Сергей Перовский)
___________________________

Ответ на »сообщение 2101« (Jack Of Shadows)
___________________________
>>>Что опять таки утверждает меня в моем мнении что разреши в соревнованиях хаскель, окамл, лисп - и о гегемонии ИЯ на соревнованиях можно забыть.
Полностью согласен, поскольку это соревнования на написание функций.
Проблемы у ФП возникают только когда задача существенно интерактивная.

Сергей, можно ли Вас понять так, что Ваши задачи, если отвлечься от GUI, а сосредоточиться на предметной области, хорошо "лягут" на ФП?