Imaginemos un mundo libre

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Archive for the ‘Haskell’ Category

Algoritmos de ordenación – Haskell

with 3 comments

Los algoritmos de ordenación, así como los de búsqueda, también son muy estudiados en el área de ciencia de la computación. Básicamente, el trabajo de un algoritmo de ordenación es establecer una relación de orden en una secuencia de elementos. La necesidad de ordenar archivos, datos, etc es una tarea que realizamos muy a menudo en nuestras vidas, por ello la importancia de investigar la eficiencia y complejidad de estos algoritmos.

A continuación vamos a ver algunos algoritmos de ordenación y su implementación en Haskell:

Insert Sort: Se trata de un algoritmo en el que va haciendo comparaciones del primer elemento del vector con el resto y se inserta ese elemento cuando encuentre su ubicación adecuada Es prácticamente un intercambio de elementos hasta que el vector se encuentre ordenado. ESte algoritmo tiene una complejidad en el mejor de los casos de Ω (n) y en el peor de los casos de O(n²). Veamos su implementación y explicación en haskell.

Primero creamos una función que me inserte un elemento dado en una lista en su correcta ubicación, esta función compara el elemento con la cabeza de la lista y si es menor lo inserta delante, caso contrario sigue recorriendo la lista recursivamente. Así:

insert::Ord a => a -> [a] ->[a]
insert e [] = [e]
insert e (x:xs)
| e<=x = e:x:xs
| otherwise = x: insert e xs

Main> insert 5 [1,9,4,7,8,43,34,65,89]
[1,5,9,4,7,8,43,34,65,89]

Como ya tenemos la función que hace ese trabajo, entonces la llamaremos desde otra función para que inserte la cabeza de la lista, en la cola de la misma. Entonces quedaría así:

insertSort::Ord a =>[a] ->[a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)

Main> insertSort [45,23,78,96,22,7,6,14]
[6,7,14,22,23,45,78,96]

El algoritmo insertSort no es tan eficiente comparado a otros, pero se recomienda usarlo con vectores pequeños y cuando es necesario una solución rápida, dada su facilidad de programación.

Quick Sort: Algoritmo que utiliza la técnica divide y vencerás ,es uno de los algoritmos más conocidos y eficientes por su rapidez. Consiste en tomar un elemento pibote y a partir de él generar 2 sublistas una de los menores y una de los mayores a él. Y con cada una de estas sublistas hacer lo mismo, es decir es un algoritmo recursivo. Tiene una complejidad en el mejor de los casos de Ω (n log n) y en el peor de los casos de O(n²). Veamo como es en haskell:

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

Main> quickSort [‘p’,’d’,’g’,’r’,’h’,’s’,’x’,’w’,’l’,’i’,’t’,’y’,’a’,’z’,’e’]
“adeghilprstwxyz”

