Category Archives: Programación

Escritos sobre código, algoritmos y lenguajes de programación

Applicative Functors

Como mencioné en el escrito anterior de esta serie, los Applicative Functors son extensiones naturales de los Functors. ¿Cuál es la diferencia entonces?

Cuando hablamos de Functors, especificamos que estos saben cómo aplicar una función a los elementos que contienen, y el resultado queda “envuelto” en otro Functor del mismo tipo (lo que se conoce como endomorfismo). Pero ¿qué pasa si la función que queremos aplicar está contenida dentro de un Functor?

Recordemos que un para mapear una función en un Functor (levantarla a su contexto), la definición es:

map (f: A => B): F[A] => F[B]

Se puede apreciar que f es simplemente una función que toma valores de tipo A y regresa valores de tipo B; la función no está contenida en ningún contexto. Entonces, si tenemos algo como:

(f: F[A => B]): F[A] => F[B]

no concuerda con lo que map espera, puesto que la función ya está dentro del Functor, y map espera que no lo esté.

Los applicative entran en escena aquí. Definidos en una typeclass, definen 2 operaciones básicas:

Continue reading Applicative Functors

Functors – Más detalles

Ya he mencionado un poco acerca de Functors cuando hablé de Monads. Aquí ampliaré un poco al respecto.

Matemáticamente hablando, un functor es un tipo de “mapeo” entre categorías… sí, esa definición no ayuda mucho. Supongamos que tenemos dos conjuntos C y D, y objetos X que pertenecen a C.  Un functor F asocia a esas X con un objeto F(X) que pertenece a D (tomado tal cual de la definción en Wikipedia). Si hablamos de morfismos, asocia X -> Y que pertenecen a C con F(X) -> F(Y) que pertenecen a D.

functor

Muchas matemáticas de por medio…

En lo que concierne a programación funcional, un functor es una typeclass cuyos miembros deben saber mapear un morfismo que toma un valor y lo transforma en otro, sin tener que “sacarlo” para aplicarlo. Esos “morfismos” son simplemente funciones que toman un argumento del tipo de datos que envuelve el Functor y regresan otro tipo de datos (que puede ser que sea el mismo).

Demasiada confusión…

Continue reading Functors – Más detalles

Semigrupos y monoids

Una vez que hemos entendido lo que son las typeclasses y cómo implementarlas en Scala, lo que sigue es hablar de abstracciones,

Muchos programadores se asustan cuando leen algo que tiene que ver con teoría de categorías o matemáticas abstractas; después de todo, se puede programar bien sin meterse en tantos líos. No obstante, hay un principio que todo programador conoce: DRY (Don’t Repeat Yourself), que básicamente se refiere a no repetir el mismo código en diferentes partes; de hecho, es de lo más importante que se aprende cuando se aprende programación estructurada: si vas a usar una serie de instrucciones en más de un lugar, mejor júntalas, ponlas en un método por separado y mándalo llamar cada vez que lo necesites con los datos que necesites procesar. Simple.

Las abstracciones matemáticas son exactamente lo mismo, solamente llevado a más alto nivel: si existe un patrón que se repite constantemente en diferentes programas, ¿por qué no abstraerlo en código separado y llamarlas con los datos necesarios?

Continue reading Semigrupos y monoids

Composición de funciones en Scala

La idea principal en programación funcional es llevar a cabo el proceso mediante la aplicación de funciones sin guardar estado (sin modificar los valores originalmente proveídos). Por ello, y al igual que en álgebra, es posible crear una función compuesta, que no es nada más que la aplicación sucesiva de dos funciones. Obviamente, hay que tener cuidado en que el valor de retorno de la primera función sea del tipo del argumento que la segunda función espera.

Wikipedia muestra una imagen que ilustra claramente el concepto de composición de funciones.

Compfun

La composición de funciones se define con el signo ・, que indica que la primera función se aplica al resultado de aplicar la segunda función al parámetro recibido. Usando el ejemplo de la imagen y definiendo h = g ・f, tenemos que h(a) = @, puesto que h se define aplicando g(f(a)).

El mismo concepto se aplica en programación funcional. Supongamos que tenemos las siguientes funciones:

 def toInt(s: String) = s.toInt
 def addOne(i: Int) = i + 1
 def by4(i: Int) = i * 4

