sorting - segun - Clasificación en lenguajes de programación funcionales.

orientacion de lenguajes de programacion

Question

He estado aprendiendo programación funcional por algún tiempo, pero no he leído en algún lugar sobre cómo ordenar con los lenguajes de programación funcionales.

Sé que los algoritmos de clasificación que se basan en el intercambio de valores son difíciles de implementar con la idea funcional, pero quiero saber si hay algoritmos de clasificación para usar en programación funcional. ¿Qué son?

Gracias.

Answer 1

Aquí está el clásico ( pseudo-? ) Quicksort en Haskell:

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

Ver, por ejemplo, c2.com o LiteratePrograms.org . La clasificación por fusión no es mucho más difícil de escribir y más confiable en la práctica. Lo mismo se puede hacer en Esquema con:

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

con partition de SRFI-1 (código no probado). Véase también el capítulo 4 de las bibliotecas R6RS .

Answer 2

Aquí hay algunos enlaces a algoritmos de clasificación implementados en Haskell:

• Quicksort
• Tipo de inserción
• Fusionar orden
• Selección de selección
• Contando orden

La clasificación por fusión suele ser la mejor opción para ordenar las listas vinculadas. Los lenguajes funcionales generalmente operan en listas, aunque tengo poco conocimiento de cómo la mayoría de los lenguajes funcionales implementa las listas. En Common Lisp se implementan como listas enlazadas y supongo que la mayoría de los lenguajes funcionales también lo hacen.

Si bien Quicksort puede escribirse para listas vinculadas, sufrirá una mala selección de pivote debido al acceso aleatorio. Si bien esto no importa en una entrada completamente aleatoria, en una selección de pivote de entrada ordenada parcial o completamente se vuelve muy importante. Otros algoritmos de clasificación también pueden verse afectados por el lento rendimiento de acceso aleatorio de las listas vinculadas.

La clasificación de fusión por otro lado funciona bien con listas vinculadas y es posible implementar el algoritmo de modo que solo requiera una constante de espacio extra con listas vinculadas.

Answer 3

Ciertamente puede implementar algoritmos de ordenamiento imperativo y de efectos secundarios en lenguajes funcionales.

He implementado un algoritmo de clasificación que opera en el lugar en un lenguaje de programación funcional llamado ATS; Todas las mutaciones son manejadas por tipos lineales. Si estás interesado en este tipo de cosas, escríbeme.

Answer 4

En un lenguaje funcional, usted escribe una función que, dada una lista, devuelve una lista ordenada, sin tocar (por supuesto) la entrada.

Considere, por ejemplo, combinar clasificación ... primero, escriba una función que, dadas dos listas ya ordenadas, devuelva una sola lista ordenada con los elementos de ambas en ella. Por ejemplo:

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

luego, puede escribir una función que ordene una lista combinando el resultado de clasificar la primera y la segunda mitad de la lista.

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

Acerca de la sintaxis de Python:

• L[0] es el primer elemento de la lista L
• L[1:] es la lista de todos los elementos restantes
• Más generalmente, L[:n] es la lista de hasta el elemento n-ésimo, L[n:] el resto
• A + B si A y B son ambas listas es la lista obtenida por concatenación
• [x] es una lista que contiene solo el elemento x

PD: Tenga en cuenta que el código de Python anterior es solo para mostrar el concepto ... en Python NO es un enfoque razonable. Usé Python porque creo que es lo más fácil de leer si conoces cualquier otro lenguaje imperativo común.