Este artículo describe las características del lenguaje de programación Haskell .
Un ejemplo simple 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 ) de lo contrario 1 Esto describe el factorial como una función recursiva, con un caso base final. Es similar a las descripciones de los factoriales que se encuentran en los libros de texto de matemáticas. Gran parte del código Haskell es similar a la notación matemática estándar en 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 que incluirla es un buen estilo [1] . Puede leerse como la función factorial ( factorial) tiene tipo ( ::) de entero a entero ( Integer -> Integer). Es decir, toma un entero como argumento y devuelve otro entero. El tipo de una definición se infiere automáticamente si no se proporciona ninguna anotación de tipo.
La segunda línea se basa en la búsqueda 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 entero 1 (uno). Para todos los demás casos, se intenta la tercera línea. Esta es la recursión y ejecuta la función nuevamente hasta que se alcanza el caso base.
Utilizando la productfunción del Preludio, una serie de pequeñas funciones análogas a la biblioteca estándar de C y utilizando 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]se denota la secuencia aritmética 1, 2, …, n en forma de lista. Utilizando la función Preludio enumFromTo, la expresión [1..n]se puede escribir como enumFromTo 1 n, lo que permite expresar la función factorial como
factorial n = producto ( enumFromTo 1 n ) que, utilizando el operador de composición de función (expresado como un punto en Haskell) para componer la función de producto con la función de enumeración currificada , se puede reescribir en un estilo sin puntos : [2]
factorial = producto . enumFromTo 1 En el intérprete de Hugs, a menudo es necesario definir la función y usarla en la misma línea separada por un whereo let.. in. Por ejemplo, para probar los ejemplos anteriores y ver el resultado 120:
sea { factorial n | n > 0 = n * factorial ( n - 1 ); factorial _ = 1 } en factorial 5 o
factorial 5 donde factorial = producto . enumFromTo 1 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 hacer referencia a ellas más adelante.
En el código fuente de Haskell que se muestra a continuación, ::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 el tipo de una función de cadenas a 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, según la circunstancia detallada 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 where utilizando la coincidencia de patrones y la clase de tipo Leer :
calc :: String -> [ Float ] calc = foldl f [] .words 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 un nombre de función, tomando dos números del principio de la lista y colocando el resultado nuevamente, 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 : zipWith ( + ) fibs ( cola fibs ) La lista infinita se produce mediante recursión : los últimos valores de la lista se calculan a pedido a partir de los dos elementos iniciales 0 y 1. Este tipo de definición se basa en la evaluación diferida , una característica importante de la programación Haskell. Para un ejemplo de cómo evoluciona la evaluación, lo siguiente ilustra los valores de fibs y tail fibs después del cálculo de seis elementos y muestra cómo zipWith (+) ha producido cuatro elementos y procede a producir el siguiente elemento:
mentiras = 0 : 1 : 1 : 2 : 3 : 5 : ... + + + + + +pestañas de 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 utilizando la sintaxis de comprensión de listas paralelas del compilador Glasgow Haskell (las extensiones GHC deben habilitarse utilizando un indicador de línea de comando especial, aquí -XParallelListComp , o iniciando el archivo fuente con ):{-# LANGUAGE ParallelListComp #-}
fibs = 0 : 1 : [ a + b | a <- fibs | b <- cola fibs ] o con listas por comprensión regulares :
fibs = 0 : 1 : [ a + b | ( a , b ) <- zip fibs ( cola fibs ) ] o directamente autorreferencial:
fibs = 0 : 1 : siguiente fibs donde siguiente ( a : t @ ( b : _ )) = ( a + b ) : siguiente t Con función generadora de estado :
fibs = siguiente ( 0 , 1 ) donde siguiente ( a , b ) = a : siguiente ( b , a + b ) o con unfoldr:
fibs = desplegar ( \ ( a , b ) -> Sólo ( a , ( b , a + b ))) ( 0 , 1 ) o scanl:
fibs = 0 : scanl ( + ) 1 fibs Uso de la recursión de datos con el combinador de puntos fijos predefinido de Haskell :
fibs = fix ( \ xs -> 0 : 1 : zipWith ( + ) xs ( tail xs )) -- zipWith versión = fix (( 0 : ) . ( 1 : ) . ( zipWith ( + ) <*> tail )) -- 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*) . id $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* ( id 1 ))))) factorial n = foldr (( . ) . ( * )) ( const 1 ) [ 1 .. n ] $ () -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) () -- == (1*) . (2*) . (3*) . (4*) . (5*) . const 1 $ () -- == 1* ( 2* ( 3* ( 4* ( 5* ( const 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 arriba, esta utiliza corecursionismo para producir una lista de números a pedido, comenzando desde el caso base de 1 y construyendo 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 de conjuntos :
Es posible generar solo 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 punto fijo, con compartición Esto utiliza la función más eficiente mergeque no se ocupa de los duplicados (también se utiliza en la siguiente función mergesort):
fusionarPor 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 de ella, que se evalúa si la protección es verdadera.
A continuación se muestra una ordenación por combinación de abajo hacia arriba , definida mediante la función de orden superior until :
mergesortBy less [] = [] mergesortBy less xs = head $ till ( null . tail ) ( pairwise $ mergeBy less ) [[ x ] | x <- xs ] pares f ( a : b : t ) = f a b : pares f t pares f t = t La definición matemática de números primos se puede traducir prácticamente palabra por palabra al lenguaje Haskell:
-- "Números enteros mayores que 1 que no pueden ser divididos por un número entero menor que 1" -- primos = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem nd = 0 } -- = { n ∈ [2..] | ∀ d ∈ [2..n-1] ⇒ rem nd ≠ 0 }primos = [ n | n <- [ 2 .. ], todos ( \ d -> rem n d /= 0 ) [ 2 .. ( n - 1 )] ] Este método permite encontrar números primos por división de prueba . Tenga en cuenta que no está optimizado para lograr eficiencia y tiene un rendimiento muy bajo. Un poco más rápido (pero aún muy lento) [3] es este código de David Turner :
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 : [ n | n <- [ 3 .. ], todos (( > 0 ) . rem n ) $ takeWhile (( <= n ) . ( ^ 2 )) primos ] o un tamiz ilimitado de Eratóstenes con tamizado pospuesto en etapas, [4]
primos = 2 : tamiz primos [ 3 .. ] donde tamiz ( p : ps ) ( span ( < p * p ) -> ( h , t )) = h ++ tamiz ps ( menos t [ p * p , p * p + p .. ]) o la implementación del tamiz combinado de Richard Bird , [5]
-- "Números enteros mayores que 1 sin ningún número compuesto que -- se encuentran por enumeración de los múltiplos de cada primo" primos = 2 : menos [ 3 .. ] ( foldr ( \ ( m : ms ) r -> m : unión 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 multietapa de números primos:
primos = 2 : _Y (( 3 : ) . minus [ 5 , 7 .. ] . _U . map ( \ p -> [ p * p , p * p + 2 * p .. ])) donde -- combinador Y no compartidor: _Y g = g ( _Y g ) -- (g (g (g (g (...))))) -- unión grande ~= nub.sort.concat _U (( x : xs ) : t ) = x : ( unión xs . _U . unión por pares ) t Trabajando sobre matrices por segmentos entre cuadrados consecutivos de primos, es
importar Data.Array importar Data.List ( tails , inits ) primos = 2 : [ n | ( r : q : _ , px ) <- zip ( colas ( 2 : [ p * p | p <- primos ])) ( inicializa primos ), ( n , Verdadero ) <- assocs ( accumArray ( \ _ _ -> Falso ) Verdadero ( r + 1 , q - 1 ) [ ( m , () ) | p <- px , s <- [ div ( r + p ) p * p ] , m <- [ s , s + p .. q - 1 ] ] ) ] El código más corto posible es probablemente nubBy (((>1) .) . gcd) [2..]. Es bastante lento.
Haskell permite utilizar sangrías para indicar el comienzo de una nueva declaración. Por ejemplo, en una cláusula where :
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, entre ellas 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 lo denominaba regla del off-side . Esta regla fue adoptada más tarde por Miranda y Haskell adoptó una versión similar (pero bastante más compleja) de la regla del off-side de Miranda, que se denomina "layout". Otros lenguajes que adoptan una sintaxis sensible a los caracteres de espacio en blanco incluyen Python y F# .
El uso de layout en Haskell es opcional. Por ejemplo, la función productanterior también se puede escribir así:
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 independientes utilizarán puntos y coma explícitos y que la lista de declaraciones terminará con una llave de cierre explícita. Una de las razones por las que se desea compatibilidad con 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 debe intentar insertar una llave de cierre (la regla del "error de análisis"). Implementar esta regla en una combinación tradicional de análisis léxico y análisis sintáctico requiere una cooperación bidireccional entre el analizador y el analizador léxico, mientras que en la mayoría de los lenguajes, estas dos fases se pueden considerar de forma independiente.
La aplicación de una función fa un valor xse expresa simplemente como f x.
Haskell distingue las llamadas a funciones de los operadores infijos sintácticamente, pero no semánticamente. Los nombres de funciones que están compuestos por caracteres de puntuación se pueden utilizar como operadores, al igual que otros nombres de funciones si se incluyen entre comillas simples invertidas; y los operadores se pueden utilizar en la notación de prefijo si se incluyen entre paréntesis.
Este ejemplo muestra las formas en que se pueden llamar las funciones:
suma a b = a + b diez1 = 5 + 5 diez2 = ( + ) 5 5 diez3 = sumar 5 5 diez4 = 5 ` sumar ` 5 Las funciones que se definen como que toman varios parámetros siempre se pueden aplicar parcialmente. Los operadores binarios se pueden aplicar parcialmente utilizando la notación de sección :
diez5 = ( + 5 ) 5 diez6 = ( 5 + ) 5 sumacinco = ( 5 + ) diez7 = sumacinco 5 Consulte Comprensión de listas#Descripción general para el ejemplo de Haskell.
La búsqueda de patrones se utiliza para buscar coincidencias en los distintos constructores de tipos de datos algebraicos. A continuación se muestran algunas funciones, cada una de las cuales utiliza la búsqueda de patrones en cada uno de los tipos siguientes:
-- Esta firma de tipo dice que empty toma una lista que contiene cualquier tipo y devuelve un Bool empty :: [ a ] -> Bool empty ( x : xs ) = False empty [] = True -- Devolverá un valor de un Maybe a, dado un valor predeterminado en caso de que se encuentre un Nothing fromMaybe :: a -> Maybe a -> a fromMaybe x ( Just y ) = y fromMaybe x Nothing = x isRight :: O bien a b -> Bool isRight ( Right _ ) = True isRight ( Left _ ) = False getName :: Persona -> String getName ( Nombre de la persona _ _ ) = nombre getSex :: 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 ( deMaybe 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] mapa getName [ Persona "Sarah" Mujer 20 , Persona "Alex" Hombre 20 , tom ] -- devuelve ["Sarah", "Alex", "Tom"], utilizando la definición para tom anterior Las tuplas en Haskell se pueden utilizar para almacenar una cantidad fija de elementos. Se utilizan para agrupar fragmentos de datos de distintos tipos:
cuenta ::( Cadena , Entero , Doble ) - El tipo de una tupla de tres, que representa : un nombre, un saldo y una tasa de interés cuenta = ( "John Smith" , 102894 , 5.25 ) Las tuplas se utilizan comúnmente en las funciones zip* para colocar elementos adyacentes en listas separadas juntas en tuplas (zip4 a zip7 se proporcionan en el módulo Data.List):
-- Definición de la función zip. Otras funciones zip* se definen de forma 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',Falso),(4,'l',Falso),(5,'o',Verdadero)] -- 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 utiliza en dos sentidos, mostrando que hay 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 las listas integradas Maybey Eitherlos tipos:
-- Una lista de a ([a]) es una a convertida (:) en otra lista de a, o una lista vacía ([]) datos [ a ] = a : [ a ] | [] -- Algo de tipo Quizás a es Sólo algo, o Nada datos Quizás a = Sólo a | Nada -- Algo de tipo Cualquiera de los dos tipos atype btype es un atype Izquierdo, o un btype Derecho datos Cualquiera de los dos tipos a b = Izquierda a | Derecha b Los usuarios del lenguaje también pueden definir sus propios tipos de datos abstractos . Un ejemplo de un TAD utilizado para representar el nombre, el sexo y la edad de una persona podría ser el siguiente:
datos Sexo = Masculino | Femenino datos Persona = Persona String Sexo Int -- Tenga en cuenta que Persona es tanto un constructor como 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 imperativa en Haskell, utilizando variables mutables (STRefs) y matrices 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 utilizando la mónada ST aparecen puras para el resto del programa. Esto permite utilizar código imperativo donde puede resultar poco práctico escribir código funcional, al mismo tiempo que se mantiene 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 Data.STRef importar Control.Monad sumST :: Num a => [ a ] -> a sumST xs = runST $ do -- runST toma código ST con estado y lo vuelve puro. summed <- newSTRef 0 -- Crea un STRef (una variable mutable) forM_ xs $ \ x -> do -- Para cada elemento de la lista de argumentos xs .. modifySTRef sumado ( + x ) -- agregarlo 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. Esto 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 secuenciación adecuada de las construcciones imperativas. El ejemplo típico es la entrada/salida (E/S), pero las mónadas son útiles para muchos otros propósitos, incluidos 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 se puedan escribir en un estilo similar a los lenguajes de programación imperativa actuales; para esto no se requieren conocimientos matemáticos de la E/S monádica . El siguiente programa lee un nombre desde la línea de comandos y muestra un mensaje de bienvenida:
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 a la versión sin azúcar que emplea los operadores monádicos directamente, pero (posiblemente) más fácil de escribir y comprender que la anterior:
main = putStrLn "¿Cuál es tu nombre?" >> getLine >>= \ nombre -> putStr ( "Hola, " ++ nombre ++ "! \n " ) La definición del lenguaje Haskell no incluye ni 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 de GHC se basa en multiplexar subprocesos ligeros de Haskell en unos pocos subprocesos pesados del sistema operativo (SO), [8] de modo que los programas Concurrent Haskell se ejecuten en paralelo a través de multiprocesamiento simétrico . El entorno 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 sistema de bloqueo sin bloquear otros subprocesos de Haskell en ejecución. [10] Por lo tanto, los subprocesos livianos de Haskell tienen las características de los subprocesos pesados del sistema operativo, y un programador puede desconocer los detalles de la 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 de STM de GHC es la única implementación de 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 STM de Haskell también proporciona dos operaciones que no se encuentran en otras STM: retryy orElse, que juntas permiten definir operaciones de bloqueo de forma modular y componible .