Scala tiene 2 operadores para componer funciones: compose y andThen. La diferencia es que mientras f compose g es f(g(x)), f andThen g es g(f(x)). Por tanto, si queremos definir una función que primero convierta la cadena recibida en entero y después le sume uno a ese entero, podemos hacerlo de dos formas:

  /*
    With compose:
    composed1 = addOne(toInt(x))
   */
  val composed1 = addOne _ compose toInt

  /*
    With andThen
    composed2 = addOne(toInt(x))
   */
  val composed2 = toInt _ andThen addOne

Es entonces fácil ver que estas 2 funciones compuestas (composed3 y composed4) no son lo mismo:

val composed3 = addOne _ compose by4
val composed4 = addOne _ andThen by4

Aplicando las funciones compuestas definidas:

val strFunctions = List(composed1, composed2)
val intFunctions = List(composed3, composed4)

strFunctions foreach (f => println(f("3")))
intFunctions foreach (f => println(f(4)))

Y los resultados son:

4
4
17
20

El concepto de composición de funciones es realmente muy simple, y facilita mucho la creación de nuevas funciones basadas en algunas que ya tengamos definidas.

Como nota adicional, en Haskell es mucho más fácil crear una función compuesta, ya que solo es necesario usar “.”:

import Control.Monad

main = do
 f ← liftM(composed1) $ getLine
 print f
 where composed1 = addOne . toInt
 
addOne ∷ Int → Int
addOne = (+1)

toInt ∷ String → Int
toInt x = read x ∷ Int

El “.” en Haskell funciona como el compose en Scala; además, hay diferentes formas de hacer un programa como el de arriba, pero en este caso escogí usar liftM.

Cabe mencionar que en Scala también es posible componer 2 funciones monádicas en una usando algo llamado composición Kleisli, pero hay que usar Scalaz para tener acceso a ella. Y no es necesario entender teoría de categorías para usarlas; simplemente hay que cuidar los parámetros y los tipos de datos que regresan las funciones.  Esto es tema de otro post, pero lo pongo aquí por si alguien se interesa pueda ir investigando por su cuenta.

Detectando si hay monitor conectado en el puerto HDMI con Haskell

Generalmente hay 2 lugares en donde uso la laptop:

  • En mi escritorio, donde la conecto a un par de monitores, uno de ellos por HDMI).
  • En cualquier otro lugar.

Como uso XMonad, la posición de algunas barras personalizadas varía dependiendo de si estoy usando el monitor de la laptop o el de HDMI. El cambio siempre lo he he hecho manualmente comentando o habilitando un par de líneas en el xmonad.hs, pero quería automatizar el proceso de ser posible. Tenía rato que no usaba Haskell en forma, así que…

Básicamente, lo que necesito es hacer esto en Haskell:

xrandr | grep HDMI1 | cut -d " " -f2

Me eché un clavado en la documentación, y encontré la librería System.Process, concretamente la función createProcess, la cual está definida de la siguiente forma:

createProcess :: CreateProcess -> IO (Maybe Handle, Maybe Handle, Maybe Handle, ProcessHandle)

Donde CreateProcess está definido como se menciona acá:

http://hackage.haskell.org/package/process-1.2.0.0/docs/System-Process.html#t:CreateProcess

Lo que necesito entonces es crear un proceso por cada comando que quiero ejecutar, pero pasar los resultados de uno al siguiente (pipe).  Por tanto, necesito  declarar CreateProcess de la siguiente manera:

Continue reading Detectando si hay monitor conectado en el puerto HDMI con Haskell

Implementando PageRank

Tuve oportunidad de leer este artículo técnico de Stanford, titulado “Searching the Web”:

 http://ilpubs.stanford.edu:8090/457/

Básicamente, es una explicación de cómo funcionan las búsquedas en internet; muestra lo que era el state-of-the-art en ese tópico, incluyendo el algoritmo que fue el comienzo de Google: PageRank.

Existen muchas páginas que describen en detalle cómo funciona esta técnica; incluso, el artículo mencionado arriba lo menciona de forma entendible, así que no ahondaré mucho en detalles: PageRank determina el grado de importancia de una página con base en el número de páginas que tienen ligas hacia ella. y del mismo grado de importancia de cada una de esas páginas. Es decir: una página será más relevante si muchas otras páginas ligan a ella, o también si las páginas que ligan a ella son a su vez relevantes.

