Sorting in functional programming languages

I've been learning functional programming for some time, but I haven't read somewhere about sorting with the functional programming languages.

I know 开发者_如何转开发the sorting algorithms that are based on value exchanges are hard to implement with the functional idea, but I want to know that are there any sorting algorithms for use in functional programming? What are they?

Thank you.

In a functional language you write a function that given a list returns a sorted list, not touching (of course) the input.

Consider for example merge sorting... first you write a function that given two already sorted lists returns a single sorted list with the elements of both in it. For example:

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:])

then you can write a function that sorts a list by merging the resulting of sorting first and second half of the list.

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

About Python syntax:

• L[0] is the first element of list L
• L[1:] is the list of all remaining elements
• More generally L[:n] is the list of up to the n-th element, L[n:] the rest
• A + B if A and B are both lists is the list obtained by concatenation
• [x] is a list containing just the single element x

PS: Note that python code above is just to show the concept... in Python this is NOT a reasonable approach. I used Python because I think it's the easiest to read if you know any other common imperative language.

Here are some links to sorting algorithms implemented in Haskell:

• Quicksort
• Insertion sort
• Merge sort
• Selection sort
• Counting sort

Merge sort is often the best choice for sorting linked lists. Functional languages usually operates on lists although I have little knowledge on how most functional languages implements lists. In Common Lisp they are implemented as linked lists and I presume most functional languages do as well.

While quicksort can be written for linked lists it will suffer from poor pivot selection because of random access. While this does not matter on completely random input, on partially or completely sorted input pivot selection becomes very important. Other sorting algorithms may also suffer from the slow random-access performance of linked lists.

Merge sort on the other hand works well with linked lists and it is possible to implement the algorithm such that it only requires some constant of extra space with linked lists.

Here's the classic (pseudo-?)quicksort in Haskell:

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

See, e.g., c2.com or LiteratePrograms.org. Merge sort isn't much harder to write and more reliable in practice. The same can be done in Scheme with:

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

with partition from SRFI-1 (untested code). See also chapter 4 of R6RS libraries.

You certainly can implement imperative, side-effecting sort algorithms in functional languages.

I've implemented a sorting algorithm that operates in-place in a functional programming language called ATS; all mutation is handled by linear types. If you're interested in this kind of thing, drop me a line.

I'm probably raising this question from the grave but I think a global comparison approach might be useful to some people (in case we're not sorting numbers for example). Here is a TypeScript version using ES6:

TL;DR

type Comparator<T> = (itemA: T, itemB: T) => number;

const mergeSort = <T>(list: T[], compare: Comparator<T>): T[] => {
  if (list.length <= 1) return list;
  const middleIndex = Math.floor(list.length / 2);
  const listA = mergeSort(list.slice(0, middleIndex), compare);
  const listB = mergeSort(list.slice(middleIndex), compare);
  return merge(listA, listB, compare);
};

const merge = <T>(listA: T[], listB: T[], compare: Comparator<T>): T[] => {
  if (listA.length === 0) return listB;
  if (listB.length === 0) return listA;
  return compare(listA[0], listB[0]) <= 0
    ? [listA[0], ...merge(listA.slice(1), listB, compare)]
    : [listB[0], ...merge(listA, listB.slice(1), compare)];
};

Explaination

We can pass an extra compare function to the mergeSort function now. This compare function has the same definition as in JavaScript's Array.prototype.sort() method's parameter.

For instance, the number comparator would be:

const compareNumbers: Comparator<number> = (numberA, numberB) =>
  numberA - numberB;

...while a User object comparator could be:

const compareUsersByAge: Comparator<User> = (userA, userB) =>
  userA.age - userB.age;

...or anything more complicated if need be (e.g. string comparison).