Metonymie.com :: Apuntes » Programación Funcional
Bloque de Colores

foldr, foldl, scanl, scanr

Icono de Post August 13 2009 :: Haskell, Programación Funcional ::

Foldr y Foldl

foldr y foldl son funciones de plegado sobre la estructura recursiva de las listas.

Cumpliendose que:

foldr f z (x1 : (x2 : (… : (xn : []))))

= x1 ‘f’ (x2 ‘f’ (… ‘f’ (xn ‘f’ z))))

foldl f z (x1 : (x2 : (… : (xn : []))))

= ((((z ‘f’ x1) ‘f’ x2) … ‘f’ xn-1) ‘f’ xn)

En ambas se toma una función y se la aplica sucesivamente a cada miembre de una lista, hasta recibir un resultado final.

Ejemplos. Definición de una función and que devuelve True si todos los elementos de una lista de Bool son verdaderos y definición de una función or que devuelve True si alguno es verdadero.


and3 :: [Bool] -> Bool
and3 = foldr (&&) True

or3 :: [Bool] -> Bool
or3 = foldr (||) False

scanl y scanl, devuelven los pasos intermedios de una operación de foldl y foldr respectivamente. Los siguientes ejemplos demuestran que si una operación no es asociativa (como la resta en los naturales) foldr y foldl devuelven resultados distintos.


*Main> scanl (+) 0 [1..5]
[0,1,3,6,10,15]
*Main> scanr (+) 0 [1..5]
[15,14,12,9,5,0]

*Main> scanr (-) 0 [1..5]
[3,-2,4,-1,5,0]
*Main> scanl (-) 0 [1..5]
[0,-1,-3,-6,-10,-15]

El segundo argumento es el caso final o primero a aplicarse.


*Main> scanl (*) 10 [1..5]
[10,10,20,60,240,1200]
*Main> scanr (*) 10 [1..5]
[1200,1200,600,200,50,10]

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on foldr, foldl, scanl, scanr

Funciones de Orden Superior Y Combinadores

Icono de Post May 19 2009 :: Haskell, Programación Funcional ::

Una función de orden superior es una función que devuelve otra función.

Un Combinador es un función de orden superior que encapsula un determinado comportamiento de una clase de funciones y provee un template para la creación de estas. Ej:


iter :: (Integer -> Integer -> Integer) -> Integer -> ( Integer -> Integer )
iter op e = fun
	where 
	fun 0	= e
	fun m@(n + 1) = op m (fun n)

factorial :: Integer -> Integer
factorial = iter (*) 1

sumatorio :: Integer -> Integer
sumatorio = iter (+) 0

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on Funciones de Orden Superior Y Combinadores

Un poco de Análisis en Haskell

Icono de Post May 18 2009 :: Análisis, Haskell, Programación Funcional ::

Teniendo en cuenta que:

Derivada   f   x = lim h   0   f   ( x + h ) f   x h

Se puede hacer una definición de la función derivada en Haskell como:


derivada :: (Double -> Double) -> Double -> Double
derivada f x = ( f(x + h) - f x ) / h
		where h = 0.0001

Considerando que la derivada de f(x) = x2 es f'(x) = 2x, testeamos la definición:


*Main> derivada (x -> x^2) 2
4.0001000000078335

Afinando la definición de h:


derivada :: (Double -> Double) -> Double -> Double
derivada f x = ( f(x + h) - f x ) / h
		where h = 0.00000000001

Da como resultado:


*Main> derivada (x -> x^2) 2
4.000000330961484

Independientemente ( o más bien a pesar ) de los problemas Inherentes a la aritmetica de punto flotante, se ve que Cuando h tiende a 0 más se acerca al resultado esperable.

Aplicación Parcial (Currying)

Se puede usar la definición de derivada anterior para producir una función y no un resultado, ej:


casiPor2 :: (Double -> Double)
casiPor2  = derivada (x -> x^2)

Que si bien no es equivalente a x -> 2 * x, (por los problemas de la aritmetica de punto flotante), se le acerca.

Una versión de testeo con diversos niveles de acercamiento.