Consideremos el caso de una red que sólo tiene 4 sitios: A, B, C y D, y que están ligados de la siguiente forma:

pagerank-example1

Gracias a PageRank, podemos determinar la relevancia de cada uno de estos sitios, usando la fórmula que aparece en el artículo arriba mencionado:

(1)   \begin{equation*} r(i) = \sum_{j \epsilon B(i)} r(j) / N(j) \end{equation*}

Donde r(i) es el pagerank de la página i, r(j) el pagerank de la página j, y N(j) es el número de links que salen de la página j. B(i) es el conjunto de páginas que tienen liga hacia la página i.

A ojo de buen cubero, la página C tendría un valor de relevancia mayor al de las otras páginas por haber 2 que ligan hacia ella (A y B).

Existen un par de problemas con esta fórmula: si encontramos una serie de páginas que sólo tienen ligas entre ellas, o si llegamos a una página que no tiene ligas a ningún lado, a final de cuentas la relevancia se centrará o en las páginas dentro de un cluster (para el primer caso) o convergerá a 0 (en el segundo caso). En el artículo, el primer caso se nombra como rank sink, mientras que el segundo se nombra rank leak.

Se propone también el modelo del Random Surfer para describir el comportamiento de un usuario: o bien puede seguir las ligas de una página a otra, o bien se puede aburrir y “brincar” directamente a una página.

Para resolver los problemas antes mencionados e implmentar al Random Surfer, lo siguiente es propuesto:

  • Eliminar todas la páginas que no tengan ligas externas (leaks). No necesariamente la mejor solución.
  • Suponer que los leak tienen ligas a todas las otras páginas.
  • Agergar un valor que modele al Random Surfer. Este valor se denomina d (decay factor), y es un valor 0 < d < 1, indicando qué tan frecuentemente el Random Surfer se “aburre” de una página y brinca a otra aleatoriamente.

La fórmula anterior entonces cambia a:

(2)   \begin{equation*} r(i) = d * \sum_{j \epsilon B(i)} r(j) / N(j) + (1 - d) / m \end{equation*}

Donde d es el decay factor explicado arriba, m es el número total de páginas en la red, y el factor (1 – d) / m hace que la suma de todos los pagerank de las páginas consideradas sea igual a 1. Por supuesto, dependiendo del manejo de los sinks y leaks, los resultados varían.

Para información más detallada, consulten el artículo.

Power iteration

Es obvio pensar que teniendo tantas páginas que revisar necesitamos un método que sea lo más eficiente posible. Page y Brin mencionan que es posible hacer el cálculo de PageRank usando el método llamado Power Iteration, y que en un número relativamente bajo de iteraciones ( < 100 ) los valores convergen. Omito aquí la explicación técnica de obtener el principal eigenvector de la matriz de pagerank, y me centro específicamente en explicar el método con estructuras simples:

  1. Inicializamos un vector s de longitud m = número de páginas. Cada valor es el pagerank de la página en cuestión. El valor inicial puede ser aleatorio, pero los autores lo inicializan en 1/m
  2. Usando la fórmula (2), calculamos los nuevos valores de pagerank y los guardamos en un vector r.
  3. Calculamos la L1 Norm de las diferencias absolutas entre rs, y las comparamos con un valor de error máximo e previamente determinado. Si la L1 Norm es menor a e, los valores han convergido y r contiene los pagerank finales de las páginas. Si no, ir a 4.
  4. Asignar a s los valores actuales de r y regresar 2.

Implementación

Como siempre, lo aquí establecido no es la verdad absoluta. Quienes estén interesados en mejorar la implementación o crear la suya propia, ¡adelante!
Continue reading Implementando PageRank

Un poquito de Scala

Tengo rato queriendo poner ejemplos de código en Scala que sean  relativamente fáciles de seguir: He visto código que he hecho a lo largo de estos años, pero no sé si sea adecuado para mostrar  características del lenguaje.

Encontré el “mini clon” de Twitter que me hicieron crear en la H. compañía descrita en el post de Luz, pero definitivamente no es nada básico. De hecho, ahora que vi el código de nuevo y ya con cierta experiencia en el lenguaje, me doy cuenta de que es la PEOR manera de que alguien entre en el mundo de Scala. Con razón nadie de los de ahí realmente entendía qué estaba pasando.

