Je recherche une combinaison simple de fonctions standard d'ordre supérieur pour compresser une liste en comptant les éléments répétitifs. Par exemple, le résultat pourCompression par comptage d'éléments répétitifs (Haskell)
"abbccccb"
serait:
[(1, 'a'), (2, 'b'), (4, 'c'), (1, 'b')]
un autre exemple, le résultat pour
(sort "abrakadabra")
serait:
[(5, 'a'), (2, 'b'), (1, 'd'), (1, 'k'), (2, 'r')]
j'ai écrit un code qui ne fait que l'utilisation des fonctions élémentaires.
f :: Eq a => [a] -> [(Int, a)]
f [] = []
f (x:xs) = (1 + length (takeWhile (==x) xs), x) : f (dropWhile (==x) xs)
J'espère que cela aidera !.
Commencez par utiliser Data.List.group. Cela vous donne une liste d'exécutions d'éléments égaux, par ex.
> group "abbccccb"
["a","bb","cccc","b"]
Ensuite, map sur cette liste, en prenant la head et length de chaque course. Cela peut être fait avec élégance l'opérateur &&& de Control.Arrow:
> map (length &&& head) . group $ "abbccccb"
[(1,'a'),(2,'b'),(4,'c'),(1,'b')]
Une description plus détaillée de ce qui précède est la section Run Length Encoding de Real World Haskell: http://book.realworldhaskell.org/read/barcode-recognition.html#id631625 – scvalex
Vous pouvez également utiliser Control.Applicative et l'instance de foncteur applicatif (->) e
map ((,) <$> length <*> head) . group
Si vous vouliez maintenant un triple avec la valeur ord, il est vraiment facile!
map ((,,) <$> length <*> head <*> ord . head) . group
Cependant, une fonction anonyme est probablement plus claire pour le lecteur.
map (\xs -> (length xs, head xs, (ord . head) xs) . group
Vous voulez probablement commencer par 'Data.List.group' et continuer à partir de là. – kosmikus
Ce deuxième exemple n'est pas du tout le premier; le premier est réversible, le second est juste des statistiques. – Nyerguds