martes, 10 de junio de 2008

C# es fácil (iv): Expresiones lambda

La inclusión de las expresiones lambda en C#, ha hecho que algunos empiecen a tener escalofríos y sudores fríos, recordando sus tiempos de estudiante de ingeniero informático y el cálculo lambda... Cuando Microsoft anunció, la incorporación de expresiones lambda en C# muchos se empezaron a preguntar si esto era el renacimiento de C# como lenguaje funcional. Al final, como suele suceder, no ha sido para tanto...

En definitiva podemos decir que las expresiones lambda son una sintaxis alternativa para los métodos anónimos (que aparecieron en C# 2.0, o sea Visual Studio 2005). Imaginemos el caso que queremos ordenar una lista, usando el método Sort. El mètodo Sort espera un delegate de tipo Comparison. Este delegate es un delegate genérico que espera dos argumentos de tipo T, y devuelve un int:

public delegate int Comparison<T>(T x,T y);

Si queremos ordenar una lista, usando un método anónimo, haríamos algo parecido a esto:

List<string> lista = new List<string>() { "Perro", "Gato", "Zorro" };

lista.Sort (delegate (string s1, string s2)

{

return s1.CompareTo(s2);

} );

Dentro de la llamada del método Sort, creamos el método anónimo (de tipo Comparison<string>).

Bien, pues básicamente las expresiones lambda son una sintaxis alternativa (muuucho más compacta), para hacer exactamente lo mismo. Fijaros como quedaría el código anterior usando expresiones lambda:

List<string> lista = new List<string>() { "Perro", "Gato", "Zorro" };

lista.Sort ( (x,y) => x.CompareTo(y));

Es una sintaxis mucho más compacta que "la clásica" de métodos anónimos, verdad??? ;-) Pues vamos a comentarla rápidamente...

El operador => es el operador lambda, y la sintaxis és param-list => valor_retorno siendo param-list una lista de parámetros (separados por comas), y valor_retorno una expresión que se evaluará y será el resultado de la expresión lambda.

Veamos otro ejemplo de como las expresiones lambda sustituyen (sintacticamente) a un método anónimo. Imaginemos el delegate:

public delegate T Updater<T> (T value);

Un delegate que toma un objeto de tipo T y devuelve otro del mismo tipo.