En este caso tomaríamos a p(cabeza de la lista como nuestro pibote y crearíamos 2 sublistas una de los menores de ‘p’ y otra de sus mayores e iríamos llamando a la función recursivamente para que hagan la misma operación con estas sublistas. Cuando se ha dividido hasta más no poder, entonces se empieza a concatenar los elementos menores con su pibote y con los mayores.

Merge Sort: Este también es un algoritmo que usa la técnica dividde y vencerás.Consiste en dividir el vector dado en 2 vectores, ordenar estos vectores aparte y luego mezclar el resultado de las 2 ordenaciones obteniendo así un nuevo vector ordenado.

Tiene una complejidad en el mejor de los casos de Ω (n) y en el peor de los casos de O(n log n). Veamo como es en haskell: Lo primeros que haremos es crear una función que concatener 2 listas ordenadas y el resultado también sea ordenado, llamaremos a esta función Merge, Veamos:

merge::Ord a =>[a] ->[a] ->[a]
merge [] l2 = l2
merge l1 [] = l1
merge (x:xs) (y:ys)
| x<=y = x : merge xs (y:ys)
| True = y : merge (x:xs) ys

Main> merge [1,3,5,7,9] [2,4,6,8]
[1,2,3,4,5,6,7,8,9]

La función Merge lo que hace es ir comparando la cabeza de las 2 lista. En caso que la cabeza de la x (primera lista) sea menor a la cabeza de y (la segunda lista), entonces concatenamos x con la llamada recurisva a su cola y la lista y. caso contrario concatenamos y con la llamada recursiva a la lista x con la cola de y.

Ahora llamaremos a la función Merge en nuestro algoritmo mergeSort, veamos:

mergeSort::Ord a =>[a] ->[a]
mergeSort [] = []
mergeSort l  = merge (mergeSort izq) (mergeSort der)
where
mitad = (div (length l) 2)
izq = take mitad l
der = drop mitad l

Obtenemos cual es la mitad de la lista para obtener 2 divisiones con igual número de elementos, para ello simplemente dividimos la longitud de la lista (length) en 2. Las funciones take y drop se utilizan para tomar y quitar elementos de una lista, las veremos más adelante. Pero aquí el objetivo es tener 2 listas y después con la función Merge ordenarlas.

Main> mergeSort [1,3,5,7,9,2,4,6,8]
[1,2,3,4,5,6,7,8,9]

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

December 11, 2007 at 6:28 pm

Algoritmos de búsqueda – Haskell

leave a comment »

En la ciencias de la Computación, y la clasificación de algoritmos, los algoritmos de búsqueda son imprescindibles y son una de las operaciones más importantes en el procesamiento de la información ya que continuamente nos vemos en la necesidad de buscar información.

Un algoritmo de búsqueda consiste en buscar en un elemento en una estructura de datos (listas , arrays, matrices, etc) y devolvernos un valor booleano en el caso de la existencia o no del elemento. Los algoritmos de búsqueda tienen 2 objetivos primordiales:

  • Determinar si el elemento buscado se encuentra o no en la estructura.
  • En el caso que se encuentre el elemento, devolver la posición en la que se encuentra.

Ahora veremos la implementación en Haskell de 2 algoritmos de búsqueda muy conocidos:

Búsqueda Secuencial.- Este es un tipo de algoritmo en el cual se explora consecutivamente todos los elementos de un conjunto. La comprobacion se realiza desde el primer elemento hasta el último, en el caso que se encuentre el elemento buscado el algoritmo se detiene. Este algoritmo tiene una complejidad en el mejor de los casos de Ω(1) y en el peor de los casos O(n).

En código haskell:

busSec::Ord a=>[a]->a->Bool
busSec [] _ = False
busSec (x:xs) ele
| x==ele = True
| True = busSec xs ele

Main> busSec [48,59,63,12,45,8,5,36,25,120] 41
False
Main> busSec [48,59,63,12,45,8,5,36,25,120] 25
True

Como lo dije anteriormente con Ord indicamos que ‘a’ puede ser un dato de cualquier tipo. El caso base es si la lista está vacía o no indicamos el elemento a buscar, en estos caso el algoritmo retorna False.

Sino se da el caso base, entonces separamos cabeza y cola y se empieza a preguntar, si el elemento es igual a la cabeza devuelve True, caso contrario que siga buscando recursivamente en la cola hasta encontrarlo. Sencillo no?.

Búsqueda Binaria: Este es un tipo de algoritmo en el cual se parte de la premisa de que una determinada lista de elementos se encuentra ordenada y además de ello se conoce su número de elementos. Este algoritmo tiene una complejidad en el mejor de los casos de Ω(1) y en el peor de los casos O(log n).

En código haskell:

busBin::Ord a=>[a]->a->Int->Int->Bool
busBin [] _ _ _ = error (“please,check your code”)
busBin vector ele ini fin
| ini > fin = False
| ele == vector!!medio = True
| ele > vector!!medio = busBin vector ele (medio+1) fin
| True = busBin vector ele ini (medio-1)
where
medio = (div(ini+fin) 2)

Main> busBin [‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’] ‘f’ 1 25
True
Main> busBin [‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’] ‘ñ’ 1 25
False

Explicaré como funciona:

  1. Es necesario pasarle 4 parámetros a la función busBin: El vector (conjunto de elementos), el elemento a buscar, el inicio y fin del vector, en este caso del abecedario, 1 y 25 respectivamente.
  2. A nosotros nos interesa la posición del elemento que se encuentra en el medio del vector. Para a partir de ello empezar a buscar a su izquierda o a su derecha o detenerse en el caso que el elemento a buscar sea igual al del medio.
  3. El elemento del medio lo calculamos con :(inicio + fin) /2.
  4. El algoritmo pregunta si el elemento a buscar es el del medio, si es asi, simplemente retorna true y se detiene.
  5. Si no, preguntamos si el elemento a buscar es mayor al elemento del medio, entonces volvemos a llamar a la función recursivamente y tendriamos como parámetros: vector ele (medio+1) fin, es decir se buscaría en el vector desde un elemento después del medio hacia la derecha.
  6. En caso contrario, la función tendria como parámetros: vector ele ini (medio-1) , es decir se buscaría desde el inicio hasta un elemento antes del medio.

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

December 10, 2007 at 6:04 pm

Funciones útiles en listas – Haskell

with 2 comments

  • !!: Retorna el elemento ubicado en la posición n, empezando desde cero.
  • head: Retorna el primer elemento de la lista.
  • last: Retorna el último elemento de la lista.
  • tail: Retorna todos los elementos menos el primero.
  • init: Retorna todos los elementos menos el último.
  • length: Retorna el número de elementos de la lista.
  • take: Retorna los primeros n elementos de la lista.
  • drop: Retorna los elementos de la lista, excepto los n primeros.
  • takeWhile : Más potente que take pues puede retornar ciertos tipos de datos indicados.
  • dropWhile: Más potente que drop pues puede retornar ciertos tipos de datos indicados.
  • reverse: Invierte una lista.
  • concat: Toma ciertos elementos o listas y las retorna en una sola lista.
  • words: Retorna una lista de strings de acuerdo a los espacios en blanco de un string.
  • unwords: Retorna un string de una lista de strings.
  • elem: Retorna si un elemento esta o no en la lista
  • notElem: Lo opuesto a elem.

Ejemplos:

Main> [“maritza”,”celeste”,”nadia”,”maria”,”julia”]!!1
“celeste”

Main> head [11,1,1985,22,8,2007]
11

Main> last [11,1,1985,22,8,2007]
2007

Main> tail [11,1,1985,22,8,2007]
[1,1985,22,8,2007]

Main> init [11,1,1985,22,8,2007]
[11,1,1985,22,8]

Main> take 2 [11,1,1985,22,8,2007]
[11,1]

Main> length [11,1,1985,22,8,2007]
6

Main> drop 2 [11,1,1985,22,8,2007]
[1985,22,8,2007]

Main> takeWhile (<=15) [1..30]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Main> dropWhile (<=15) [1..30]
[16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]

Main> reverse [11,1,1985,22,8,2007]
[2007,8,22,1985,1,11]

Main> concat [“open”,”source”,”solutions”]
“opensourcesolutions”

Main> words ” I like to use Debian GNU/Linux”
[“I”,”like”,”to”,”use”,”Debian”,”GNU/Linux”]

Main> unwords [“I”,”like”,”to”,”use”,”Debian”,”GNU/Linux”]
“I like to use Debian GNU/Linux”

Main> elem ‘t’ [‘a’,’f’,’r’,’h’,’t’]
True

Main> notElem ‘t’ [‘a’,’f’,’r’,’h’,’t’]
False

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

December 8, 2007 at 5:16 pm

Listas en Haskell

with 19 comments

Una lista es una estructura de datos que representa un conjunto de datos de un mismo tipo, es muy usada e importante en el lenguaje haskell.

Su declaración es muy simple, ejem:

[Int]: Representa una lista de enteros [4,5,9,25,60 ]

[Char]: Representa una lista de chars [‘l’,’i’,’n’,’u’,’x’]

[Bool]: Representa una lista de valores booleanos [True, False, True]

[String]: Representa una lista de strings [“buenas”,”noches”]

[Float]: Representa una lista de flotantes [2.5,5.8,4.3,7.1 ]

También podríamos definir una lista de listas así: [[Int]], pero eso lo veremos más adelant con el tema de matrices. Una lista vacía se representa [] y algo importante para el manejo de listas es separar el primer elemento (cabeza), del resto(cola) de la sgt manera(x:xs) . X representa la cabeza y xs la cola.

Como Haskell hace mucho uso de la recursividad entonces, debemos tener en cuenta cuando deterne la operación recursiva y para ello necesitamos un caso base.

Vamos a ver algunos ejemplos:

1.- Sumar los elementos de una lista.En este caso, el caso base es que la lista se encuentre vacía y devuelve 0, mientras tanto que siga sumando los elementos con la operación recursiva.

sumar::[Int]->Int
sumar [ ] = 0
sumar (x:xs) = x + sumar(xs)

Main> sumar [5,4,7,8]
24
2.- Invertir una lista: El operador Ord me sirve para indicar que representa a cualquier tipo de dato.

invertir::Ord a=>[a]->[a]
invertir [ ] = [ ]
invertir (x:xs) = (invertir xs)++[x]

Main> invertir [5,4,7,8]
[8,7,4,5]

3.- Comparar si 2 listas son iguales:

igualLista:: Eq a => [a]->[a]->Bool
igualLista l1 l2 = l1 == l2

Main> igualLista [“Hola”,”Mundo”] [“Mundo”,”Hola”]
False

4.- Comprobar si una lista esta ordenada: En este caso ‘y’ representa al 2do elemento de la lista.

lista_ordenada::Ord a=>[a]->Bool
lista_ordenada [] = True
lista_ordenada [_] = True
lista_ordenada (x:y:xs) = (x<=y) && lista_ordenada (y:xs)

Main> lista_ordenada [‘a’,’b’,’c’,’d’]
True

5.- Mostrar el elemento que se encuentra en cierta ubicacion:Como en un array el 1er elemento esta en la ubicacion 0.

mostrar_ubicacion::Ord a=>[a]->Int->a
mostrar_ubicacion l n = l!!n

Main> mostrar_ubicacion [15,25,26,28] 2
26

6.- Mayor elemento de una lista:

mayor::[Int]->Int
mayor (x:xs)
| x > mayor(xs) = x
| otherwise = mayor(xs)

Main> mayor [78,24,56,93,21,237,46,74,125]
237

Listas por comprensión: Son listas que no usan cabeza y cola, sino ciertos argumentos para definir los elementos que pertenecen a ella, de esta manera resolvemos problemas de una manera muy elegante y potente. Ejm: Le decimos a haskell que queremos una lista de elementos x, tales que x este en el rango de 1 a 12.

Main> [x | x <- [1 .. 12]]
[1,2,3,4,5,6,7,8,9,10,11,12]

Apliquemos esto a las operaciones con listas.

1.- Contar cuantos elementos pares hay en una lista. Estamos diciendo que x pertenece a la lista y ademas debe cumplir la condición de ser par. Como en varios lenguajes el length cuenta los elementos.

contarpares::[Int]->Int
contarpares []=0
contarpares lista= length [x | x <- lista, mod x 2 ==0]

Main> contarpares [5,4,7,8]
2

2.- Devolver los cuadrados de una lista:

cuadrados::[Int]->[Int]
cuadrados [ ] = [ ]
cuadrados l = [x*x| x <- l]

Main> cuadrados [1..10]
[1,4,9,16,25,36,49,64,81,100]

3.- Devolver una lista de  numeros primos de 1 a n: Para ello debemos crear nuestra funcion para saber si un numero es primo o no y despues la aplicamos a la lista por comprensión:

divisible::Int->Int->Bool
divisible x y = (mod x y) ==0

divisibles::Int->[Int]
divisibles x = [y | y <-[1..x],divisible x y]

esPrimo::Int->Bool
esPrimo n = length (divisibles n) <=2

primos::Int->[Int]
primos n = [x | x <-[1..n],esPrimo x]

Main> primos 100
[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

December 6, 2007 at 6:17 pm

Haskell y la Programación Funcional

with 6 comments

Despues de tanto tiempo sin postear debido al trabajo y estudios. Mi blog ya estaba llenándose de polvo. Pues hoy quiero hablar brevemente de lo que estoy estudiando en la Universidad: Haskell y Programación Funcional (P.F)

La P.F es un paradigma de programación que se basa en el uso de funciones matemáticas para resolver problemas. Algunos lenguajes de programación funcional son Lisp (El más popular aun usado por muchos programadores) , Scheme, AP, Haskell y Miranda.

Entre las principales características de P.F tenemos:

  • Los bucles se modelan a través de la recursividad ya que no hay manera de incrementar o disminuir el valor de una variable,
  • Definición y evaluación de funciones y variables.
  • Y una cosa realmente interesante de la P.F es que las funciones son consideradas un tipo de dato primitivo. Qué significa esto?.

Primeramente, definimos a un dato primitivo como aquel que puede ser el valor de una variable, argumento de una función o valor que devuelve una función. En otros paradigmas de programación los números, caracteres y cadenas son datos primitivos, sin embargo sus funciones y procedimientos no pueden ser considerados como tal. Entonces podríamos decir que en la PF.podríamos hacer esto:

  • Una función podría tomar como argumentos otras funciones
  • Devolver un procedimiento como resultado de una llamada a otro procedimiento.
  • Tener estructuras de datos que contengan procedimientos como elementos
  • Una variable puede tener como valor un procedimien

No es esto una gran ventaja?. Solo sería cuestión que TÚ lo pruebes y juzgues por tu cuenta. En muchas univesidades e institutos del país aun se sigue enseñando paradigmas como el imperativo y orientación a objetos, pero es interesante probar nuevas cosas y apostar por el cambio.

EL L.P que estamos aprendiendo este semestre en la U es Haskell, un lenguaje funcional puro de propósito general que no goza de mucha popularidad, pero ya tiene un prestigio bien ganado, por algunas características que lo hacen elegante, eficiente y potente para resolver problemas. Más adelante entraremos en detalles.

Quisiera contar como experiencia personal que he programado en PHP desde hace casi 2 años a Ruby lo he investigado tan solo un par de meses y ahora puedo decir que con Haskell he pensado, razonado y hecho funcionar más el cerebro que con los anteriores. El nivel de abstracción, desarrollo de la lógica se producen a grandes niveles en Haskell.

Ahora vamos al grano, queremos jugar con Haskell. Tenemos varias implementaciones del lenguaje, entre las principales tenemos el intérprete HUGS y el compilador GHC. He leído en algunas listas de correo y me han recomendado usar GHC, pero bueno empezemos con algo más liviano y menos sofisticado como es Hugs para empezar a probar.

No perdamos tiempo compilando, y como Debian todo lo tiene y lo que no tiene se lo inventa solo bastaría un: sudo apt-get install hugs , Tecleamos en nuesto terminal hugs y tendremos una salida como esta:
|| || || || || || ||__ Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__|| __|| Copyright (c) 1994-2005
||—|| ___|| World Wide Web: http://haskell.org/hugs
|| || Report bugs to: hugs-bugs@haskell.org
|| || Version: 20050308 _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type : ? for help
Hugs.Base>

Jejeje, sigamos , puedes editar tus programas en consola si deseas, nano, pico, vi,etc, bueno yo prefiero usar el gedit que te aclara muy bien el código. Crearemos nuestro archivo examples.hs y empezemos con un típico ejemplo, una función que me calcule el factorial de un número, tan simple como esto

fact::Int->Int
fact n
| n ==0 = 1
| otherwise = n * fact(n-1)

Recibimos un entero y que nos devuelva otro entero y usamos la recursión para hacer el cálculo. Para probarlo en nuestra consola:

ronny@mentelibre:~/haskell$ hugs examples.hs

Main> fact 5

120

Ohhhhhh que maravilla, fue solo para probar. Ahora queremos una funcion que me halle a^b editamos nuestro examples.hs

potencia::Int->Int->Int
potencia a b
| b ==0 = 1
| a ==1 = 1
| otherwise = a * potencia a (b-1)

Main> :r //para actualizar nuestro archivo y luego

Main> potencia 5 4

625

Ahora vamos a sumar todos los dígitos de determinado número:

suma::Int->Int
suma n

| n < 10 = n
| otherwise = suma(div n 10) + (mod n 10)

Actualizamos con :r y luego

Main> suma 123456789

45

Fueron ejemplos sencilllos de introducción, en los proximos posts emplearemos listas, tuplas, matrices, algoritmos de ordenación, algoritmos de búsqueda y otras cosillas que con Haskell son muy interesantes.

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

November 23, 2007 at 6:14 pm