Group Sub-Expression Values ​​Based on Equivalent Amounts with Haskell

Question

I am trying to learn Haskell, and I was trying to create a function that enumerates a list of lists and subscription groups using equivalent amounts. This is not homework.

import Data.List
let x = [[1,2],[2,1],[5,0],[0,3],[1,9]]
let groups = groupBy (\i j -> sum i == sum j) x

I get this output in GHCi:

[[[1,2],[2,1]],[[5,0]],[[0,3]],[[1,9]]]

I get grouping [[1,2],[2,1]]together, but not with [0,3]. Why is this?

I suspect that I need to use map, but I cannot get it to work.

Answer 1

The function groupBypreserves the input order and is therefore reversible. If you want to throw away this information, you can use the code in the lines

import Data.List (foldl')
import Data.Map (elems,empty,insertWith')

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

In action:

* Main> bucketBy sum x
[[[0.3], [2.1], [1.2]], [[5.0]], [[1.9]]]

---

How it works

elems Data.Map , .

elems :: Map κ α -> [α]

(). .

elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []

κ , , α. x,

*Main> :type x
x :: [[Integer]]

, x - . partition x, ,

*Main> :t [[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]]
[[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]] :: Num τ => [[[τ]]]

, , . Num τ => , τ Num. Integer - :

*Main> :info Integer
data Integer
…
instance Num Integer -- Defined in GHC.Num
…

, [[[Integer]]]. , . ( , , typechecker , , 0, , Int Integer.)

. , . , bucketBy,

Map Integer [[Integer]]

, 3

[ [0,3]
, [2,1]
, [1,2]
]

- . Left fold, foldl Haskell "" , . , [5,3,9,1], ,

((((0 + 5) + 3) + 9) + 1)

foldl (+) 0 [5,3,9,1]

, , .

, bucketBy

elems . foldl' go empty

, Map Integer [[Integer]], - , go - .

, foldl' foldl, . (. " " HaskellWiki.)

, ?

foldl'

*Main> :t foldl'
foldl' :: (a -> b -> a) -> a -> [b] -> a

, . , . - foldl'.

.

*Main> :t foldl (+) 0
foldl (+) 0 :: Num b => [b] -> b

. , . , .

*Main> :t sum
sum :: Num a => [a] -> a

. . , g∘f, , " f, g ". , bucketBy: .

,

m. go

...
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

, m - , , l - Integer , . , eq bucketBy.

, , insertWith'. ( , , .)

(++)combinator . eq l l.

l, [l],

*Main> bucketBy sum x
[[0,3,2,1,1,2],[5,0],[1,9]]

.

bucketBy [[[α]]] , , . l, [1,2]. (++), - [[Integer]], .

*Main> [[0,3],[2,1]] ++ [1,2]

<interactive>:1:21:
    No instance for (Num [t0])
      arising from the literal `2'
    Possible fix: add an instance declaration for (Num [t0])
    In the expression: 2
    In the second argument of `(++)', namely `[1, 2]'
    In the expression: [[0, 3], [2, 1]] ++ [1, 2]

l

*Main> [[0,3],[2,1]] ++ [[1,2]]
[[0,3],[2,1],[1,2]]

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

, .

, y,

y :: [[Int]]
y = [[1,2],[2,1],[5,0],[0,3],[1,9]]

, x, bucketBy y.

*Main> bucketBy sum y

<interactive>:1:15:
    Couldn't match expected type `Integer' with actual type `Int'
    Expected type: [[Integer]]
      Actual type: [[Int]]
    In the second argument of `bucketBy', namely `y'
    In the expression: bucketBy sum y

, - y. , bucketByInt, Integer Int .

, .

, , , .

*Main> bucketBy (maximum . map length) [["a","bc"],["d"],["ef","g"],["hijk"]]
[[["d"]],[["ef","g"],["a","bc"]],[["hijk"]]]

, , : , . , ,

*Main> bucketBy (maximum . map length) [["a","bc"],["d"],["ef","g"],["hijk"]]

<interactive>:1:26:
    Couldn't match expected type `Integer' with actual type `[a0]'
    Expected type: Integer -> Integer
      Actual type: [a0] -> Int
    In the first argument of `map', namely `length'
    In the second argument of `(.)', namely `map length'

, bucketByString, .

- . bucketBy, Integer, .

*Main> :t bucketBy
bucketBy :: Ord k => (b -> k) -> [b] -> [[b]]

bucketBy . , !

, , bucketBy, , , . , Ord - insertWith',

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

, go, .

{-# LANGUAGE ScopedTypeVariables #-}

import Data.List (foldl')
import Data.Map (Map,elems,empty,insertWith')

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go :: Map b [a] -> a -> Map b [a]
        go m l = insertWith' (++) (eq l) [l] m

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]

typechecker

    Could not deduce (b ~ b1)
    from the context (Ord b)
      bound by the type signature for
                 bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
      at prog.hs:(10,1)-(12,46)
      `b' is a rigid type variable bound by
          the type signature for
            bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
          at prog.hs:10:1
      `b1' is a rigid type variable bound by
           the type signature for go :: Map b1 [a1] -> a1 -> Map b1 [a1]
           at prog.hs:12:9
    In the return type of a call of `eq'
    In the second argument of `insertWith'', namely `(eq l)'
    In the expression: insertWith' (++) (eq l) [l] m

, typechecker b b1, - .

.

, . , ,

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]

, [Integer] , a.

Answer 2

groupBy , . [0,3] [1,2] [2,1], . , , , , . sortBy.

import Data.List
import Data.Function
import Data.Ord

groupBySum :: Num a => [[a]] -> [[[a]]]
groupBySum xss = groups
  where
    ys = map (\xs -> (sum xs,xs)) xss
    sortedSums = sortBy (comparing fst) ys
    groupedSums = groupBy ((==) `on` fst) sortedSums
    groups = map (map snd) groupedSums

Answer 3

From hackage :

The group function takes a list and returns a list of lists, so concatenating the result is equal to the argument.

groupBythe same, except that you can specify your equality test. Thus, since your input list is [0,3]not adjacent to [1,2]or [2,1], it is placed on its own.