Esto es interesante para entender gráficamente el concepto de limite.


derivada3 :: (Double -> Double) -> Double -> Double ->Double
derivada3 f x h = (f(x + h) - f x ) / h

tiendeA0 :: Double -> [Double]
tiendeA0 h = h : ( tiendeA0 (h*0.1) )

Testeo de tender a 0:


*Main> take 10 (tiendeA0 1)
[1.0, 0.1, 1.0000000000000002e-2, 1.0000000000000002e-3, 1.0000000000000003e-4, 1.0000000000000004e-5, 1.0000000000000004e-6, 1.0000000000000005e-7, 1.0000000000000005e-8, 1.0000000000000005e-9]

Ahora considerando que: f(x) = x^3 => f'(x) = 3x^2 y En particular si x=2, f'(x) = 3x^2 = 3.4 = 12; podemos probar su aplicación para ver el comportamiento extraño del punto flotante.


*Main> map ( derivada3 (x -> x^3) 2 ) (take 10 (tiendeA0 1))
[19.0, 12.61000000000001, 12.060099999999705, 12.006000999999596, 12.000600010022563, 12.00006000026121, 12.000006002210734, 12.000000584322374, 11.999999927070343, 12.000000992884447]

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Calculus; M. Spivak; Editorial Reverte; 1992

Algebra de Boole Aplicada a Circuitos de Computación; M. C. Guinzburg; Biblioteca Técnica Superior; 1998

Autor: Emiliano Martínez Luque.

Comments Off on Un poco de Análisis en Haskell

Haskell: Sintaxis Basica II

Icono de Post May 18 2009 :: Haskell, Programación Funcional ::

Algunos detalles más de Sintaxis de Funciones: Uso de Where, de Let y definición de listas por comprensión.

Ej: una función que tomando una cantidad de segundos devuelve las horas, minutos y segundos que representa (Ejercicio 2.26 de Razonando con Haskell)-


aHoras:: Integer -> ( Integer, Integer, Integer )
aHoras x = ( horas, minutos, segundos )
	where
	m = div x 60
	h = div m 60
	segundos = mod x 60
	minutos = mod m 60
	horas = mod h 60

Otro Ej: un listado (no muy eficiente) de los números perfectos. (Ejercicio 6.19)


divideA :: Integer -> Integer -> Bool
divideA x y = mod x y == 0

divisoresDe :: Integer -> [Integer]
divisoresDe n = [x | x <- [1..(n-1)], divideA n x]


perfecto :: Integer -> Bool
perfecto x = suma == x
		where
		ds = divisoresDe x
		suma = sum ds

perfectos :: [Integer]
perfectos = [x | x <- [0..], perfecto x ]

Otra posible definición usando let.


perfectos2 :: [Integer]
perfectos2 = [x | x <- [0..], let ds = divisoresDe x, let suma = sum ds, x == suma]

Listas por extensión, Las ternas pitagóricas (Ejemplo 6.20):


ternasPit :: Integer -> [(Integer, Integer, Integer)]
ternasPit n = [(x,y,z) | let ns = [1..n], x <- ns, y <- ns, z <- ns, x^2 + y^2 == z^2 ]

Una definición de Quicksort (Ejemplo 6.10.3)


quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (p:xs) = quickSort menores ++ [p] ++ quickSort mayores
		where 
			menores = [x | x <- xs, x < p ]
			mayores = [x | x <- xs, x >= p ]

Otra definición de Quicksort más eficiente (Ejercicio 6.30)


partirPor :: Ord a => (a -> Bool) -> [a] -> ([a], [a])
partirPor f [] = ([], [])
partirPor f [x] | f x = ([x], [])
		| otherwise = ([], [x])
partirPor f (x:xs) 	| f x = (x:ys, zs)
			| otherwise = (ys, x:zs)
			where
				(ys, zs) = partirPor f xs
{-
*Main> partirPor even [1..10]
([2,4,6,8,10],[1,3,5,7,9])
-}

quickSort2 :: Ord a => [a] -> [a]
quickSort2 [] = []
quickSort2 (p:xs) = quickSort2 menores ++ [p] ++ quickSort2 mayores
		where 
			(menores, mayores)= partirPor (x -> x < p) xs 

