Haskell эквивалентен Scala groupBy

Scala имеет функцию groupBy в списках, которые принимают функцию для извлечения ключей из элементов списка и возвращает другой список, где элементы являются кортежами, состоящими из ключа и списка элементов, создающих этот ключ. Другими словами, что-то вроде этого:

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

(На самом деле, похоже, что в текущих версиях он предоставляет Map вместо этого, но это не важно). С# имеет еще более полезную версию, которая позволяет сопоставлять значения в одно и то же время (очень полезно, если, скажем, ваша ключевая функция просто извлекает часть кортежа).

Haskell имеет groupBy, но несколько отличается - он группирует пробеги в соответствии с некоторой функцией сравнения.

Прежде чем я пойду и напишу его, есть ли эквивалент Scala groupBy в Haskell? У Hoogle нет ничего для того, что я ожидаю, что подпись будет выглядеть (ниже), но я, возможно, просто ошибся.

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

Ответ 1

Вы можете написать функцию самостоятельно довольно легко, но вам нужно поместить ограничение Ord или Hashable на результат функции классификатора, если вы хотите получить эффективное решение. Пример:

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

Вы также можете использовать хеш-карту типа Data.HashMap.Strict вместо сортировки для ожидаемого линейного времени.

Ответ 2

В частности, должно работать следующее:

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

по модулю, что это не дает вам результата f в каждой группе, но если вам это действительно нужно, вы всегда можете выполнять пост-процесс с помощью

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

Ответ 3

Это не функция в библиотеке списка.

Вы можете записать его как состав sortBy и groupBy.

Ответ 4

Ввод trace в f показывает, что при решении @Niklas f оценивается 3 раза для каждого элемента в любом списке длиной 2 или более. Я позволил изменить его, чтобы f применялся к каждому элементу только один раз. Однако неясно, не является ли стоимость создания и уничтожения кортежей меньше стоимости оценки f несколько раз (так как f может быть произвольным).

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)

Ответ 5

Это решение сломается и группируется по (f x), независимо от того, сортируется оно или нет.

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

Результат: [(1, [1,3]), (0, [4,6,8]), (1, [9])]