Este artículo describe las características del lenguaje de programación Haskell .
Un ejemplo sencillo que se utiliza a menudo para demostrar la sintaxis de los lenguajes funcionales es la función factorial para números enteros no negativos, que se muestra en Haskell:
factorial :: Entero -> Entero factorial 0 = 1 factorial n = n * factorial ( n - 1 ) O en una línea:
factorial n = si n > 1 entonces n * factorial ( n - 1 ) más 1 Esto describe el factorial como una función recursiva, con un caso base terminal. Es similar a las descripciones de factoriales que se encuentran en los libros de texto de matemáticas. Gran parte del código de Haskell es similar a la notación matemática estándar en cuanto a facilidad y sintaxis.
La primera línea de la función factorial describe el tipo de esta función; si bien es opcional, se considera de buen estilo [1] incluirlo. Se puede leer como la función factorial ( factorial) tiene tipo ( ::) de entero a entero ( Integer -> Integer). Es decir, toma un número entero como argumento y devuelve otro número entero. El tipo de definición se infiere automáticamente si no se proporciona ninguna anotación de tipo.
La segunda línea se basa en la coincidencia de patrones , una característica importante de Haskell. Tenga en cuenta que los parámetros de una función no están entre paréntesis sino separados por espacios. Cuando el argumento de la función es 0 (cero), devolverá el número entero 1 (uno). Para todos los demás casos se prueba la tercera línea. Esta es la recursividad y ejecuta la función nuevamente hasta alcanzar el caso base.
Usando la productfunción del Preludio, una serie de pequeñas funciones análogas a la biblioteca estándar de C , y usando la sintaxis de Haskell para secuencias aritméticas, la función factorial se puede expresar en Haskell de la siguiente manera:
factorial n = producto [ 1 .. n ] Aquí [1..n]denota la secuencia aritmética 1, 2,…, n en forma de lista. Usando la función Preludio enumFromTo, la expresión [1..n]se puede escribir como enumFromTo 1 n, permitiendo que la función factorial se exprese como
factorial n = producto ( enumFromTo 1 n ) que, utilizando el operador de composición de funciones (expresado como un punto en Haskell) para componer la función del producto con la función de enumeración al curry, se puede reescribir en un estilo sin puntos : [2]
factorial = producto . enumeraciónDeA1 En el intérprete de Hugs, a menudo es necesario definir la función y usarla en la misma línea separada por a whereo let... inPor ejemplo, para probar los ejemplos anteriores y ver el resultado 120:
sea { factorial norte | norte > 0 = norte * factorial ( norte - 1 ); factorial _ = 1 } en factorial 5 o
factorial 5 donde factorial = producto . enumeraciónDeA1 El intérprete GHCi no tiene esta restricción y las definiciones de funciones se pueden ingresar en una línea (con la letsintaxis sin la inparte) y se puede hacer referencia a ellas más adelante.
En la fuente de Haskell inmediatamente debajo, ::se puede leer como "tiene tipo"; a -> bse puede leer como "es una función de a a b". (Por lo tanto, Haskell calc :: String -> [Float]se puede leer como " calctiene un tipo de función desde cadenas hasta listas de flotantes".) En la segunda línea, calc = ...el signo igual se puede leer como "puede ser"; por lo tanto, varias líneas con calc = ...se pueden leer como múltiples valores posibles para calc, dependiendo de las circunstancias detalladas en cada línea.
Una calculadora simple de notación polaca inversa expresada con la función de orden superior foldl cuyo argumento f se define en una cláusula donde usando la coincidencia de patrones y la clase de tipo Leer :
calc :: Cadena -> [ Flotador ] calc = foldl f [] . palabras donde f ( x : y : zs ) "+" = ( y + x ) : zs f ( x : y : zs ) "-" = ( y - x ) : zs f ( x : y : zs ) "* " = ( y * x ) : zs f ( x : y : zs ) "/" = ( y / x ) : zs f ( x : y : zs ) "FLIP" = y : x : zs f zs w = leer w : zs La lista vacía es el estado inicial, y f interpreta una palabra a la vez, ya sea como el nombre de una función, tomando dos números del encabezado de la lista y volviendo a introducir el resultado, o analizando la palabra como un número de punto flotante y anteponiéndolo a la lista.
La siguiente definición produce la lista de números de Fibonacci en tiempo lineal:
fibs = 0 : 1 : zipCon ( + ) fibs ( fibs de cola ) La lista infinita se produce mediante corecursión : los últimos valores de la lista se calculan según demanda a partir de los dos elementos iniciales 0 y 1. Este tipo de definición se basa en una evaluación diferida , una característica importante de la programación de Haskell. Para ver un ejemplo de cómo evoluciona la evaluación, a continuación se ilustran los valores de fibs y tail fibs después del cálculo de seis elementos y se muestra cómo zipWith (+) ha producido cuatro elementos y procede a producir el siguiente elemento:
mentiras = 0: 1: 1: 2: 3: 5: ... + + + + + +fibras de la cola = 1: 1: 2: 3: 5: ... = = = = = =zipCon... = 1: 2: 3: 5: 8 : ...mentiras = 0: 1: 1: 2: 3: 5: 8 : ...
La misma función, escrita usando la sintaxis de comprensión de listas paralelas del Glasgow Haskell Compiler (las extensiones GHC deben habilitarse usando un indicador de línea de comando especial, aquí -XParallelListComp , o iniciando el archivo fuente con ):{-# LANGUAGE ParallelListComp #-}
mentiras = 0 : 1 : [ a + b | a <- mentiras | b <- fibrillas de la cola ] o con listas de comprensión regulares :
mentiras = 0 : 1 : [ a + b | ( a , b ) <- fibs zip ( fibs de cola ) ] o directamente autorreferencial:
mentiras = 0 : 1 : siguientes mentiras donde siguiente ( a : t @ ( b : _ )) = ( a + b ) : siguiente t Con función generadora de estado :
mentiras = siguiente ( 0 , 1 ) donde siguiente ( a , b ) = a : siguiente ( b , a + b ) o con unfoldr:
mentiras = desplegarr ( \ ( a , b ) -> Sólo ( a , ( b , a + b ))) ( 0 , 1 ) o scanl:
fibs = 0 : scanl ( + ) 1 fibs Uso de la recursividad de datos con el combinador de puntos fijos predefinido de Haskell :
fibs = arreglar ( \ xs -> 0 : 1 : zipWith ( + ) xs ( cola xs )) - zipWith versión = arreglar (( 0 : ) . ( 1 : ) . ( zipWith ( + ) <*> cola )) -- igual que arriba, pointfree = fix (( 0 : ) . scanl ( + ) 1 ) -- versión scanl El factorial que vimos anteriormente se puede escribir como una secuencia de funciones:
factorial n = foldr (( . ) . ( * )) id [ 1 .. n ] $ 1 -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) . ) ( ((4*) .) ( ((5*) .) id )))) 1 -- == (1*) . (2*) . (3*) . (4*) . (5*) . identificación $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* ( identificación 1 ))))) factorial n = foldr (( . ) . ( * )) ( const 1 ) [ 1 .. n ] $ () -- factorial 5 == ((1*) .) ( ((2*) .) ( (( 3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) () -- == (1*) . (2*) . (3*) . (4*) . (5*) . constante 1 $ () -- == 1* ( 2* ( 3* ( 4* ( 5* ( constante 1 () ))))) factorial n = foldr (( $ ) . ( * )) 1 [ 1 .. n ] = foldr ( $ ) 1 $ mapa ( * ) [ 1 .. n ] -- factorial 5 == ((1*) $) ( ((2*) $) ( ((3*) $) ( ((4*) $) ( ((5*) $) 1 )))) -- == (1*) $ (2*) $ (3*) $ (4*) $ (5*) $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* 1 )))) Una función notablemente concisa que devuelve la lista de números de Hamming en orden:
hamming = 1 : mapa ( 2 * ) hamming ` unión ` mapa ( 3 * ) hamming ` unión ` mapa ( 5 * ) hamming Al igual que las diversas fibssoluciones mostradas anteriormente, utiliza corecursion para producir una lista de números a pedido, comenzando desde el caso base de 1 y creando nuevos elementos basados en la parte anterior de la lista.
Aquí la función unionse utiliza como operador encerrándola entre comillas invertidas. Sus casecláusulas definen cómo fusiona dos listas ascendentes en una lista ascendente sin elementos duplicados, representando conjuntos como listas ordenadas. Su función complementaria minusimplementa la diferencia establecida :
Es posible generar sólo los múltiplos únicos, para una operación más eficiente. Como no hay duplicados, no es necesario eliminarlos:
smooth235 = 1 : foldr ( \ p s -> fix $ mergeBy ( < ) s . map ( p * ) . ( 1 : )) [] [ 2 , 3 , 5 ] donde fix f = x donde x = f x - - combinador de puntos fijos, con uso compartido Esto utiliza la función más eficiente mergeque no se ocupa de los duplicados (también se usa en la siguiente función mergesort):
fusionar por menos xs ys = fusionar xs ys donde fusionar xs [] = xs fusionar [] ys = ys fusionar ( x : xs ) ( y : ys ) | menos y x = y : fusionar ( x : xs ) ys | de lo contrario = x : fusionar xs ( y : ys ) Cada barra vertical ( |) inicia una cláusula de protección con una expresión de protección antes del =signo y la definición correspondiente después, que se evalúa si la protección es verdadera.
A continuación se muestra una clasificación de combinación de abajo hacia arriba , definida mediante la función de orden superior until :
mergesortBy less [] = [] mergesortBy less xs = head $ hasta ( null . tail ) ( por pares $ mergeBy less ) [[ x ] | x <- xs ] por pares f ( a : b : t ) = f a b : por pares f t por pares f t = t La definición matemática de números primos se puede traducir prácticamente palabra por palabra a Haskell:
-- "Enteros superiores a 1 que no pueden dividirse por un entero menor superior a 1" -- primos = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem nd = 0 } -- = { n ∈ [2..] | ∀ d ∈ [2..n-1] ⇒ rem nd ≠ 0 }primos = [ norte | n <- [ 2 .. ], todos ( \ d -> rem n d /= 0 ) [ 2 .. ( n - 1 )] ] Esto encuentra números primos por división de prueba . Tenga en cuenta que no está optimizado para la eficiencia y tiene un rendimiento muy pobre. Ligeramente más rápido (pero aún muy lento) [3] es este código de David Turner :
números primos = tamiz [ 2 .. ] donde tamiz ( p : xs ) = p : tamiz [ x | x <- xs , rem x p /= 0 ] Mucho más rápido es el algoritmo de división de prueba óptimo.
primos = 2 : [ norte | n <- [ 3 .. ], todos (( > 0 ) . rem n ) $ takeWhile (( <= n ) . ( ^ 2 )) primos ] o un tamiz ilimitado de Eratóstenes con tamizado pospuesto por etapas, [4]
números primos = 2 : números primos de tamiz [ 3 .. ] donde tamiz ( p : ps ) ( span ( < p * p ) -> ( h , t )) = h ++ tamiz ps ( menos t [ p * p , p * p + p .. ]) o la implementación combinada del tamiz de Richard Bird , [5]
-- "Enteros superiores a 1 sin números compuestos que -- se encuentran mediante la enumeración de los múltiplos de cada primo" primos = 2 : menos [ 3 .. ] ( foldr ( \ ( m : ms ) r -> m : union ms r ) [] [[ p * p , p * p + p .. ] | p <- primos ]) o una variante de plegado en forma de árbol aún más rápida [6] con una complejidad temporal casi óptima (para un código basado en listas) y una complejidad espacial muy baja lograda mediante la producción recursiva telescópica de números primos en varias etapas:
primos = 2 : _Y (( 3 : ) . menos [ 5 , 7 .. ] . _U . map ( \ p -> [ p * p , p * p + 2 * p .. ])) donde -- no- compartiendo el combinador Y: _Y g = g ( _Y g ) -- (g (g (g (g (...))))) -- big union ~= nub.sort.concat _U (( x : xs ) : t ) = x : ( unión xs . _U . unión por pares ) t Trabajando en matrices por segmentos entre cuadrados consecutivos de números primos, es
importar datos.Array importar datos.lista ( colas , inicios ) primos = 2 : [ norte | ( r : q : _ , px ) <- zip ( tails ( 2 : [ p * p | p <- primos ])) ( inits primos ), ( n , True ) <- assocs ( accumArray ( \ _ _ -> Falso ) Verdadero ( r + 1 , q - 1 ) [ ( m , ( ) ) | p <- px , s <- [ div ( r + p ) p * p ] , m <- [ s , s + p . . q - 1 ] ] ) ] Probablemente el código más corto posible sea nubBy (((>1) .) . gcd) [2..]. Es bastante lento.
Haskell permite utilizar sangría para indicar el comienzo de una nueva declaración. Por ejemplo, en una cláusula donde :
producto xs = prod xs 1 donde prod [] a = a prod ( x : xs ) a = prod xs ( a * x ) Las dos ecuaciones de la función anidada prod están alineadas verticalmente, lo que permite omitir el separador de punto y coma. En Haskell, la sangría se puede utilizar en varias construcciones sintácticas, incluidas do, let, case, classy instance.
El uso de sangría para indicar la estructura del programa se origina en el lenguaje ISWIM de Peter J. Landin , donde se le llamó regla del fuera de juego . Esto fue adoptado más tarde por Miranda , y Haskell adoptó una versión similar (pero bastante más compleja) de la regla del fuera de juego de Miranda, que se llama "diseño". Otros lenguajes que adoptan una sintaxis sensible a los espacios en blanco incluyen Python y F# .
El uso del diseño en Haskell es opcional. Por ejemplo, la función productanterior también se puede escribir:
producto xs = prod xs 1 donde { prod [] a = a ; prod ( x : xs ) a = prod xs ( a * x ) } La llave de apertura explícita después de la wherepalabra clave indica que las declaraciones separadas utilizarán punto y coma explícitos, y la lista de declaraciones terminará con una llave de cierre explícita. Una razón para querer soporte para delimitadores explícitos es que facilita la generación automática de código fuente de Haskell .
La regla de diseño de Haskell ha sido criticada por su complejidad. En particular, la definición establece que si el analizador encuentra un error de análisis durante el procesamiento de una sección de diseño, entonces debería intentar insertar una llave (la regla del "error de análisis"). La implementación de esta regla en una combinación tradicional de análisis sintáctico y léxico requiere una cooperación bidireccional entre el analizador sintáctico y el analizador léxico, mientras que en la mayoría de los idiomas, estas dos fases se pueden considerar de forma independiente.
Aplicar una función fa un valor xse expresa simplemente f x.
Haskell distingue las llamadas a funciones de los operadores infijos sintácticamente, pero no semánticamente. Los nombres de funciones que se componen de caracteres de puntuación se pueden utilizar como operadores, al igual que otros nombres de funciones si están rodeados de comillas invertidas; y los operadores se pueden utilizar en notación de prefijo si están entre paréntesis.
Este ejemplo muestra las formas en que se pueden llamar funciones:
sumar a b = a + b diez1 = 5 + 5 diez2 = ( + ) 5 5 diez3 = sumar 5 5 diez4 = 5 ` sumar ` 5 Las funciones que se definen tomando varios parámetros siempre se pueden aplicar parcialmente. Los operadores binarios se pueden aplicar parcialmente usando notación de sección :
diez5 = ( + 5 ) 5 diez6 = ( 5 + ) 5 sumacinco = ( 5 + ) diez7 = sumacinco 5 Consulte Comprensión de lista#Descripción general para ver el ejemplo de Haskell.
La coincidencia de patrones se utiliza para hacer coincidir los diferentes constructores de tipos de datos algebraicos. A continuación se muestran algunas funciones, cada una de las cuales utiliza la coincidencia de patrones en cada uno de los tipos siguientes:
-- Esta firma de tipo dice que vacío toma una lista que contiene cualquier tipo y devuelve un Bool vacío :: [ a ] -> Bool vacío ( x : xs ) = Falso vacío [] = Verdadero -- Devolverá un valor de Quizás a, dado un valor predeterminado en caso de que no se encuentre Nada deQuizás :: a -> Quizás a -> a deQuizás x ( Sólo y ) = y deQuizás x Nada = x isRight :: Ya sea a b -> Bool isRight ( Derecha _ ) = Verdadero isRight ( Izquierda _ ) = Falso getName :: Persona -> Cadena getName ( nombre de persona _ _ ) = nombre getSexo :: Persona -> Sexo getSex ( Persona _ sexo _ ) = sexo getAge :: Persona -> Int getAge ( Persona _ _ edad ) = edad Usando las funciones anteriores, junto con la mapfunción, podemos aplicarlas a cada elemento de una lista, para ver sus resultados:
mapa vacío [[ 1 , 2 , 3 ], [] ,[ 2 ],[ 1 .. ]] - devuelve [Falso, Verdadero, Falso, Falso] mapa ( deQuizás 0 ) [ Solo 2 , Nada , Solo 109238 , Nada ] - devuelve [2,0,109238,0] map isRight [ Izquierda "hola" , Derecha 6 , Derecha 23 , Izquierda "mundo" ] - devuelve [Falso, Verdadero, Verdadero, Falso] map getName [ Persona "Sarah" Mujer 20 , Persona "Alex" Hombre 20 , tom ] - devuelve ["Sarah", "Alex", "Tom"], usando la definición de tom anterior Las tuplas en Haskell se pueden utilizar para contener un número fijo de elementos. Se utilizan para agrupar datos de diferentes tipos:
cuenta :: ( Cadena , Integer , Doble ) - El tipo de una tupla triple, que representa : un nombre, saldo y tasa de interés de cuenta = ( "John Smith" , 102894 , 5.25 ) Las tuplas se usan comúnmente en las funciones zip* para colocar elementos adyacentes en listas separadas juntos en tuplas (zip4 a zip7 se proporcionan en el módulo Data.List):
-- La definición de la función zip. Otras funciones zip* se definen de manera similar zip :: [ x ] -> [ y ] -> [( x , y )] zip ( x : xs ) ( y : ys ) = ( x , y ) : zip xs ys zip _ _ = [] zip [ 1 .. 5 ] "hola" -- devuelve [(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,' o')] - y tiene tipo [(Integer, Char)] zip3 [ 1 .. 5 ] "hola" [ Falso , Verdadero , Falso , Falso , Verdadero ] - devuelve [(1,'h',Falso),(2,'e',Verdadero),(3,'l ',False),(4,'l',False),(5,'o',True)] - y tiene tipo [(Integer,Char,Bool)] En el compilador GHC, las tuplas se definen con tamaños desde 2 elementos hasta 62 elementos.
En la sección § Ejemplos más complejos anterior, calcse usa en dos sentidos, lo que muestra que existe un espacio de nombres de clase de tipo Haskell y también un espacio de nombres para valores:
calc. El dominio y el rango se pueden indicar explícitamente en una clase de tipo Haskell.calc.Los tipos de datos algebraicos se utilizan ampliamente en Haskell. Algunos ejemplos de estos son la lista integrada Maybey Eitherlos tipos:
-- Una lista de a ([a]) es una a conseguida (:) en otra lista de a, o una lista vacía ([]) data [ a ] = a : [ a ] | [] -- Algo de tipo Quizás a sea Solo algo o Nada de datos Quizás a = Solo a | Nada - Algo de tipo Cualquiera tipo btype es un tipo a izquierdo o un tipo b derecho datos O a b = Left a | derecha b Los usuarios del lenguaje también pueden definir sus propios tipos de datos abstractos . Un ejemplo de un ADT utilizado para representar el nombre, el sexo y la edad de una persona podría verse así:
datos Sexo = Masculino | Datos femeninos Persona = Persona Cadena Sexo Int . Observe que Persona es a la vez un constructor y un tipo. -- Un ejemplo de creación de algo del tipo Persona tom :: Persona tom = Persona "Tom" Hombre 27 La mónada ST permite escribir algoritmos de programación imperativos en Haskell, utilizando variables mutables (STRefs) y arrays mutables (STArrays y STUArrays). La ventaja de la mónada ST es que permite escribir código que tiene efectos secundarios internos, como la actualización destructiva de variables y matrices mutables, al tiempo que contiene estos efectos dentro de la mónada. El resultado de esto es que las funciones escritas usando la mónada ST parecen puras para el resto del programa. Esto permite utilizar código imperativo donde puede resultar poco práctico escribir código funcional, manteniendo al mismo tiempo toda la seguridad que proporciona el código puro.
Aquí hay un programa de ejemplo (tomado de la página wiki de Haskell sobre la mónada ST) que toma una lista de números y los suma usando una variable mutable:
importar Control.Monad.ST importar Datos.STRef importar Control.Monad sumST :: Num a => [ a ] -> a sumST xs = runST $ do - runST toma código ST con estado y lo hace puro. sumed <- newSTRef 0 - Crea un STRef (una variable mutable) forM_ xs $ \ x -> do - Para cada elemento de la lista de argumentos xs .. modifiqueSTRef sumado ( + x ) - agréguelo a lo que tenemos en n. readSTRef sumado : lee el valor de n, que será devuelto por el runST anterior. La mónada STM es una implementación de la memoria transaccional de software en Haskell. Se implementa en el compilador GHC y permite modificar variables mutables en las transacciones .
Como Haskell es un lenguaje puramente funcional, las funciones no pueden tener efectos secundarios. Al no ser estricto, tampoco tiene un orden de evaluación bien definido. Este es un desafío para los programas reales, que entre otras cosas necesitan interactuar con un entorno. Haskell resuelve esto con tipos monádicos que aprovechan el sistema de tipos para garantizar la secuencia adecuada de construcciones imperativas. El ejemplo típico es la entrada/salida (E/S), pero las mónadas son útiles para muchos otros propósitos, incluido el estado mutable, la concurrencia y la memoria transaccional, el manejo de excepciones y la propagación de errores.
Haskell proporciona una sintaxis especial para expresiones monádicas, de modo que los programas con efectos secundarios puedan escribirse en un estilo similar a los lenguajes de programación imperativos actuales; Para ello no se requieren conocimientos de las matemáticas detrás de las E/S monádicas . El siguiente programa lee un nombre de la línea de comando y genera un mensaje de saludo:
main = do putStrLn "¿Cuál es tu nombre?" nombre <- getLine putStr ( "Hola, " ++ nombre ++ "! \n " ) La notación do facilita el trabajo con mónadas. Esta expresión do es equivalente, pero (posiblemente) más fácil de escribir y comprender, que la versión sin azúcar que emplea los operadores monádicos directamente:
principal = putStrLn "¿Cuál es tu nombre?" >> getLine >>= \ nombre -> putStr ( "Hola, " ++ nombre ++ "! \n " ) La definición del lenguaje Haskell no incluye concurrencia ni paralelismo , aunque GHC admite ambos.
Concurrent Haskell es una extensión de Haskell que admite subprocesos y sincronización . [7] La implementación de Concurrent Haskell por parte de GHC se basa en la multiplexación de subprocesos ligeros de Haskell en unos pocos subprocesos de sistema operativo (SO) pesados, [8] de modo que los programas de Concurrent Haskell se ejecuten en paralelo mediante multiprocesamiento simétrico . El tiempo de ejecución puede admitir millones de subprocesos simultáneos. [9]
La implementación de GHC emplea un grupo dinámico de subprocesos del sistema operativo, lo que permite que un subproceso de Haskell realice una llamada de bloqueo al sistema sin bloquear otros subprocesos de Haskell en ejecución. [10] Por lo tanto, los subprocesos ligeros de Haskell tienen las características de los subprocesos pesados del sistema operativo, y un programador puede desconocer los detalles de implementación.
Recientemente, [ ¿ cuándo? ] Concurrent Haskell se ha ampliado con soporte para memoria transaccional de software (STM), que es una abstracción de concurrencia en la que las operaciones compuestas sobre datos compartidos se realizan de forma atómica, como transacciones. [11] La implementación STM de GHC es la única implementación STM hasta la fecha que proporciona una garantía de tiempo de compilación estática que evita que se realicen operaciones no transaccionales dentro de una transacción. La biblioteca Haskell STM también proporciona dos operaciones que no se encuentran en otros STM: retryy orElse, que juntas permiten que las operaciones de bloqueo se definan de forma modular y componible .