Trabajando con Funciones como argumentos.

Una función que recibe una lista de funciones y un entero, devuelve la lista de resultados. (Ejercicio 2.28)


(|>)::[Integer -> Integer] -> Integer -> [Integer]
(|>) [] x = []
(|>) (f:fs) x = f x : (|>) fs x

Se puede probar con expresiones lambda:


Main> (|>) [(x -> x * 10), (x -> x +10), (x -> x*20)] 5
[50,15,100]

Una función que devuelve el primer elemento de una lista que cumple con una determinada condición. (Ejercicio 6.18)


primeroQue :: (a -> Bool) -> [a] -> a
primeroQue f (x:xs) 	| f x == True = x
			| otherwise = primeroQue f xs

Seudónimos

La función:

factorial :: Integer -> Integer
factorial 0 = 1
factorial (n + 1) = (n + 1) * factorial n

puede escribirse como:

factorial :: Integer -> Integer
factorial 0 = 1
factorial m@(n + 1) = m * factorial n

donde m = ( n + 1).

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on Haskell: Sintaxis Basica II

Lazy Evaluation ( Evaluación perezosa ) en Haskell

Icono de Post August 4 2008 :: Algebra, Haskell, Programación Funcional ::

Del capitulo 3 de The Haskell Road To Logic, Math and Programming:



sieve :: [Integer] -> [Integer]

sieve (0:xs) = sieve xs

sieve (n : xs) = n : sieve ( mark xs 1 n )

	where

	mark :: [Integer] -> Integer -> Integer -> [Integer]

	mark (y:ys) k m | k == m 	= 0 : (mark ys 1 m)

					| otherwise = y : (mark ys (k+1) m)

LLamando a la función con sieve [2..] , nos retorna los números primos por el método de Criba de Eratosthenes.

Lo interesante es pensar en como la lista infinita que se le paso como parámetro es evaluada por Haskell. Si pensamos desde una perspectiva de programación imperativa, es imposible que una función sea procesada por otra función hasta que no haya terminado su procesamiento, entonces como es posible que sieve devuelva resultados si en este caso mark devuelve una lista infinita. Este es un ejemplo de Lazy Evaluation y una muy buena explicación se puede encontrar acá y con más profundidad acá.

Ejercicio 3.39 de THRTLMP

Agrego este ejercicio porque me gusto y es otro ejemplo de Lazy Evaluation. Se nos pide refutar la afirmación de que si p1, p2, … , pk son todos los números primos menores a n, entonces ( p1 . p2 . … . pk ) + 1 es también primo, para todo n perteneciente a los naturales.



filterMinor :: [Integer] -> Integer -> [Integer]

filterMinor [] _ = []

filterMinor (x:xs) n 	| x >= n	= []

			| otherwise = x : filterMinor(xs) n



proveSTforN :: Integer -> Bool

proveSTforN n = prime (product( filterMinor (sieve [2..]) n ) + 1)



proveST :: Bool

proveST = all (==True) (map proveSTforN [1..])

Y para ver los resultados:



proveSTforNShow :: Integer -> (Integer, Integer, Bool)

proveSTforNShow n = (n, a, prime(a)) 

		where

		a = product( filterMinor (sieve [2..]) n ) + 1



proveSTShow :: [(Integer, Integer, Bool)]

proveSTShow = map proveSTforNShow [2..]

Una curiosidad de Haskell

Icono de Post June 17 2008 :: Haskell, Lógica, Programación Funcional ::

En el ejemplo del capitulo 2.8 de The Haskell Road To Logic, Math and Programming, la formula:

∀x ∈ {1,2,3} ∃y ∈ {1,4,9} x = y2

Se codifica como:


every, some :: [a] -> (a -> Bool) -> Bool
every xs p = all p xs
some xs p = any p xs
every [1,4,9] (x -> some [1,2,3] (y -> x = y^2))

Después en el Ej 2.51 se propone definir una función unique :: (a -> Bool) -> [a] -> Bool
que retorne True para unique p xs solo cuando haya un solo elemento de xs que cumpla con p.

