Haskell jest odpowiednikiem Scala's groupBy

Question

Scala ma funkcję groupBy na listach, które akceptują funkcję wyodrębniania kluczy z elementów listy, i zwraca następną listę, w której elementami są krotki składające się z klucza i listy elementów wytwarzających ten klucz. Innymi słowy, coś takiego:

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))) 

(Właściwie to wygląda w aktualnych wersjach zapewnia on Map zamiast, ale to nie jest ważne). C# ma jeszcze bardziej użyteczną wersję, która pozwala na mapowanie wartości w tym samym czasie (bardzo przydatne, jeśli, powiedzmy, twoja kluczowa funkcja to tylko wyodrębnianie części krotki).

Haskell ma groupBy, ale jest nieco inny - grupuje biegi rzeczy zgodnie z pewną funkcją porównania.

Zanim przejdę do pisania, czy istnieje odpowiednik Scala? groupBy w Haskell? Hoogle nie ma nic takiego, jak oczekiwałbym podpisu (poniżej), ale może się pomyliłem.

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

Answer 1

Można napisać funkcję samodzielnego dość łatwo, ale trzeba złożyć Ord lub Hashable presję na wynik funkcji klasyfikatora jeśli chcesz efektywne rozwiązanie. Przykład:

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])]  

Można również korzystać z mapy hash jak Data.HashMap.Strict zamiast sortowania dla przewidywanego czasu linearnego.

Answer 2

To nie jest funkcja w bibliotece list.

Możesz napisać to jako kompozycję sortBy i groupBy.

Answer 3

W szczególności, następujące powinny działać:

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

modulo że to nie ci wynik f w każdej grupie, ale czy naprawdę trzeba go zawsze można post-procesie z

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

Answer 4

Umieszczenie trace w f ujawnia, że ​​przy rozwiązaniu @Niklas, f jest oceniany 3 razy dla każdego elementu na dowolnej liście o długości 2 lub większej. Miałem możliwość modyfikowania go tak, aby f był stosowany do każdego elementu tylko raz. Nie jest jednak jasne, czy koszt tworzenia i niszczenia krotek jest mniejszy niż koszt wielokrotnego oceniania f (ponieważ f może być dowolny).

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

Roztwór pęknie i grupy, w (fx), bez względu na to pogoda jest sortowany lub nie

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 

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