Programación

Funcional
Características
Paradigmas de Programación - 2022

Dr. Rubén A. Bernal

rbernal@frre.utn.edu.ar
 Modelo Funcional

• Programas constituidos únicamente por definiciones

de funciones puramente matemáticas.
• Brevedad. Los programas son más cortos y concisos.
• No existen las asignaciones de variables ni
construcciones estructuradas como la secuencia o la
iteración.
Características • En el esquema funcional se evalúan las expresiones
mediante un proceso de reducción.
• Transparencia referencial. El valor que devuelve una
función está únicamente determinado por el valor de
sus argumentos.
• Funciones de orden superior. Las funciones pueden
recibir como argumento otras y funciones y también
devolverlas como resultado.
 Reducción de Expresiones

Regla de Selección o Evaluación

Cálculo: para Impaciente
determinar el redex a Evaluación
reducir. Perezosa
Estrategia de
Control
Regla de Búsqueda: para
determinar la ecuación a utilizar.
Es igual para todos los sistemas
de programación funcional.
 Reducción de Expresiones
• La labor de un evaluador es calcular el resultado que se obtiene al simplificar
una expresión utilizando las definiciones de las funciones involucradas.

Ej: doble :: Integer -> Integer

doble x = x + x

5 * doble 3
5 * ( 3 + 3 ) { por el operador + }
5 * 6 { por el operador * }
30

Un redex es cada parte de la expresión que pueda reducirse.

Puede ser de afuera hacia adentro o de adentro hacia fuera.

Cuando una expresión no posee redex, se dice que esta en forma normal.
 Ordenes de reducción
Impaciente
• Se reduce siempre el término MAS INTERNO (el más anidado en la
expresión).
• En caso de que existan varios términos a reducir (con la misma
profundidad) se selecciona el que aparece más a la izquierda de la
expresión.
• Esto también se llama paso de parámetros por valor (call by value)

doble :: Integer -> Integer

doble x = x + x

doble (doble 3) por la definición de doble

doble (3 + 3) por el operador +
doble (6) por la definición de doble
6 + 6 por el operador +
12
 Ordenes de reducción
Perezoso
• Consiste en seleccionar el término MÁS EXTERNO (el menos anidado), y en caso
de conflicto el que aparezca más a la izquierda de la expresión.
• Esta estrategia se conoce como “paso de parámetro por nombre o referencia”
(call by name), ya que se pasan las expresiones como parámetros de las
funciones en vez de valores.
• La evaluación perezosa recuerda los valores de los argumentos ya calculados
para evitar recalcularlos.

doble :: Integer -> Integer

doble x = x + x

doble (doble 3) por la definición de doble

a + a donde a = doble 3 por la definición de doble
a + a donde a = 3 + 3 = 6 por el operador +
6 + 6 por el operador +
12
 Funciones no Estrictas

En este tipo de funciones los argumentos se evalúan solo si es necesario.

fun1 :: Integer -> Integer -> Integer

fun1 x y = x + 12

fun2 :: Integer -> Integer

fun2 x = x + 10

Impaciente Perezoso

fun1 3 (fun2 4) fun1 3 (fun2 4)

fun1 3 (4 + 10) 3 + 12
fun1 3 14 15
3 + 12
15
 Transparencia Referencial

• Si una función es llamada dos veces con los mismos parámetros, se

obtendrá siempre el mismo resultado. El resultado depende única y
exclusivamente de los parámetros provistos y no produce efecto de
lado.
• Decimos que una operación tiene transparencia referencial si es:
• Independiente: No dependen del estado de nada que este fuera de si misma
• Sin estado/Stateless: No tiene un estado que se mantenga de llamada en llamada
• Determinística: Siempre devuelven el mismo valor dados los mismos argumentos

Efecto de Lado/Colateral (Side Effect)

• Hay efecto de lado cuando un cambio de estado sobrevive a la realización
de una operación.
• Ej: Modificación de una variable global; uso de variable estáticas; fecha y
hora del sistema; valores ingresados por el usuario; valores aleatorios.
Type System

