文章目錄

1. 1. 什麼是Group By Key
2. 2. 問題
   1. 2.1. 解決方法1
   2. 2.2. 解決方法2

什麼是Group By Key

Group By Key 就是把Element 計算一個key，相同key的element 就放左一組內
例如group by key by the reminder equal to 3 in Scala

val arr = Array(2, 4, 5, 6, 9, 23, 24, 25, 31, 37)
scala> val ans = arr.groupBy { n => n % 3 }
ans: scala.collection.immutable.Map[Int,Array[Int]] = Map(2 -> Array(2, 5, 23), 1 -> Array(4, 25, 31, 37), 0 -> Array(6, 9, 24))

問題

Haskell 中把 List 中的element Group By Key 是麻煩的一件事
因為Data.List.groupBy 是linear scan 每兩個element, 然後比較他們是否相同

import Data.List
Prelude Data.List> groupBy (==) [1, 1, 2, 3, 1] 
[[1,1],[2],[3],[1]]

解決方法1

List 事前需要被sorted by key
Scala 的例子在Haskell 可以寫成這樣
值得注意sortBy 要求data Ordering, 需要用compare, 不是Bool結果的> == <

Prelude Data.List> let allInOne = groupBy (\x y -> (x `mod` 3) == (y `mod` 3)) . sortBy (\x y -> compare (x `mod` 3) (y `mod` 3))
Prelude Data.List> allInOne [2, 4, 5, 6, 9, 23, 24, 25, 31, 37]
[[6,9,24],[4,25,31,37],[2,5,23]]

解決方法2

一個package解決這個問題, 當中的groupBy 是scala中的`groupByKey 但return 一個List

安裝

> cabal install utility-ht
> ......
> ghci

例子

Prelude> import Data.List.HT
Prelude Data.List.HT> let a = [2, 4, 5, 6, 9, 23, 24, 25, 31, 37]
Prelude Data.List.HT> groupBy (\x y -> x `mod` 3 == y `mod` 3 )
[[2],[4],[5],[6,9],[23],[24],[25,31,37]]