Encuentra la diferencia – versión Kanji – en Haskell

Lo prometido es deuda. Siguiendo con el escrito anterior, aquí está el código que resuelve el problema, pero ahora en Haskell:

import qualified Data.ByteString as B
import qualified Data.ByteString.UTF8 as U
import System.Environment(getArgs)
import Data.List
import Data.Maybe

main = do
    putStrLn "Write the sequence you want to analyze:"
    B.getLine >>=  processArguments

processArguments :: B.ByteString ->  IO ()
processArguments xs = findUniques $ U.toString xs

findUniques = printUniques . findUniques'

findUniques' :: (Eq a, Show a) => [a] ->  [(a,Int)]
findUniques' xs = let uniques = filter (\i ->  countInstances i xs == 1) $ nub xs
                  in [(x,y) | x <- uniques, y <- mapMaybe (\i ->  i `elemIndex` xs) [x]]

printUniques :: (Eq a, Show a) =>  [(a,Int)] ->  IO ()
printUniques [] = putStrLn "All instances are the same"
printUniques us = mapM_ putStrLn $ map (\c →  ((("Unique instance: " ++ ) $ show $ fst c) ++ ) $ ((" in position " ++ ) $ show $ (+1) $ snd c)) us

countInstances :: (Eq a, Show a) =>  a ->  [a] ->  Int
countInstances _ [] = 0
countInstances c (x:xs)
    | c == x = 1 + countInstances c xs
    | otherwise = countInstances c xs

 

Es un hecho que puedo usar un where en la definición de printUniques, pero bueno, el caso es que funciona:

mmedina@yggdrasil-m:~/Programming/Haskell/FindDifference$ ./fdc
Write the sequence you want to analyze:
麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈
Unique instance: '\22645' in position 66

Todo muy bonito, sí. Pero entonces: ¿para qué tanto código en Haskell? Explico:

En sí, la función que encuentra las instancias diferentes a las demás es findUniques’, y nos dice en qué posición la encontró:

findUniques' :: (Eq a, Show a) => [a] ->  [(a,Int)]
findUniques' xs = let uniques = filter (\i ->  countInstances i xs == 1) $ nub xs
                  in [(x,y) | x <- uniques, y <- mapMaybe (\i →  i `elemIndex` xs) [x]]

findUniques’ utiliza otra función: countInstances. Nos dice cuántas instancias de algo hay dentro de una lista de ese algo:

countInstances :: (Eq a, Show a) =>  a ->  [a] -> Int
countInstances _ [] = 0
countInstances c (x:xs)
    | c == x = 1 + countInstances c xs
    | otherwise = countInstances c xs

Probando en modo interactivo:

*Main> findUniques' "麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈"
Loading package bytestring-0.9.1.7 ... linking ... done.
Loading package utf8-string-0.3.6 ... linking ... done.
[('\22645',65)]

Todo lo demás es para obtener el argumento directamente al llamar al programa y para imprimir el resultado… o tratar de hacerlo. Haskell maneja bien UTF8, pero al momento de llamar a show para obtener un elemento en su representación en String, parece ser que show decodifica el carácter; es por eso que se muestra el código “\22645” en vez de 塵. Esto fue lo que me tomó más tiempo puesto que me puse a investigar, ya que si usan un putStrLn de la forma que muestro abajo, sí se muestran los caracteres japoneses:

import Data.ByteString as B
import Data.ByteString.UTF8 as U
import System.Environment(getArgs)

main = do
       line <- B.getLine       
       Prelude.putStrLn $ show $ U.length line
       B.putStrLn line
       Prelude.putStrLn $  ("入力は: " ++) $ U.toString line

Lo interesante aquí es que, si se fijan, las funciones importantes no están definidas solamente para Strings. Gracias a las typeclasses de Haskell, es posible generalizar el algoritmo para que funcione en cualquier dato que sea tenga instancia de Eq y Show. Por tanto, si probamos la misma función findUniques’ con cualquier otro tipo de dato que cumpla con las restricciones especificadas, funcionará sin necesidad de cambiarle nada.

Con String, 2 instancias únicas:

*Main> findUniques' "aaaaaabaaaaac"
[('b',6),('c',12)]

Con Int:

*Main> findUniques' [1,3,3,4,4,5,2,4,5]
[(1,0),(2,6)]

Y claro que con listas de Int también:

*Main> findUniques' [[1,2],[1,2],[4,3],[2,5],[4,3],[3,4,1]]
[([2,5],3),([3,4,1],5)]

Es claro que no esta no es la única forma de implementarlo (y seguramente hay mejores), pero todo paso a paso 🙂

Lo que sí me latió mucho fue la conveniencia de las typeclasses y cómo generalizando un algoritmo se puede aplicar para diferentes tipos de datos sin necesidad de cambiar ni agregar nada de código. Además, el uso de Monads me ahorró un buen de código.

¿Qué sigue? Hacerlo en Scala, tanto con y sin Scalaz.

One Reply to “Encuentra la diferencia – versión Kanji – en Haskell”

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.