Haskell's type
system allows us to
think at a very
abstract level: it
permits us to write
concise, powerful Strong Static Inferred
programs.
 Inferencia de Tipos

Es el proceso por el cual, el tipo de una entidad declarada es

inferida a partir del tipo de la expresión asociada siempre
que no sea explícitamente enunciado.
Se utiliza el método de Hindley-Milner.

Ejemplos:
par n = (n ´mod´ 2 = 0)
Como el operador mod es del tipo Integer -> Integer -> Integer, n
debe ser de tipo entero. Luego el cuerpo de la función será Boolean. Finalmente
se infiere que la función par es del tipo par :: Integer -> Boolean.

id n = n
Como no hay pistas suficientes del tipo de n, podemos asumir que es de tipo a,
en esas condiciones el tipo de id será polimórfico… id :: a -> a
 Polimorfismo de Parámetros
Una función puede recibir parámetros de diferentes tipos; operará
uniformemente sobe cualquiera de ellos.

Ejemplos

long :: [a] -> Int

long [] = 0
long (x:xs) = 1 + long xs

toma :: Num a => a -> [b] -> [b]

toma 0 x = []
toma _ [] = []
toma n (x:xs) = x:toma (n-1) xs
Programación
Funcional
Introducción a Haskell
Paradigmas de Programación - 2022

Dr. Rubén A. Bernal

rbernal@frre.utn.edu.ar
 Lenguaje Haskell

Lenguaje lleva el nombre de Haskell

Curry, pionero en el Cálculo Lambda.

Primera especificación en 1980.

Haskell Brooks Curry

(1900-1982)
 Installing GHC and Haskell libraries

WinGHCi Visual Studio Code

Glasgow Haskell Compiler
Interpreter
 Alguna Documentación
• The craft of functional programming

http://book.realworldhaskell.org/read/

http://www.lcc.uma.es/~blas/pfHaskell/gentle/index.html

http://aprendehaskell.es/main.html

• Haskell Reference

http://zvon.org/other/haskell/Outputglobal/index.html

• Standard Prelude

https://www.haskell.org/onlinereport/standard-prelude.html
 Intérprete Haskell

Comandos :info (-)

class Num a where
...
:info
(-) :: a -> a -> a
...
:type
infixl 6 –

:type (^)
(^) :: (Num a, Integral b) => a -> b -> a
 Programas en Haskell

Un programa funcional en Haskell consiste en un número de

definiciones.
Una definición asocia un nombre a una expresión de un tipo
específico.

name <parámetros> = <cuerpo de la función>

name :: t1 -> t2 -> ... -> tn -> result_type

name p1 p2 ... pn = expresión
Valores y Tipos
 Valores y Tipos
Todos los valores de Haskell son de primera clase.

Int (enteros)
Integer (enteros con precisión ilimitada)
Char (caracteres)
[Integer] (lista homogénea de enteros)
Integer->Integer (funciones que aplican Integer sobre Integer)
(Char, Double) (tupla formado por un carácter y un flotante)

• 5 :: Integer
• 'a' :: Char
• inc :: Integer -> Integer
• [1,2,3] :: [Integer]
• ('b',4) :: (Char,Integer)
 Sinónimos de Tipos

Los sinónimos no definen tipos nuevos, sino simplemente

proporcionan nuevos nombres a tipos ya existentes.
Dan nombre a otras expresiones de tipo.

type Entero = Integer

type String = [Char]
type Persona = (Name, Address)
type Name = String
type Pila a = [a]
Operadores
 Valores Lógicos y Operadores

La álgebra booleana es también bastante simple.

True
False

• Operador y: && :: Bool -> Bool -> Bool

• Operador o: || :: Bool -> Bool -> Bool
• Negación: not :: Bool -> Bool
 Operadores

Son una variante sintáctica de las funciones con dos argumentos; se

