Pillole di Haskell - ricerca di duplicati
Di recente ho dovuto scrivere una funzioncina in Haskell per trovare elementi duplicati in una lista. Anche se non necessariamente il più furbo, trovo che il metodo che ho usato fornisca un esempio interessante di programmazione funzionale in questo linguaggio.
L'idea (semplice) è la seguente: ordiniamo la lista (il che richiede che gli elementi siano confrontabili, cioè che appartengano alla classe Ord) e poi cerchiamo due elementi consecutivi uguali. Mostro come implementare quest'idea, procedendo per applicazioni consecutive di funzioni.
Il primo passo è l'ordinamento della lista. Senza avventurarci in algoritmi di ordinamento, utilizziamo la funzione sort nel modulo Data.List. Quindi la nostra prima versione è questa:
import Data.List ( sort ) dups a = sort aIn una sessione interattiva di ghci esaminiamo il tipo del nostro primo abbozzo della funzione dups e il suo comportamento su una lista di esempio:
# ghci dups.hs ... *Main> :t dups dups :: (Ord a) => [a] -> [a] *Main> dups [ 7, 8, 5, 12, 5, 1, 3, 8, 6 ] [1,3,5,5,6,7,8,8,12]
Senza troppe sorprese, per ora dups trasforma una lista di elementi della classe Ord in un'altra lista dello stesso tipo.
Un modo per analizzare elementi consecutivi (dobbiamo trovare quelli uguali) è di affiancare alla lista ordinata una sua copia scalata di un elemento. La funzione tail restituisce gli elementi di una lista dal secondo in poi. Proviamo ad usarla così:
import Data.List ( sort )
dups a =
let sorted = sort a
in
( sorted, tail sorted )
Dovendo usare due volte la lista ordinata, le abbiamo assegnato un nome (sorted) e poi abbiamo restituito una coppia con la versione ordinata con e senza primo elemento.
*Main> dups [ 7, 8, 5, 12, 5, 1, 3, 8, 6 ] ([1,3,5,5,6,7,8,8,12],[3,5,5,6,7,8,8,12])
Invece della coppia con le due liste, ci farebbe comodo una lista con le coppie di elementi, in cui andremo a cercare quelle costituite da elementi uguali. La funzione zip del modulo di base Prelude fa quello che ci serve.
import Data.List ( sort )
dups a =
let sorted = sort a
in
zip sorted ( tail sorted )
Ci dà
*Main> dups [ 7, 8, 5, 12, 5, 1, 3, 8, 6 ] [(1,3),(3,5),(5,5),(5,6),(6,7),(7,8),(8,8),(8,12)]
A questo punto dobbiamo solo cercare le coppie che hanno i due elementi uguali. Basta filtrare la lista (con la funzione filter, che corrisponde al grep di perl) con la condizione di uguaglianza.
import Data.List ( sort )
dups a =
let sorted = sort a
in
filter ( \ ( a, b ) -> a == b ) ( zip sorted ( tail sorted ) )
*Main> dups [ 7, 8, 5, 12, 5, 1, 3, 8, 6 ] [(5,5),(8,8)]
Quasi ci siamo. La funzione dups ora ha tipo
dups :: (Ord a) => [a] -> [(a, a)]
ma noi vorremmo che ci restituisse una lista di elementi e non di coppie. Applichiamo la funzione fst a tutte le coppie di duplicati per avere solo il primo elemento di ogni coppia:
import Data.List ( sort )
dups a =
let sorted = sort a
in
map fst
( filter ( \ ( a, b ) -> a == b ) ( zip sorted ( tail sorted ) ) )
e finalmente:
*Main> dups [ 7, 8, 5, 12, 5, 1, 3, 8, 6 ] [5,8]
La funzione dups è generica e possiamo ad esempio applicarla a stringhe, che in Haskell sono in tutto e per tutto liste di caratteri.
*Main> dups "we love haskell" " eell"
La lista di duplicati contiene a sua volta dei duplicati, perché alcune lettere appaiono tre volte. Se vogliamo, possiamo semplificare l'output con la funzione nub del modulo Data.List.
import Data.List ( sort, nub )
dups a =
let sorted = sort a
in
nub ( map fst
( filter ( \ ( a, b ) -> a == b ) ( zip sorted ( tail sorted ) ) )
)
*Main> dups "we love haskell" " el"
Dal punto di vista stilistico, possiamo applicare un paio di modifiche. La lambda expression \ ( a, b ) -> a == b definisce una funzione che è semplicemente l'operatore ==. Messo tra parentesi, l'operatore diventa una funzione di due argomenti:
(==) :: (Eq a) => a -> a -> Bool
Il problema è che a questa funzione passiamo un unico argomento di tipo (a, a). Ci viene in aiuto uncurry, che trasforma una funzione di due argomenti in una funzione di un argomento di tipo coppia.
*Main> :t uncurry uncurry :: (a -> b -> c) -> (a, b) -> c
Possiamo quindi sostituire la lambda expression con uncurry (==) e avere una definizione scritta come:
import Data.List ( sort, nub )
dups a =
let sorted = sort a
in
nub ( map fst
( filter ( uncurry (==) ) ( zip sorted ( tail sorted ) ) )
)
A seconda dei gusti, possiamo scegliere di utilizzare l'operatore $, che ha l'effetto di raggruppare il secondo membro rendendo inutile l'uso di parentesi. La scrittura
myfun ( otherfun arg1 ( subfun x y ) )
può essere resa con
myfun $ otherfun arg1 $ subfun x y
con il notevole risparmio di un paio di spazi e altrettante parentesi. Arriviamo così alla versione finale della nostra funzioncina:
import Data.List ( sort, nub )
dups a =
let sorted = sort a
in
nub $ map fst
$ filter ( uncurry (==) ) $ zip sorted $ tail sorted