La forma obvia de resolverlo es:


unique :: (a -> Bool) -> [a] -> Bool
unique p [] = False
unique p xs = length(filter p xs) == 1

Que se puede testear con:


unique (x -> x>4) [1,2,3,4,5]
True
unique (x -> x>4) [1,2,3,4,5,6]
False

Sin embargo es interesante pensarlo en la formula de Russell para Unicidad: ∃x ( Φ(x) ∧ ∀y ( Φ(y) => x=y ) ) . Que se puede hacer como:


unique1 :: (Eq a) => (a -> Bool) -> [a] -> Bool
unique1 p xs = some xs (x -> p x && every xs (y -> p y ==> x == y))
unique1 (x -> x>4) [1,2,3,4,5]
True
unique1 (x -> x>4) [1,2,3,4,5,6]
False

Lo interesante es que usando expresiones lambda llegamos a una formula que expresa prácticamente idéntica la original.

Autor: Emiliano Martínez Luque.

Comments Off on Una curiosidad de Haskell

Haskell: Sintaxis Básica

Icono de Post May 10 2008 :: Haskell, Programación Funcional ::

Tipos y Funciones

:t Muestra el tipo de datos

Las funciones son tipos de datos (pensar en definición matematica)


mas2 a = a+2

:t mas2
mas2 :: (Num a) => a -> a

Debe leerse como si a es numérico, entonces, mas2 es una función de a en a. Pensar en f: A -> A

Para forzar un tipo, lo declaro al principio:


multiploDe2 :: Int -> Bool
multiploDe2 a = rem a 2 == 0

Funciones con mas de una variable.


multiplo :: (Integral a) => a -> a ->
Boolmultiplo a b = rem a b == 0

Para comprender mejor:


:t multiplo 10
multiplo 10 :: (Integral t) => t -> Bool

(O sea que al llenar la primer variable se retorna una función de el tipo de la segunda variable al tipo de retorno.)

Sintaxis de Funciones

Función definida en diferentes casos:


fibonacci :: Int -> Int
fibonacci a		| a < 1				= error "Indefinida para ese valor"
			| a == 1 || a == 2 		= 1
			| otherwise			= fibonacci (a-1) + fibonacci (a-2)

Otra forma es:


prefix :: String -> String -> Bool
prefix [] ys			= True
prefix (x:xs) []		= False
prefix   (x:xs) (y:ys)		= (x==y) && prefix xs ys

O una combinación


substring :: String -> String -> Bool
substring xs []	= False
substring xs (y:ys)		| prefix xs (y:ys) = True
				| otherwise = substring xs ys

Construcción de Conjuntos a partir de listas

Un ejemplo, el conjunto de los pares. x = 2k; k ∈ N


pares = map (*2) [1..]

Otro ejemplo Primos y compuestos (del libro)


prime :: Integer -> Bool
prime n			| n < 1		= error "not positive integer"
			| n == 1		= False
			| otherwise		= ldp n == n

ldp :: Integer -> Integer
ldp = ldpf primes

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n				| rem n p == 0			= p
					| p^2 > n 			= n
					| otherwise			= ldpf ps n

primes :: [Integer]
primes = 2 : filter prime [3..]

composite :: Integer -> Bool
composite n = not (prime n)

composites :: [Integer]
composites = 4 : filter composite [5..]

Operadores Infix


(-) 5 3 ≡ 5 - 3
rem 10 3 ≡ 10 `rem` 3