caracterizan porque se aplican de manera infija.

x op y

(==), (/=) :: a -> a -> Bool

(<), (<=), (>=), (>) :: a -> a -> Bool
max, min :: a -> a -> a
elem :: (Eq a) => a -> [a] -> Bool
 Declaración de operadores

• Para los nombres de operadores se puede utilizar cualquier

combinación de los símbolos siguientes:

: ! # $ % & * + . / < = > ? @ \^ |

siempre que no coincidan con símbolos predefinidos.

 Asociatividad y Precedencia
• Las declaraciones de operadores se pueden completar con
declaraciones de asociatividad y de precedencia (que deben preceder
a la declaración del operador) de la forma:

asociatividad precedencia nom_op{, nom_op}*

La asociatividad sirve para resolver situaciones de ambigüedad entre

dos aplicaciones de un mismo operador, como:
x op y op z

La precedencia sirve para resolver situaciones de ambigüedad entre

aplicaciones sucesivas de distintos operadores, como:
x op1 y op2 z
 Asociatividad y Precedencia

La asociatividad puede tomar los valores siguientes:

infixl se asocia por la izquierda

infixr se asocia por la derecha
infix no se asocia

• La precedencia debe ser un valor del rango 0..9 y marca la “fuerza

de atracción” del operador sobre los argumentos.

• Los valores por defecto para cualquier operador son: infix 9.

 Declaraciones de los operadores
predefinidos

infixr 2 ||
infixr 3 &&
infix 4 ==, /=, <, <=, >=, >
infixr 5 ++, :
infixl 6 +, -
infix 7 /, `div`, `rem`, `mod`
infixl 7 *
infixr 8 ^
 Operadores y funciones prefijas

• Los operadores se pueden utilizar como funciones prefijas

escribiéndolos entre paréntesis:
x op y => (op) x y
• Las funciones prefijas se pueden utilizar como operadores
escribiéndolos entre comillas simples abiertas:
f x y => x `f` y
• Con las funciones prefijas se pueden producir aplicaciones parciales
sobre los primeros argumentos:
f x y z => f, f x, f x y
• Con los operadores se pueden producir aplicaciones parciales sobre
cualquiera de los dos argumentos:
x op y => (x op), (op y)
 Cadenas

Una cadena es una forma simplificada de la lista de caracteres.

"hola" es una forma simplificada de la lista de caracteres