En la sintaxis estándard (C# 1.0 sin métodos anónimos) haríamos algo como:

Updater<int> pFoo = new Updater<int>(SumaUno);

donde SumaUno, seria un método definido como algo parecido a:

int SumaUno(int x) { return x + 1; }

Usando métodos anónimos (C# 2.0) la cosa nos queda como:

Updater<int> pFooAnonimo = delegate(int x) { return x + 10; };

Lo cual ya es más compacto que la sintaxis anterior... y usando las nuevas expresiones lambda, la cosa nos queda como:

Updater<int> pFooLambda = x => x + 50;

Más compacto... imposible, no??

Bueno... una cosilla debeis tener presente con las expresiones lambda... C# es un lenguaje fuertemente tipado, y por ello las expresiones lambda tienen tipo... Que nosotros no pongamos tipo en los parámetros de una expresión lambda, no significa que lo tengan, significa que el compilador debe poder deducirlos por el contexto.En este ejemplo que acabo de poner, el compilador deduce que "x" es de tipo int, porque estamos asignando la expresión lambda a un delegate que espera un parámetro de tipo int (y una expresión lambda siempre se asigna a un delegate, y es este delegate quien nos define el tipo de los parámetros). En el otro ejemplo que he expuesto antes (el de la llamada a Sort), el compilador puede deducir que los parámetros x e y son de tipo string, porque estoy llamando a Sort de una List<string> que por lo tanto me espera un delegate de tipo Comparison<string> que define dos parámetros de tipo string.

En resumen: las expresiones lambda son una nueva sintaxis (eso sí, mucho más compacta) para una funcionalidad que ya teníamos: los métodos anónimos en C#.

lunes, 2 de junio de 2008

El método de la burbuja (para ordenar listas, claro).

MMmm... analizando los logs de google analytics, he visto que mucha (mucha de la poca se entiende xD), que entra al blog, lo hace a través de una búsqueda relacionada con... el algoritmo de ordenamiento de la burbuja! Así, que bueno... me he decidido a escribir algo sobre este algoritmo... al menos los pocos que llegan por aquí, que se queden contentos!! ;)

Por quien no conozca este algoritmo, diré que se trata de una forma no muy eficiente de ordenar los elementos de una lista. Eso sí, al menos tiene dos ventajas: és un método sencillo y además es un método sencillo. Y en que consiste???

Pues bueno, supongamos una lista de números, desordenada... por ejemplo 32,4,35,1 y queremos ordenarla de menor a mayor. Para ello cojemos el primer par de elementos (32 y 4) y:

  • Si el segundo es menor que el primero los intercambiamos
  • En caso contrario, los dejamos tal cual.
  • Repetimos el procedimiento, ahora con el segundo y tercer elemento de la lista... hasta llegar al final.
  • Luego volvemos a repetir todo el procedimiento, pero hasta llegar al penúltimo elemento... luego repetimos, pero llegamos hasta el antepenúltimo elemento, y así sucesivamente, hasta tener la lista ordenada.

En nuestro ejemplo (en negrita el par de elementos que comparamos y en cursiva los elementos que quedan fuera de la comparación):

32, 4, 35,1 => 4,32,35,1 => 4,32,35,1 => 4,32,1,35 => Repetimos desde el inicio, pero sin contar el último elemento

4,32,1,35 => 4,32,1,35 => 4,1,32,35 => Repetimos desde el inicio, pero sin contar los dos últimos elementos:

4,1,32,35 => 1,4,32,35 => Fin del algoritmo. Lista ordenada.

Bueno... el código en C# seria algo así como sigue (adaptación del código que podeis encontrar en "la tecla de escape"):

static void Burbuja(List<int> lst)

{

int iaux;

for (int i = 0; i < lst.Count - 1; i++)

{

for (int j = 0; j < lst.Count - i - 1; j++)

{

if (lst[j] > lst[j + 1])

{

iaux = lst[j];

lst[j] = lst[j + 1];

lst[j + 1] = iaux;

}

}

}

}


Qué sencillo, no???? Pues bueno... vamos ahora a hacer que el método ordene, no solo listas de ints, si no listas de cualquier tipo... uno podría pensar que igual basta declarar el método genérico... Lamentablemente si declaramos el método como:

static void Burbuja<T>(List<T> lst)

{

T iaux = default(T);

// El resto todo igual que antes...


El método no compila... el compilador se queja diciendo: Operator '>' cannot be applied to operands of type 'T' and 'T'. Este error es debido a que los parámetros genéricos son tratados como de tipo object... y el operador > no está definido para tipos object. Además usar una clausula where, no nos sirve en este caso (ya que where nos permite indicar que el parámetro template debe satisfacer una determinada interfaz, pero los operadores siempre se declaran como static en C# y por lo tanto nunca pueden declararse en una interfaz).

Entonces... estamos atrapados? Pues no... la solución pasa por usar un parámetro extra en nuestro método Burbuja, que le indique como debe ordenar los elementos. Es decir, un parámetro que le indique a nuestra función Burbuja, que método debe usar (en lugar de operador '>') para determinar si un elemento es "mayor" que otro. Además, eso es incluso más lógico que usar el operador '>', puesto que imaginemos que tenemos una lista de perros... igual nos interesa ordenarlos por tamaño, pero quizá lo queremos hacer por raza o color del pelo... entonces si tenemos que pasar un parámetro que apunte a un método... necesitamos un delegate.

Así deberiamos declarar un delegate que fuese algo parecido a:

delegate int Comparador<T> (T a1, T a2);


En este caso asumiremos que el delegate nos devuelve 1 si a1 es "mayor" que a2 y -1 si es al revés.

Y usar nuestro método Burbuja como sigue:

delegate int Comparador<T> (T a1, T a2);

class Program

{

static int ComparaDoubles(double d1, double d2)

{

if (d1 == d2) return 0;

return d1 > d2 ? 1 : -1;

}

static void Main(string[] args)

{

List<double> lista = new List<double>() { 32.3, 4.1, 35.2, 1.09 };

Burbuja(lista, new Comparador<double>(Program.ComparaDoubles));

}

static void Burbuja<T>(List<T> lst, Comparador<T> comparador)

{

T iaux = default(T);

for (int i = 0; i < lst.Count - 1; i++)

{

for (int j = 0; j < lst.Count - i - 1; j++)

{

if (comparador(lst[j], lst[j + 1]) == 1)

{

iaux = lst[j];

lst[j] = lst[j + 1];

lst[j + 1] = iaux;

}

}

}

}

}


Ale... solo teneis que cambiar el método al que apunta el delegate y podeis ordenar lo que os de la gana!

Bueno... y ahora que os he soltado el rollo... dos cosillas:

  1. El framework ya define un delegate como nuestro "Comparador", y se llama Comparison.
  2. La clase List<T> tiene un método Sort, que espera como parámetro... un delegate de tipo Comparison... :)

O sea que si quereis ordenar listas, lo mejor es algo del estilo:

lista.Sort (delegate (double d1, double d2)

{

if (d1 == d2) return 0;

return d1 > d2 ? 1 : -1;

} );


Bueno... espero que al menos los que aterrizais por aquí buscando información sobre el método de la burbuja... os haya servido este post!

Nos leemos! ;)