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

Ответ 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, потому что я думаю, что это проще всего читать, если вы знаете какой-либо другой общий императивный язык.

Ответ 2

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

• Quicksort
• Сортировка вставки
• Merge sort
• Сортировка сортировки
• Сортировка сортировки

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

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

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

Ответ 3

Здесь классическая (псевдо-?) quicksort в Haskell:

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

См., например, c2.com или LiteratePrograms.org. Merge sort не намного сложнее писать и более надежно на практике. То же самое можно сделать на схеме с помощью:

(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.

Ответ 4

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

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