['h','o','l','a’]

type String = [Char]

Esto significa que podemos usar las funciones polimórficas sobre listas
para operar con cadenas (strings). Por ejemplo:

"hello" ++ " world" => "hello world"

 Manos a la obra

Definir una función que calcule la media de tres

números.

Definir una función que reciba dos valores de verdad y devuelva la

disyunción exclusiva de ambos.
 Patrones

Cada patrón tendrá una forma que dependerá del tipo

correspondiente al parámetro que represente:

x , _ patrones irrefutables (con nombre y sin nombre)

3 patrones para números enteros.
[], (x:xs) patrones para listas vacías y no vacías
[_, x, _] patrón que fija el número de elementos de una lista
(x, y) patrones para tuplas
Lu, Ma, ... Cent x patrones en base a constructores
 Manos a la obra

Definir una función que determine el producto de dos números solo

con sumas.

Definir una función que determine el cociente de un número

utilizando restas.

Definir una función que devuelva el factorial de un número.

 Recursión sobre números naturales

• Recursión lineal

facto :: (Eq p, Num p) => p -> p

facto 0 = 1
facto n = n * facto (n-1)

• Recursión de Cola

factoC :: (Eq t, Num t) => t -> t -> t

factoC 0 n = n
factoC m n = factoC (m-1) (n * m)
 Recursión sobre listas
• Recursión lineal

suma :: Num p => [p] -> p

suma [] = 0
suma (x:xs) = x + suma xs

• Recursión de cola

sumaC :: Num t => [t] -> t -> t

sumaC [] a = a
sumaC (x:xs) a = sumaC xs (a+x)
 Cláusula where

La declaración local se utiliza para definir objetos (valores y funciones)

de uso privado dentro de una función.

inversa :: [a] -> [a]

inversa lis = inv_ac lis []
where
inv_ac [] ys = ys
inv_ac (x:xs) ys = inv_ac xs (x:ys)
 Expresiones let
Las expresiones let sirven para ligar identificadores en cualquier lugar y son
expresiones en si mismas, pero son muy locales, así que no pueden extenderse
entre las guardas. Permiten usar el ajuste de patrones.

let <definición> in <expresión>

Los identificadores que se definan en la expresión let son accesibles en la parte

in.

4 * (let a = 9 in a + 1) + 2

[let square x = x * x in (square 5, square 3, square 2)]

(let (a,b,c) = (1,2,3) in a+b+c) * 100

calcBmis xs =
[bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]
 Expresiones case
Se toma una expresión y se reduce a determinados bloques en función al
emparejamiento de patrones que se realiza.

case expresion of
patrón -> resultado
patrón -> resultado
patrón -> resultado
...

describeList :: [a] -> String

describeList xs = "La lista es" ++ case xs of
[] -> "una lista vacía."
[x] -> "una lista unitaria."
xs -> "una lista larga."
Tuplas
 Tuplas

Las construcciones de tuplas tienen la siguiente forma:

(t1, t2, ..., tn)

Cada elemento de la tupla puede ser de distinto tipo.

Funciones para tuplas

fst
snd
zip [1,2,3] [5,5..] => [(1,5),(2,5),(3,5)]
 Manos a la obra

Definir una función que devuelva el tercer elemento de una tupla de

tres elementos.
Listas
 Listas

Las listas constituyen una estructura de datos comúnmente utilizada

en lenguajes funcionales.

La lista [1,2,3]
es realmente una abreviatura de la lista 1:(2:(3:[]))

: es el operador (infijo) que añade un elemento a la cabeza de la lista

[] es la lista vacía
 Listas aritméticas

[1..10] => [1,2,3,4,5,6,7,8,9,10]

[1,3..10] => [1,3,5,7,9]

Secuencia Infinita
[5..] => [5,6,7,8,9,10,11, ... ]
 Listas aritméticas II

[LimInf,Salto..LimSup]

Ejemplos
[2,4..20] => [2,4,6,8,10,12,14,16,18,20]

[3,6..20] => [3,6,9,12,15,18]

[20,18..10] => [20,18,16,14,12,10]

Algunas funciones de Listas

length take
null drop
reverse sum
 Manos a la obra

Definir una función que devuelva la cabeza de una lista cualquiera.

Definir una función que devuelva el último elemento de una lista

cualquiera.

Definir una función myDrop que quite los n primeros elementos de la

lista.
 Ejemplos

Dada una lista de enteros, contar la cantidad

de números 5 que existen en la lista.
cont5 :: (Eq a, Num p, Num a) => [a] -> p
cont5 [] = 0
cont5 (5:xs) = 1 + cont5 xs
cont5 (_:xs) = cont5 xs
Dada una lista, ¿podremos quitar los elementos que coinciden con el
que nos pasan como parámetro?
quita :: Eq a => [a] -> a -> [a]
quita [] _ = []
quita (x:xs) y | x == y = quita xs y
| True = x:quita xs y
 Manos a la obra

Definir una función myTake que quite los n primeros elementos de la

lista.

Probemos luego cómo se comporta con una lista infinita.

 Listas por comprensión
Notación ZF (Zermelo-Fraenkel)
Las listas por comprensión son expresiones del tipo:

[ exp | x <- xs, guardas_booleanas ]

Intuitivamente, esta expresión puede leerse como "la lista de todos las
exp tales que x pertenece a xs y cumplen las condiciones de guarda”

Determina el producto cartesiano de dos listas xs y ys.

[ (x,y) | x <- xs, y <- ys ]

Guardas booleanas… permiten colocar restricciones al generador

[ (x,y) | x <- [1..5],
y <- "frase",
x `mod` 2 == 0, not (y `elem` ['g', 'h'])]
 Ejemplos varios

[f x | x<-xs] = map f xs
[f x | x<-xs, p x] = map f (filter p xs)
[f x y | x<-xs, y<-ys] = concat [[f x y | y<-ys] | x<-xs]
[2 | even 4] = [2]
[2 | 2>3] = []
[x+3 | x <- [1..4]] = [4,5,6,7]
[y | (3,y) <- [(3,2),(5,1),(3,5)]] = [2,5]
[x*x | x <- [1..10], even x] = [4,16,36,64,100]
[x*x | x <- [1..8], even (x+1)] = [1,9,25,49]
 Ejemplos varios II
[(x,y) | x<-[1..2],y<-[1..2]] =[(1,1),(1,2),(2,1),(2,2)]
[x| x<-[1..3],y<-[1..2]] = [1,1,2,2,3,3]
[3*x| letx+2 = 4] = [6]

Ternas de números naturales que cumplen el teorema de Pitágoras (ternas pitagóricas):

tPit n = [(x,y,z) | x<-ns, y<-ns, z<-ns, x*x+y*y==z*z]

where ns = [1..n]

Lista de los números primos:

criba (p:xs) = [x | x <- xs, x `mod` p /= 0]

listaPrimos = map head (iterate criba [2..])
 Observaciones
• Los calificadores pueden utilizar valores generados por calificadores
anteriores:

[(x,y) | x <- [1..3], y <- [x+1..4]]

• Las variables de los calificadores posteriores se imponen sobre las variables de

los calificadores anteriores

[x | x <- [1,2], x <- [3,4]] = [3,4,3,4]

[x | x <- [1..3], let x = 5] = [5,5,5]

• El orden de las guardas y las definiciones locales influyen en la eficiencia de

los cálculos

[(x,y) | x <- [1..3], even x, y <- [1..2]]

[facX + y | x <- [1..3], let facX = fact x, y<-[1,2]]
 Ejemplos

¿Contamos las vocales de una cadena?

sum [1 | x <- "Clase de Haskell",

x `elem` ['a', 'e', 'i', 'o', 'u'] ]

¿Podremos determinar todos los puntos del plano en el rango

[0..10,0..10] que estén por sobre la función identidad: f(x)=x?

[(x,y) | x <- [0..10], y <- [0..10], x>y]

¿Se la podrá generalizar para cualquier función lineal?

¡Trabajamos
en equipo!
 Ejemplos

Armamos la sucesión de Fibonacci?

¿Podremos determinar cuáles son los números triangulares que

tienen una cantidad de divisores propios igual a un número n dado?
https://www.youtube.com/watch?v=D_XKKJKu3IU

¿Cuáles son los puntos del espacio euclídeo de 3

dimensiones en el rango 2×3×4, cuya distancia al
origen (0,0,0) sea mayor que 5?
 Ejemplos

Armamos la sucesión de Fibonacci?

fibo :: [Integer]
fibo = 1 : 1 : [ a+b | (a,b) <- zip fibo (tail fibo) ]

¿Podremos determinar cuáles son los números triangulares que

tienen una cantidad de divisores propios igual a un número n dado?

triang :: [Integer]
triang = 1 : zipWith (+) [2..] triang

divisores :: Integral a => a -> [a]

divisores x = [y | y <- [1..x], mod x y == 0]

triD :: Int -> [Integer]

triD n = [x | x <- triang, length (divisores x) == n]
 Ejemplo

¿Cuáles son los puntos del espacio euclídeo

de 3 dimensiones en el rango 2×3×4, cuya
distancia al origen (0,0,0) sea mayor que
5?

triang = [ (a,b,c) | a <- [0..2],

b <- [0..3],
c <- [0..4],
sqrt (a^2 + b^2 + c^2)
>= 5]
 Funciones Lambda

Funciones anónimas para usarlas por única vez.

 Funciones Lambda

Las lambdas son funciones anónimas que suelen ser usadas cuando necesitamos
una función una sola vez. Normalmente creamos funciones lambda con el único
propósito de pasarlas a funciones de orden superior.

\x -> cuerpo
\x -> \y -> cuerpo
\x y -> cuerpo
inc' :: Integer -> Integer
inc' = \x -> x + 1

suma' :: Integer -> Integer -> Integer

suma' = \x -> \y -> x + y

suma'' :: Integer -> Integer -> Integer

suma'' = \x y -> x + y
 Orden superior

Un lenguaje utiliza funciones de orden superior cuando

permite que las funciones sean tratadas como valores de
1ª clase, permitiendo que sean pasadas como
argumentos de funciones y que sean devueltas como
resultados.
 Filtros

Iteradores
Esquemas
funcionales
Generadores

Plegadores
Transformadores de estructuras
Transformadores de estructuras
 Filtros

Iteradores
Esquemas
funcionales
Generadores

Plegadores
Transformadores de estructuras
Transformadores de estructuras
 Filtros

Funcionales para reducir o filtrar una estructura con la ayuda de un

predicado.

filter :: (a -> Bool) -> [a] -> [a]

filter _ [] = []
filter p (x:xs) | p x = x:xs'
| otherwise = xs'
where xs' = filter p xs

takeWhile = segmento inicial de mayor longitud de una lista cumpliendo p

dropWhile = segmento complementario a takeWhile
takeUntil = elementos hasta el primero que cumple p
 Aplicaciones de filter

Se puede definir una función a partir de otra parcialmente instanciada.

mayores :: Ord a => a -> [a] -> [a]

mayores x = filter (x<)

eliminar :: Eq a => a -> [a] -> [a]

eliminar x = filter (x/=)
 Filtros

Iteradores
Esquemas
funcionales
Generadores

Plegadores
Transformadores de estructuras
Transformadores de estructuras
 Iterador map

Función para aplicación iterada de una función sobre una lista.

map :: (a -> b) -> [a] -> [b]

map f [] = []
map f (x:xs) = f x : map f xs

map cuad [1,2,3,4] = [1, 4, 9, 16]

map impar [1,2,3,4] = [True, False, True, False]
map (*) [1..5] = [(1*), (2*), (3*), (4*), (5*)]
map (suma 3) [1,2,3,4] = [4, 5, 6, 7]
 Iterador zipWith

Toma una función y dos listas y las aplica iteradamente la función entre los
elementos que están en la misma posición de las listas.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

zipWith (+) [2..] [2..10]

[4,6,8,10,12,14,16,18,20]

zipWith (++) ["Bart ", "Lisa ", "Maggie "] (replicate 3 "Simpson")
["Bart Simpson","Lisa Simpson","Maggie Simpson"]
 Iterador until

Función para la aplicación reiterada de una función a un valor hasta

alcanzar un resultado que cumpla una condición p.

until :: (a -> Bool) -> (a -> a) -> a -> a

until p f x | p x = x
| otherwise = until p f (f x)
 Ejemplo

Dada una lista de números, generar una lista

con cadenas de asteriscos, donde la cantidad
de estos coincida con los números de la lista
inicial.

gen :: (Num t, Enum t) => t -> [Char]

gen x = ['*' | _ <- [1..x]]

map gen [1..10]

 Ejemplo

Diseñar una función que separe en dos listas

los valores de la lista que recibe como
parámetro respetando el criterio de una
función.

separa :: (a -> Bool) -> [a] -> ([a], [a])

separa _ [] = ([], [])
separa f (x:xs) | f x = (x:a, b)
| otherwise = (a, x:b)
where (a, b) = separa f xs
 Ejemplo

Diseñar una función valide que todos los

elementos consecutivos de una lista cumplen
con una condición dada por una función.
(listas ordenadas)

ordenada :: (a -> a -> Bool) -> [a] -> Bool

ordenada _ [] = True
ordenada _ [x] = True
ordenada f (x:y:xs) = f x y && ordenada f (y:xs)
 Ejemplo

Diseñar una función que devuelva las tuplas

de números enteros en el rango [0..10x0..10]
que estén justo sobre una función dada.

puntos :: (a -> b) -> [(a, b)]

puntos f = [(x, y) | x<-[0..10], y<-[0..10], y == f x]
 Filtros

Iteradores
Esquemas
funcionales
Generadores

Plegadores
Transformadores de estructuras
 Iterador iterate

Función para generar listas por aplicación reiterada de una función a

un valor dado.

iterate :: (a -> a) -> a -> [a]

iterate f x = x : iterate f (f x)

iterateUntil = arma la lista hasta que se cumpla una condición p

 Ejemplos

• Lista de las potencias de 2.

iterate (*2) 1

• Una función para calcular la suma de los cuadrados de los 10

primeros números naturales.

sum (take 10 (map (\x -> x*x) (iterate (+1) 1)))

 Notación especial para generadores

[n..] iterate (+1) n

[n,m..] iterate (+(m-n)) n

[n..p] takeWhile (<=p) (iterate (+1) n)

[n,m..p] takeWhile ((if m>=n then (>=) else (<=)) p)

(iterate (+(m-n)) n)
 Filtros

Iteradores
Esquemas
funcionales
Generadores

Plegadores
Transformadores de estructuras
 Plegadores
Los pliegues se pueden utilizar para implementar cualquier función que
recorra una lista, elemento a elemento, y luego devuelvan un valor.
Son funciones de orden superior que sintetizan los esquemas recursivos que
se utilizan con las distintas estructuras recursivas.
 Plegador foldr

Plegador por derecha.

Esta función toma otra función f (de dos parámetros), una lista y un
valor de inicio z. Aplica reiteradamente la función f a los elementos de
la lista arrancando por z. Arranca el plegado por el último elemento de
la lista.

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Si hacemos el pliegue sobre la lista [3,4,5,6], básicamente es como

si hiciésemos f 3 (f 4 (f 5 (f 6 z)))
 Plegador foldl

Plegador por izquierda.

Si hacemos el pliegue sobre la lista [3,4,5,6], tomamos g como
función binaria y z como acumulador, sería equivalente a hacer g (g
(g (g z 3) 4) 5) 6.

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl _ z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

Ejemplo:
foldl (\acc x -> x : acc) [] [1..5]
[5,4,3,2,1]
 Plegadores scanl y scanr

scanl y scanr son como foldl y foldr, solo que devuelven todos
los acumuladores intermedios en forma de lista.

scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

scanl (\acc x -> x : acc) [] [1..5]

[[],[1],[2,1],[3,2,1],[4,3,2,1],[5,4,3,2,1]]
 Funciones
polimórficas
 Funciones Polimórficas

Este tipo de funciones muy generales que permiten recibir

parámetros de tipos no determinados (genéricos).

primero :: (a, b) -> a

primero (x, y) = x
 Funciones Polimórficas

Ordenamos una lista con qSort

Elegir un elemento del conjunto de
elementos a ordenar, al que
llamaremos pivote.
Resituar los demás elementos de la
lista a cada lado del pivote, de
manera que a un lado queden todos
los menores que él, y al otro los
mayores. En este momento, el pivote
ocupa exactamente el lugar que le
corresponderá en la lista ordenada.
La lista queda separada en dos
sublistas, una formada por los
elementos a la izquierda del pivote, y
otra por los elementos a su derecha.
El proceso debe repetirse para cada
sublista.
 Funciones Polimórficas

qsort :: Ord a => [a] -> [a]

qsort [] = []
qsort (x:xs) =
qsort smaller ++ [x] ++ qsort larger
where
smaller = filter (<=x) xs
larger = filter (>x) xs

En el caso promedio, la complejidad del algoritmo es O(n·log n).

Composición de
funciones
 Composición de funciones
Definición de composición de función

𝒇. 𝒈 = 𝒇 𝒈 𝒙

(.) :: (b -> c) -> (a -> b) -> a -> c

f . g = \x -> f (g x)
 Composición de funciones. Ejemplo

Negar todos los números de una lista

map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]