Definición de un operador Infix ( “|” y “/” ya están definidos en prelude por eso use “//” )


divide :: Int -> Int -> Bool
divide a b = rem b a == 0

infix 1 //
(//) :: Int -> Int -> Bool
a // b = divide a b

Funciones auxiliares dentro de funciones


solveQdr :: Float -> Float -> Float -> (Float, Float)
solveQdr a b c		| a == 0		= error "No es Quadratica"
			| d<0			= error "No hay solucion en los Reales"
			| otherwise 		= ( (-b + sqrt d ) / 2*a, (-b - sqrt d ) / 2*a)
					where d = (b^2)-(4*a*c)

Otra opcion (let … in)


solveQdr :: Float -> Float -> Float -> (Float, Float)
solveQdr a b c     = if a == 0 then error "No es Quadratica"
          else let d = b^2 - 4*a*c in
		  if d<0 then error "No hay solucion en los reales"
		  else ( (-b + sqrt d ) / 2*a, (-b - sqrt d ) / 2*a)

Expresiones Lambda

Uso Básico


por2 :: Integer -> Integer
por2 = ( x -> x*2 )
(x -> x+1) 8
9

Pasaje de una expresión Lambda como parámetro a una función (es como pasar una función)


infix 1 ==>
(==>) :: Bool -> Bool -> Bool
True ==> x = x;
False ==> x = True;

infix 1 <=>
(<=>) :: Bool -> Bool -> Bool
x <=> y = x == y
infixr 2 <+>
(<+>) :: Bool -> Bool -> Bool
x <+> y = x /= y

{- Equivalencias logicas -}
logEquiv1 :: (Bool -> Bool) -> (Bool -> Bool) -> Bool
logEquiv1 bf1 bf2 = (bf1 True <=> bf2 True) && (bf1 False <=> bf2 False)

logEquiv2 :: (Bool -> Bool -> Bool) -> (Bool -> Bool -> Bool) -> Bool
logEquiv2 bf1 bf2 = and [(bf1 p q <=> bf2 p q) |    p <- [True, False],
                            q <- [True, False]]

logEquiv3 :: (Bool -> Bool -> Bool -> Bool) -> (Bool -> Bool -> Bool -> Bool) -> Bool
logEquiv3 bf1 bf2 = and [(bf1 p q r <=> bf2 p q r) |    p <- [True, False],
                            q <- [True, False],
                            r <- [True, False]]

{- Idempotencia -}
logEquiv1 (p -> p) (p -> p || p)
True

{- Doble Negación -}
logEquiv1 (p -> p)  (p -> not (not p))
True

{- De Morgan -}
logEquiv2 (p q -> not (p && q)) (p q -> not p || not q)
True

{- Contrareciproco -}
logEquiv2 (p q -> p ==> q) (p q -> not q ==> not p)
True

{- Distributiva -}
logEquiv3 (p q r -> (p || q) && r) (p q r -> (p && r) || (q && r))
True

Expresiones mas complejas


every , some :: [a] -> (a -> Bool) -> Bool
every xs p = all p xs
some xs p = any p xs

(x -> some [1,2,3] (y -> x==y^2)) {-  Verifica si un numero es el cuadrado de 1, 2 o 3 -}
(x -> some [1,2,3] (y -> x==y^2)) 4
True

:t (x -> some [1,2,3] (y -> x==y^2))
(x -> some [1,2,3] (y -> x==y^2)) :: (Num a) => a -> Bool

every [1,4,9] (x -> some [1,2,3] (y -> x==y^2))
True

List comprehension, And, Or


{- valid 3 por List comprehension -}
valid3 :: (Bool -> Bool -> Bool -> Bool) -> Bool
valid3 bf = and [ bf p q r |    p <- [True, False],
                q <- [True, False],
                r <- [True, False] ]
{- and es Conjuncion generalizada sobre una lista (Retorna True si todos son True),
p <- Es List Comprehension

:t and
and :: [Bool] -> Bool

Existe tambien or que es Disyunción generalizada sobre la lista. (Retorna True si al menos uno es True)
-}

Otra forma.


[ x | x <- [1..10], prime (x+5)]
[2,6,8]

Composición de Funciones


por3 :: Int -> Int
por3 x = x*3

divisiblePor2 :: Int -> Bool
divisiblePor2 x = rem x  2 == 0

:t (divisiblePor2 . por3)
(divisiblePor2 . por3) :: Int -> Bool

(divisiblePor2 . por3) 4
True

(divisiblePor2 . por3) 5
False

Referencias

Capitulo 1,2,3 de The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

Autor: Emiliano Martínez Luque.

Comments Off on Haskell: Sintaxis Básica