Haskell, алгоритмы и школа

Question

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

Чтобы получить некоторые линии Haskell под моим поясом, я начал пытаться реализовать некоторые простые альгосы. Во-первых: Гейл-Шепли для проблемы стабильного брака. Еще не получив монады, все это изменчивое состояние выглядит пугающе, поэтому вместо этого я использовал характеристику стабильных сопоставлений как фиксированных точек отображения на решетке полусогласий. Это было весело, но его уже не Gale-Shapley и сложность не очень приятная (эти цепочки в решетке могут быть довольно длинными, очевидно :)

Далее у меня есть алгоритм для Ближайшей пары точек в плоскости, но я застрял в получении обычной сложности O (n * log n), потому что не могу понять, как получить подобную набору данных структуру с проверкой O (1) для членства.

Так что мой вопрос: может ли вообще реализовать большинство алгоритмов, например. Дейкстра, Форд-Фулкерсон (Gale-Shapley!?), Получая сложности от процедурных реализаций, если лучше получить команду Haskell и функциональное программирование вообще?

Answer 1

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

Хорошее место для начала, если вы хотите понять, как обращаться к алгоритмам в этой настройке, книга Криса Окасаки Purely Functional Data Structures. Книга представляет собой расширенную версию его диссертации, которая составляет available online in PDF format.

Если вы хотите получить помощь по конкретным алгоритмам, таким как проверка членства O (1) (что фактически вводит в заблуждение - нет такой вещи, такие структуры данных обычно имеют нечто вроде O (k), где k - размер элементы, которые хранятся), вам лучше спросить об этом как о конкретном, единственном вопросе, а не о таком общем вопросе.

Answer 2

Поскольку у вас есть монада ST в Haskell, вы можете делать все с изменчивым состоянием с той же скоростью императивного языка. Внешне он может иметь неравномерный интерфейс. Смотри, например, Launchbury и Пейтон-Джонс: «Ленивая функциональное состояние нить» http://portal.acm.org/citation.cfm?id=178246

Answer 3

Existence proof для реализации алгоритмов с изменяемыми структурами данных. Просто повторите запись IO. В этом случае запись игры, в которой содержатся соответствующие переменные.