Voy a intentarlo con un problema simple que tuve hace tiempo, a ver qué tal queda.

Situación

Tengo un archivo de 112528 líneas, que contiene información en pseudo XML (porque no es válido. Un parser no lo procesa por lo mismo). Dentro de esa información están entidades Unicode (por ejemplo algo como &xyz:) que necesito listar. Hay que crear un programa que las extraiga, elimine duplicados, y las imprima en pantalla (en realidad hay que guardarlas en un archivo, pero para este post con ponerlas en pantalla está bien).

Ejemplo de una línea en el archivo:

<xyz type=”なにか”> &jajaja;漢字漢字漢字&jejeje;漢字だらけ&jajajaja;>

De esta línea el resultado sería:

  • &jajaja;
  • &jejeje;

Continue reading Un poquito de Scala

Un rápido y compacto corrector ortográfico en Scala

Construir un corrector ortográfico no es realmente una tarea muy difícil. Muchos inmediatamente mencionarán la distancia de Levenshtein para saber la distancia de edición entre 2 palabras.

Tomando el ejemplo de Wikipedia:

La distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

  1. casa → cala (sustitución de ‘s’ por ‘l’)
  2. cala → calla (inserción de ‘l’ entre ‘l’ y ‘a’)
  3. calla → calle (sustitución de ‘a’ por ‘e’)

Entonces, buscar los posibles candidatos de una palabra mal escrita se convierte en buscar las palabras que tengan la menor distancia de edición con ella. Es simple, pero en el peor de los casos tendríamos que buscar entre todo el conjunto de palabras que tengamos (como un diccionario), lo cual hace que la búsqueda sea O(n).

Para alivianar el problema, existen los BK-Tree, que básicamente son árboles cuyos nodos son palabras y las aristas tienen el valor de la distancia de edición entre esos nodos. Acá hay una explicación (en inglés) que cubre lo necesario para entenderlos: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

El caso es que usar un BK-Tree para esta tarea acelera mucho la búsqueda de candidatos, puesto que no es necesario cubrir todos los nodos si la distancia máxima que se busca es relativamente pequeña (digamos, 1 o 2).

Buscando implementaciones en Scala, me doy cuenta de que en Scalaz existe la clase BKTree (aunque está deprecated en la versión 7). Viendo el código, y teniendo una lista de 90,000 palabras en inglés, me di a la tarea de implementar un muy sencillo corrector ortográfico en ese lenguaje. La distancia máxima entre palabras la puse en 1. El resultado:

package org.mmg.tests

import scala.io.Source._
import scalaz._
import Scalaz._

object SpellCorrector {

  def main(a: Array[String]) {
	  val words = fromFile("EnglishWords.txt").getLines.toList	  
	  val bt = words.foldLeft(BKTree[String]())((acc, w) => acc + w) 	  	  
	  val MAX_DIST = 1

	 while (true) {
    	print("Input the word you want to check (Ctrl-C to end): ")
    	Option(Console.readLine) filterNot {_.isEmpty} foreach {s => 
        	bt.valuesApproximate(s, MAX_DIST) foreach println
    	}
     }
  }

}

Y probando:

Input the word you want to check (Ctrl-C to end): tail
ail
til
bail
fail
Gail
hail
jail
kail
mail
nail
pail
rail
sail
tail
vail
wail
tall
tael
tain
toil
trail

Los resultados se obtienen relativamente rápido. El ejemplo anterior toma sólo algunas décimas de segundo (casi 90,000 palabras). Por supuesto que esto no quiere decir que sea óptimo, pero si no se busca un desempeño en áreas críticas, funciona.

Obviamente esto es muy simple, pero puede mejorar si por ejemplo le asignamos menos peso a operaciones de la distancia de Levenshtein entre letras que frecuentemente se escriben mal, como por ejemplo, entre la “o” y la “p”, que están juntas en un teclado QWERTY. Eso haría que la distancia fuera menor entre ciertas palabras y reduciría el número de candidatos que se muestran.

Por supuesto, si tenemos un modelo probabilístico podemos usar el teorema de Bayes para buscar mejores candidatos, y aunque no es en sí tan complicado, sí me tomaría más tiempo escribirlo aquí.

Como sea, esta implementación es rápida, y puede sacar de algún apuro.