[-5,-3,-6,-7,-3,-2,-19,-24]

map (negate . abs) [5,-3,-6,7,-3,2,-19,24]

[-5,-3,-6,-7,-3,-2,-19,-24]
 Composición de funciones
Se pueden componer más funciones

map (negate . sum . tail) [[1..5],[3..6],[1..7]]

[-14,-15,-27]

Si las funciones tienen más de un parámetro, tenemos que aplicarlas

parcialmente de forma que cada función tome un solo parámetro.

sum (replicate 5 (max 6 8))

se puede escribir como:

(sum . replicate 5 . max 6) 8

o
sum . replicate 5 . max 6 $ 8
Redes de Procesos
 Redes de procesos de Kahn (KNP)

Las funciones que consumen y/o producen listas infinitas se puede

considerar que consumen y/o producen flujos de datos y, además, lo
hacen de forma incremental (debido a la evaluación perezosa).

Podemos considerar 3 formatos:

iter = x : iter

iter' = x : map f iter’

iter'' = x : zipWith f [y..] iter''

 Ejemplos de Redes de procesos

Múltiplos de 5
mult5 = 0 : map (+5) mult5

Potencias de 2
pot2 = 1 : map (*2) pot2

Factoriales de enteros
facts = 1 : zipWith (*) [1..] facts

