Nos proponemos hacer un programa funcional que cuente la frecuencia de las ocurrencias de palabras.

frecuencia :: [Palabra] -> [(Palabra,Int)]

Main> frecuencia ["hola","que","hola"]
[("hola",2),("que",1)]

Donde Palabra es un sinónimo de tipo, en este caso de un String, y sirve para mejorar la legibilidad del código.

type Palabra = String

Esta función resulta de gran utilidad para análisis estadístico de textos, como el que se utiliza para comprimir archivos, dar importancia a las palabras en las búsquedas, detectar palabras significativas, etc.

Para hacer más fácil el uso de esta función tomamos de Haskell The Craft of Functional Programming por Simon Thompson, la definción de una función que parte una cadena en palabras.

Veamos el código de “arriba para abajo” top-down, empezando desde la definición principal y terminando en las funciones básicas.

-- Declaracion de tipos
type Palabra = String

partePalabras :: String -> [Palabra]
partePalabras st = partePalabras' (tiraEspacio st)

partePalabras' :: String -> [Palabra]
partePalabras' [] = []
partePalabras' st = (tomaPalabra st) : partePalabras' (tiraEspacio (tiraPalabra st))


tomaPalabra :: String -> String
tomaPalabra [] = []
tomaPalabra (x:xs)      | elemento x espacio = []
                        | otherwise      = x : tomaPalabra xs


tiraPalabra :: String -> String
tiraPalabra [] = []
tiraPalabra (x:xs)      | elemento x espacio = x:xs
                        | otherwise      = tiraPalabra xs


tiraEspacio :: String -> String
tiraEspacio [] = []
tiraEspacio (x:xs)      | elemento x espacio = tiraEspacio xs
                        | otherwise      = x:xs


elemento :: Eq a => a -> [a] -> Bool
-- Definirlo!

espacio :: [Char]
espacio = ['\r', '\n','\t',' ']

• Definir la función politípica elemento :: Eq a ⇒ a → [a] → Bool, donde elemento a xs decide si a está en la lista xs. Ejemplo: elemento 'a' “Abracadabra” = True, elemento 10 [1..9] = False.

Casos de Test: elemento [] [ [1,2],[],[3,4] ], elemento “sandia” [“pera”,“melon”,“uva”].

• Usando la definición de esta función probar tomarPalabra, tirarEspacio.

Casos de Test:

tiraEspacio "           Despues de tres dias" = "Despues de tres dias"
tomaPalabra "Despues de tres dias" = "Despues"
tiraPalabra "Despues de tres dias" = " de tres dias"
tiraEspacio " de tres dias" = "de tres dias"
tomaPalabra "de tres dias" = "de"
tiraPalabra "de tres dias" = " tres dias"
...

• Las funciones tiraEspacio, tiraPalabras y tomaPalabra pueden ser generalizadas.
  • Defina la función tomaMientras :: (a → Bool) → [a] → [a], donde tomaMientras p xs devuelve todos los elementos mientras cumplan con el predicado p, al primero que no cumpla se para. Ejemplo: tomaMientras (>0) [1,2,3,-1,3,2,1] = [1,2,3], tomaMientras (=='a') “nada por aqui” = [].
  • Defina la función tiraMientras :: (a → Bool) → [a] → [a], donde tiraMientras p xs descarta todos los elementos mientras cumplan con el predicado p, al primero que no cumpla se para. Ejemplo: tiraMientras (>0) [1,2,3,-1,3,2,1] = [-1,3,2,3], tiraMientras (=='a') “nada por aqui” = “nada por aqui”.
  • ?Como se llaman tomaMientras y tiraMientras en el preámbulo standard?
• Defina tomaPalabra, tomaEspacio, tiraPalabra, usando las anteriores.

Para probar ejemplos más largos podemos agregar una función que dado el nombre de un archivo, devuelve un String con ese archivo (tomado de EasyIO.hs del curso Introductory Functional Programming for Physics Students )
Este código debe estar al inicio del script.

-- extensión para poder leer archivos en Strings
import Hugs.IOExts(unsafePerformIO)

leeArchivo :: String -> String
leeArchivo nombre = unsafePerformIO $ readFile nombre

Para obtener textos largos e interesantes tenemos el Proyecto Gutemberg-Español donde hay muchos libros que ya no tienen derecho de copia.
Por ejemplo están Cuentos de Amor de Locura y de Muerte de Horacio Quiroga y El Gaucho Martín Fierro de José Hernandez.

Hay que tener cuidado con la codificación pues no todas funcionan.
Por ejemplo UTF8 es una codificación posible. Bajamos el archivo Martín Fierro en UTF8, lo guardamos con el nombre 14765-utf8.txt y lo usamos para probar partePalabras.

