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

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

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

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

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

Ответы

Ответ 1

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

Хорошее место для начала, если вы хотите понять, как обращаться к алгоритмам в этой настройке, - это книга Chas Okasaki чисто функциональные структуры данных. Книга представляет собой расширенную версию его диссертации, которая доступна в Интернете в формате PDF.

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

Ответ 2

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

Ответ 3

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