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 December 2007

Migrations

leave a comment »

Rails has a great feature called migrations which allow the developer to have control over the database schema by using ruby code and avoiding use the conventional SQL language. But, more important is that the developer can apply certain changes to move a database from one state to another,  add-remove columns, indexes,  tables etc.  By using migrations you can get different versions of your database structure.

How it works? Migrations are files found in the db/migrate directory and have a sequence number in the filename.

For example, each time you want to add a migration you can generate it with:

./script/generate migration CreateCompanies

exists  db/migrate
create  db/migrate/001_create_companies.rb
Loaded suite ./script/generate
Started
Finished in 0.002254 seconds.
0 tests, 0 assertions, 0 failures, 0 errors

If you see the file, this was generated for you:

class CreateCompanies < ActiveRecord::Migration
    def self.up

    end

    def self.down

    end
end

and now you can modify it to create a table, the syntax is the folowing:

class CreateCompanies < ActiveRecord::Migration
    def self.up
        create_table :companies do |t|
            t.string    :name
            t.text      :description
            t.datetime  :created_on
            t.timestamps
        end
    end

    def self.down
        drop_table :companies
    end
end

I think the code is explained implicity.  It’s similar to an sql creation,  but this time you have to add the datatype first and then the column name.

Possible Column types:
:string, :text, :integer, :float, :datetime, :timestamp, :time, :date, :binary, :boolean

Column details:
:limit: Maximum long characters in the column (for types :string, :text, :binary or :integer)
:default: Specify the default value of the column.
:null: Enable or disable the value NULL in a column.

To get this table created, just you have to run the command: rake db:migrate and the companies table will be created.

Imagine you want to create another table users, generate it with:

./script/generate migration CreateUsers

exists  db/migrate
create  db/migrate/002_create_users.rb
Loaded suite ./script/generate
Started
Finished in 0.002254 seconds.
0 tests, 0 assertions, 0 failures, 0 errors

Modify the file 002_create_users.rb

class CreateUsers < ActiveRecord::Migration
    def self.up
        create_table :users do |t|
            t.string   :login
            t.string   :email
            t.string   :password,   :limit => 20
            t.datetime :created_at
            t.datetime :updated_at
            t.integer  :status
            t.datetime :last_login
            t.timestamps
        end
    end

    def self.down
        drop_table :users
    end
end

and if you run rake again db:migrate table users will be created in your database. You are probably wondering how rails knows next migration should be named 002 and when running rake db:migrate which migration has to be executed.

Whenever doing these operations rails checks in your database a table called schema_info, which has the latest version of your database schema.  So, that way rails knows which migration number to apply or generate.

Try to run again rake db:migrate and you will receive an error message

Mysql::Error: Table ‘users’ already exists:

telling you that table users already exists.  This is because this migration was already executed and in your schema_info table the version is 2 (the same as the number of your migration). Now you can realize what the pattern is.  Also you can execute an specific migration by running:

rake db:migrate version= version_number

version_number is the version you want to be executed.

When developing your rails application you will see that migrations are very useful because you are database-independent, can change to one version or another and undo changes easily.
Thanks for your visit to the blog. You can follow me on Twitter:

Advertisements

Written by Ronny Yabar

December 15, 2007 at 9:41 pm

Posted in Ruby on Rails

Tagged with ,

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