PLP | Teoría de funcional

# PLP | Teoría de funcional ### Indice [toc] ## Expresiones - Las expresiones son secuencias de simbolos que sirven para representar datos, funciones y funciones aplicadas a los datos. - (Recordemos: las funciones también son datos) - Una expresión puede ser: - 1. Un constructor - `True False [] (:) 0 1 2` - 2. Una variable. - `longitud ordenar x xs (+) (*) ...` - 3. La aplicación de una expresión a otra - `ordenar lista` - `not true` - `not (not true)` - 4. También hay expresiones de otras formas, como veremos. **Las tres de arriba son las más fundamentales** ## Tipos - El universo de las expresiones está particionado en colecciones denominadas tipos | **Tipos** | |------------------------------------------------------------------------------------------------------| | - El universo de las expresiones está particionado en colecciones, denominadas tipos. | | - Un tipo tiene operaciones asociadas | | **Tipos básicos (primitivos)** | |------------------------------------------------------------------------------------------------------| | Int Char Float Bool | | **Tipos Compuestos** | |------------------------------------------------------------------------------------------------------| | \[Int\] (Int, Bool) Int → Int | ### Ejemplo: ```haskell 99 :: Int not :: Bool -> Bool not True :: Bool (+) :: Int -> Int -> Int ((+) 1) 2 :: Int ``` Hay secuencias de símbolos que no son expresiones bien formadas - `1,,2` - `)f x(` Hay secuencias que están bien formadas pero no tienen sentido (semantica) - `True + 1` - `0 1` - `[[], (+)]` ### Condiciones de tipado Para que un programa esté **bien tipado**: 1. Todas las expresiones deben tener tipo. 2. Cada variable se debe usar siempre con un mismo tipo. 3. Los dos lados de una ecuación deben tener el mismo tipo. 4. El argumento de una función debe tener el tipo del dominio. 5. El resultado de una función debe tener el tipo del codominio. **Sólo tienen sentido los programas bien tipados.** ## Modelo de cómputo Un programa funcional está dado por un conjunto de ecuaciones. Más precisamente, por un conjunto de **ecuaciones orientadas**. Una ecuación `e1 = e2` se interpreta desde dos puntos de vista: 1. **Punto de vista denotacional:** Declara que `e1` y `e2` tienen el mismo significado. 2. **Punto de vista operacional:** Computar el valor de `e1` se reduce a computar el valor de `e2`. El lado **izquierdo** de una ecuación no es una expresión arbitraria. Debe ser una función aplicada a **patrones**. Un patrón puede ser: 1. Una variable. 2. Un comodín `_`. 3. Un constructor aplicado a patrones. El lado izquierdo no debe contener variables repetidas. ### Ejemplo ¿Cuáles ecuaciones están sintácticamente bien formadas? ```haskell sumaPrimeros (x : y : z : _) = x + y + z predecesor (n + 1) = n iguales x x = True ``` Correcta: `sumaPrimeros (x : y : z : _) = x + y + z` **¿Por que es correcta?:** Cumple las reglas para definir ecuaciones en un lenguaje funcional: 1. Uso de patrones: El lado izquierdo de la ecuación usa patrones correctos x,y,z y el comodín _. 2. Variables unicas: En el lado izquierdo cada variable es unica y no se repite. 3. Expresión valida: el lado derecho es una expresión valida que utiliza variables capturadas por los patrones a la izquierda. **Ok, pero ¿por que las otras no son correctas?** 1. `predecesor (n+1) = n`: En el lado izquierdo se intenta hacer coincidir un patrón `(n+1)` con una estructura que no es un constructor. - Sugiere una operación que no es valida en el lado izquierdo de una ecuación en funcional. 2. `iguales x x = True`: El lado izquierdo se utiliza la misma variable x dos veces. ## Alto Orden - [ ]**PREGUNTAR SOBRE ESTA DEFINICIÓN** - **Definición:** Una función es de alto orden si puede recibir otras funciones como argumentos, devolver una función como resultado, o ambas cosas. En lenguajes funcionales, las funciones son tratadas como ciudadanos de primera clase, lo que significa que pueden ser manipuladas de la misma manera que cualquier otro tipo de dato. - **Ejemplo:** ```haskell -- Función de alto orden que toma una función y una lista como argumentos aplicarDoble f x = f (f x) aplicarDoble (*2) 3 -- Devuelve 12, porque primero multiplica 3 por 2, y luego el resultado (6) por 2. ``` ## Lambda - **Definición:** Una expresión lambda es una manera de **definir funciones anónimas** (sin nombre) en lenguajes funcionales. Estas funciones pueden ser usadas donde se necesiten y no es necesario que se les asigne un nombre. - **Sintaxis:** Una expresión lambda se escribe como `\x -> x + 1`, donde `\x` es el argumento de la función y `x + 1` es el cuerpo de la función. - **Ejemplo:** ```haskell (\x -> x * 2) 5 -- Devuelve 10 ``` ## Curry - **Definición:** La currificación es el proceso de **transformar una función que toma múltiples argumentos en una secuencia de funciones que toman un solo argumento**. Esto permite la aplicación parcial de funciones, donde algunos argumentos se fijan y se devuelve una nueva función que espera los argumentos restantes. - **Ejemplo:** `suma x y = x + y` se puede currificar como `suma :: Int -> (Int -> Int)`. - **Ventajas:** Facilita la evaluación parcial y reduce la necesidad de paréntesis. - **Ejemplo**: ```haskell suma x y = x + y -- Función no currificada suma 3 4 -- Devuelve 7 -- Currificación sumaCurried = \x -> \y -> x + y sumaCurried 3 4 -- Devuelve 7 sumaCurried 3 -- Devuelve una función que espera un segundo argumento ``` ## Uncurry - **Definición**: uncurry es una función que **toma una función curried** (que recibe sus argumentos de uno en uno) y la convierte en una función que recibe un par de argumentos. - **Sintaxis**: `uncurry :: (a -> b -> c) -> ((a, b) -> c)` - Ejemplo: ```haskell curry suma :: (Int -> Int -> Int) uncurry (curry suma) (3, 4) -- Devuelve 7 ``` ## Map - **Definición:** `map` es una función de orden superior que toma una función y una lista como argumentos, y aplica la función a cada elemento de la lista, retornando una nueva lista con los resultados. - **Sintaxis:** `map f [x1, x2, ..., xn]` - **Ejemplo:** `map (+1) [1, 2, 3]` devuelve `[2, 3, 4]`. ```haskell map (+1) [1, 2, 3] -- Devuelve [2, 3, 4] map (*2) [1, 2, 3] -- Devuelve [2, 4, 6] ``` ## Flip - **Definición**: flip es una función de orden superior que toma una función de dos argumentos y devuelve una nueva función donde los argumentos están intercambiados. - Sintaxis: `flip f x y = f y x` - Ejemplo: ```haskell flip (:) [2, 3] 1 -- Devuelve [1, 2, 3] flip div 2 10 -- Devuelve 5 (10 dividido por 2) ``` ## Tipo de dato Maybe e Either - Se utilizan para **manejar situaciones en las que un cálculo puede fallar o no tener un resultado válido**. - Ambos tipos permiten trabajar de manera segura con valores que pueden ser opcionales o representar errores sin necesidad de utilizar excepciones. ```haskell data Maybe a = Nothing | Just a ``` - "Maybe" o "Quizás", representa un valor que puede ser "Just a" (un valor válido tipo a) o "Nothing" que significa ausencia de valor. - Sirve para manejar errores, representar valores que pueden o no existir. - como buscar un elemento en una lista, realizar una división donde el divisor podría ser cero, etc. - Ejemplo: ```haskell safeDivide :: Int -> Int -> Maybe Int safeDivide _ 0 = Nothing safeDivide x y = Just (x `div` y) ``` # ```haskell data Either a b = Left a | Right b ``` - "Either a b", "O bien a ó b". Representa un valor que puede ser "Left a" (generalmente un error), o "Right b" valor tipo b que generalmente es el resultado correcto. - Sirve para respresentar calculos que pueden fallar. ```haskell parseNumber :: String -> Either String Int parseNumber str | all isDigit str = Right (read str) | otherwise = Left "Input is not a valid number" ``` #### Comparación y uso - Maybe: Es útil cuando solo te interesa saber si existe un valor o no, sin necesidad de detalles adicionales sobre el error. - Either: Es más adecuado cuando necesitas manejar errores de manera más detallada, proporcionando información sobre lo que salió mal. asasd