Сортировка по функциональным языкам программирования

Question

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

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

Спасибо.

Answer 1

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

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

def merge(a, b):
    if len(a) == 0:
        return b
    elif len(b) == 0:
        return a
    elif a[0] < b[0]:
        return [a[0]] + merge(a[1:], b)
    else:
        return [b[0]] + merge(a, b[1:])

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

def mergesort(x):
    if len(x) < 2:
        return x
    else:
        h = len(x) // 2
        return merge(mergesort(x[:h]), mergesort(x[h:]))

О синтаксисе Python:

• L[0] - первый элемент списка L
• L[1:] - список всех оставшихся элементов
• В более общем смысле L[:n] - это список до n-го элемента, L[n:], остальные
• A + B, если A и B оба списка, это список, полученный путем объединения
• [x] - список, содержащий только один элемент x

PS: обратите внимание, что приведенный выше код на Python просто показывает концепцию ... в Python это НЕ разумный подход. Я использовал Python, потому что думаю, что его легче всего читать, если вы знаете какой-либо другой распространенный императивный язык.

Answer 2

Вот несколько ссылок на алгоритмы сортировки, реализованные в Haskell:

• Быстрая сортировка
• Вставка сортировки
• Сортировка слиянием
• Сортировка выбора
• Подсчет сортировки

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

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

С другой стороны, сортировка слиянием хорошо работает со связанными списками, и можно реализовать алгоритм таким образом, что он требует только некоторой константы дополнительного пространства со связанными списками.

Answer 3

Вот классическая ( псевдо -? ) быстрая сортировка в Haskell:

sort []      =   []
sort (p:xs)  =   sort [x | x<- xs, x <= p]
              ++ [p]
              ++ sort [x | x <- xs, x > p]

См., Например, c2.com или LiteratePrograms.org. Сортировка слиянием не намного сложнее в написании и более надежна на практике.То же самое можно сделать в схеме с:

(define (sort xs)
  (if (null? xs)
    '()
    (let* ((p (car xs)) (xs (cdr xs)))
      (call-with-values (lambda () (partition (lambda (x) (<= x p)) xs))
                        (lambda (l r)
                          (append (sort l) (list p) (sort r)))))))

с partition из SRFI-1 (непроверенный код).См. Также главу 4 библиотек R6RS .

Answer 4

Вы, безусловно, можете реализовать императивные алгоритмы сортировки с побочными эффектами на функциональных языках.

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