Sucesión de Fibonacci
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
 Extensión del ejemplo

Sucesión de Fibonacci
fibs= 1 : 1 : zipWith (+) fibs (tail fibs)

fibs = 1 : 1 : 2 : 3 : 5 : ...

tail fibs = 1 : 1 : 2 : 3 : ...

Tipos Algebraicos
 Tipos Algebraicos

Se generan mediante la suma directa de otros tipos. Permiten

definiciones de tipos por enumeración, unión disjunta y por recursión

data Tipo{parT} = constr{|constr}*

constr::= tag {Tipo}*

data Color = Red | Green | Blue

data Temp = Cent Float | Fahr Float
data Tree a = Hoja a | Rama (Tree a) (Tree a)
data Dia = Do | Lu | Ma | Mi | Ju | Vi | Sa
 Tipo Maybe

The Maybe type encapsulates an optional value. A value of type Maybe

a either contains a value of type a (represented as Just a), or it is empty
(represented as Nothing). Using Maybe is a good way to deal with
errors or exceptional cases without resorting to drastic measures such
as error.

data Maybe a = Nothing | Just a

Busca un valor en una lista asociativa y devuelve el segundo elemento

de la tupla (si existe).

lookup :: Eq a => a -> [(a, b)] -> Maybe b

 Caso de Estudio
AEF no determinístico
 Un aceptor de estados finitos (AEF) no
determinístico es una tupla de cinco elementos
definida como:

𝑀 = (𝑄, 𝑆, 𝑃, 𝐼, 𝐹)

donde
• 𝑄 es el conjunto finito de estados
• 𝑆 es el alfabeto finito de entrada
Definición • 𝐼 ⊆ 𝑄 son los estados iniciales
• 𝐹 ⊆ 𝑄 son los estados finales
• 𝑃 ⊆ (𝑄 𝑥 𝑆 𝑥 𝑄) son la relación de transición de
M, toda vez que (𝑞, 𝑠, 𝑞′) sea un elemento de P,
luego 𝑞 → 𝑞´es una transición de M rotulado
por 𝑠.
Autómata finito no determinístico que
acepta el lenguaje:
L = { /  ∈ {0, 1}* y  contiene la
subcadena 00 ó x contiene la
subcadena 11}