Main> take 100 (partePalabras (leeArchivo "14765-utf8.txt"))
["The","Project","Gutenberg","EBook","of","El","Gaucho","Mart\237n","Fierro, ...

o de una forma equivalente utilizando el operador . de composición de funciones, a fin de evitar un poco de paréntesis y mejorar la lectura del código.

((take 100).partePalabras.leeArchivo) "14765-utf8.txt"
["The","Project","Gutenberg","EBook","of","El","Gaucho","Mart\237n","Fierro, ...

• Contar cuantas palabras hay en total.
• Obtener las palabras de “El Gaucho Martín Fierro” que tienen más de 15 letras.
• Observar que hay problemas con partePalabras y los signos de puntuación. ?Cómo mejoraría este aspecto de la función?

La función más importante tiene el siguiente tipo:

frecuencia :: [Palabra] -> [(Palabra,Int)]

donde el resultado es una lista de pares (Palabra,Int) que representa la cantidad de veces que una palabra está en el texto.

Para definir esta función utilizaremos la idea de acumulación. Básicamente si podemos definir una función:

agregaOcurrencia :: Palabra -> [(Palabra,Int)] -> [(Palabra,Int)]

que procesa una palabra, la definición de frecuencia es simplemente acumular toda la lista con esta función.

• Definir la función agregaOcurrencia :: Palabra → [(Palabra,Int)] → [(Palabra,Int)], donde agregarOcurrencia palabra xs toma la lista xs de pares (p,n) y actualiza la lista de frecuencias para incorporar una nueva ocurrencia de palabra. Ejemplos: agregaOcurrencia “hola” [] = [(“hola”,1)], agregaOcurrencia “hola” [(“hola”,1),(“que”,1)] = [(“hola”,2),(“que”,1)].

Casos de test: agregaOcurrencia “hola” [(“hola”,1)], agregaOcurrencia “que” [(“hola”,1)].

• A partir de agregaOcurrencia y foldr definir la función frecuencia :: [Palabra] → [(Palabra,Int)], donde frecuencia xs retorna la lista de frecuencias de cada una de las palabras de xs. Ejemplo: frecuencia [“hola”, “que”, “hola”] = [(“hola”,2),(“que”,1)].

Caso de test: frecuencia (partePalabras “Cantando me he de morir Cantando me han de enterrar”) = [(“enterrar”,1),(“de”,2),(“han”,1),(“me”,2),(“Cantando”,2),(“morir”,1),(“he”,1)]

• Componer frecuencia, take, partePalabras y leeArchivo para computar la frecuencia de las primeras 10, 100, 1000 y 10000 palabras de “El Gaucho Martín Fierro”. Cuidado, con 1000 y 10000 puede demorar un buen rato.

El esquema presentado hasta ahora (frecuencia.partePalabras.leeArchivo) resulta poco útil, debido a que resulta esencial, conocer cuales son, por ejemplo, las 10 palabras más frecuentes porque para:

• Compresión de texto: estas palabras se deben codificar “cortito”.
• Relevancia de palabras para búsquedas: estas palabras hay que descartarlas porque no representan información.
• Descarte de palabras-nexo: simplemente eliminarlas.

La lista que devuelve frecuencia está ordenada según aparecen las palabras. Podríamos intentar ordenarlas de acuerdo a la frecuencia y luego tomar las 10 primeras para ver con que nos encontramos.

En el Problemario del taller, se planteó la función ordenaIns, y en en la Wiki con las soluciones tiene el siguiente código insertaOrd, ordenaIns, que al día de hoy es:

{-Lord Hobborg-}
insertaOrd :: Int -> [Int] -> [Int]
insertaOrd y (x:xs) | y>=x = x:insertaOrd y xs
                    | y<x  = y:(x:xs)
insertaOrd y _      = [y]

{-Lord Hobborg-}
ordenaIns :: [Int] -> [Int]
ordenaIns (x:xs) = insertaOrd x (ordenaIns xs)
ordenaIns _      = []

• Variando ligeramente insertaOrd, definir la función insertaOrdFrec :: (Palabra,Int) → [(Palabra,Int)] → [(Palabra,Int)], donde insertaOrdFrec (p,n) xs inserta la palabra y su frecuencia de manera ordenada en la frecuencia dentro de la lista xs que se supone ordenada de menor a mayor en frecuencia. Ejemplo: insertaOrdFrec (“algo”,10) [(“nada”,1),(“mucho”,100)] = [(“nada”,1),(“algo”,10),(“mucho”,100)].

Casos de test: insertaOrdFrec (“algo”,10) [], insertaOrdFrec (“algo”,10) [(“nada”,1)], insertaOrdFrec (“algo”,10) [(“mucho”,100)].

• Variando ligeramente ordenaIns y usando insertaOrdFrec, definir ordenaInsFrec :: [(Palabra,Int)] → [(Palabra,Int)], donde ordenaInsFrec.xs ordena la lista de frecuencias xs de menor a mayor. Ejemplo: ordenaInsFrec [(“mucho”,100),(“algo”,10),(“nada”,1)] = [(“nada”,1),(“algo”,10),(“mucho”,100)].
• Agregar ordenaInsFrec como un eslabón más a la cadena de funciones (frecuencia.(take 1000).partePalabras.leeArchivo) “14765-utf8.txt” para obtener en forma creciente la frecuencia de las primeras 1000 palabras de “El Gaucho Martín Fierro”.
• Redefinir ordenaInsFrec a partir de insertaOrdFrec y foldr.