Haskell equivale al gruppo di ScalaDi

Question

Scala ha una funzione groupBy in elenchi che accetta una funzione per l'estrazione di chiavi da voci di elenco e restituisce un altro elenco in cui gli elementi sono tuple costituite dalla chiave e l'elenco di elementi che producono quella chiave. In altre parole, qualcosa di simile:

List(1,2,3,4,5,6,7,8,9).groupBy(_ % 2) 
// List((0, List(2,4,6,8)), (1, List(1,3,5,7,9))) 

(In realtà, sembra che nelle attuali versioni fornisce un Map, invece, ma non è importante). C# ha una versione ancora più utile che ti permette di mappare i valori allo stesso tempo (molto utile se, per esempio, la tua funzione chiave sta semplicemente estraendo parte di una tupla).

Haskell ha un groupBy, ma è un po 'diverso - raggruppa le corse di cose secondo alcune funzioni di confronto.

Prima di andare a scriverlo, c'è un equivalente di Scala groupBy in Haskell? Hoogle non ha nulla per quello che mi aspetterei che la firma assomigli (sotto), ma forse ho appena sbagliato.

Eq b => (a -> b) -> [a] -> [(b,[a])] 

Answer 1

È possibile scrivere la funzione da soli piuttosto facilmente, ma è necessario porre un vincolo Ord o Hashable sul risultato della funzione di classificazione, se si desidera una soluzione efficiente. Esempio:

import Control.Arrow ((&&&)) 
import Data.List 
import Data.Function 

myGroupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])] 
myGroupBy f = map (f . head &&& id) 
        . groupBy ((==) `on` f) 
        . sortBy (compare `on` f) 

> myGroupBy (`mod` 2) [1..9] 
[(0,[2,4,6,8]),(1,[1,3,5,7,9])]  

È inoltre possibile utilizzare una mappa di hash come Data.HashMap.Strict invece di ordinamento per tempo lineare previsto.

Answer 2

Questa non è una funzione nella libreria Elenco.

È possibile scriverlo come composizione di sortBy e groupBy.

Answer 3

In particolare, il seguente dovrebbe funzionare:

scalaGroupBy f = groupBy ((==) `on` f) . sortBy (comparing f) 

con modulo che questo non si fa arrivare il risultato di f in ogni gruppo, ma se si ha realmente bisogno si può sempre post-processo con

map (\xs -> (f (head xs), xs)) . scalaGroupBy f 

Answer 4

L'inserimento di un numero trace in f rivela che, con la soluzione @Niklas, f viene valutata 3 volte per ciascun elemento su qualsiasi elenco di lunghezza 2 o superiore. Mi sono permesso di modificarlo in modo che f sia applicato a ciascun elemento solo una volta. Non è chiaro tuttavia se il costo di creazione e distruzione di tuple sia inferiore al costo di valutazione di f più volte (dal momento che f può essere arbitrario).

import Control.Arrow ((&&&)) 
import Data.List 
import Data.Function 

myGroupBy' :: (Ord b) => (a -> b) -> [a] -> [(b, [a])] 
myGroupBy' f = map (fst . head &&& map snd) 
        . groupBy ((==) `on` fst) 
        . sortBy (compare `on` fst) 
        . map (f &&& id) 

Answer 5

Questa soluzione si romperà e raggruppa per on (fx), indipendentemente wether è ordinato o meno

f = (`mod` (2::Int)) 

list = [1,3,4,6,8,9] :: [Int] 


myGroupBy :: Eq t => (b -> t) -> [b] -> [(t, [b])] 

myGroupBy f (z:zs) = reverse $ foldl (g f) [(f z,[z])] zs 
    where 
    -- folding function       
    g f ((tx, xs):previous) y = if (tx == ty) 
          then (tx, y:xs):previous 
          else (ty, [y]):(tx, reverse xs):previous 
     where ty = f y       

main = print $ myGroupBy f list 

risultato: [(1, [1,3]), (0, [4,6,8]), (1, [9])]