Haskell - Reduce list - MapReduce

Question

我正在尝试减少元组列表，其中重复键的值像这样加在一起：

[(the, 1), (the, 1)] => [(the, 2)]

我试过这个：

reduce :: [(String, Integer)] -> [(String, Integer)]
reduce [] = []
reduce [(k, v) : xs] = (+) [(k, v)] : reduce xs 

我收到此错误：

 Couldn't match expected type `(String, Integer)'
             with actual type `[(String, Integer)] -> [(String, Integer)]'

我做错了什么？

编辑

这是完整的程序

toTuple :: [String] -> [(String, Integer)]
toTuple [] = []
toTuple (k:xs) = (k, 1) : toTuple xs
reduce :: [(String, Integer)] -> [(String, Integer)]
reduce [] = []
reduce [(k, v) : xs] = (+) [(k, v)] : reduce xs     
main_ = do list <- getWords "test.txt"
       print $ reduce $ toTuple list
-- Loads words from a text file into a list.
getWords :: FilePath -> IO [String]
getWords path = do contents <- readFile path
               return ([Prelude.map toLower x | x <- words contents]) 

Answer 1

您做的模式匹配错误。模式匹配应如下所示：

  ((k,v):xs)

(k,v)表示列表的头部，xs表示列表的尾部。同样，这也是有问题的：

(+) [(k, v)] : reduce xs 

+的类型是这样的：

λ> :t (+)
(+) :: Num a => a -> a -> a

你不能简单地做(+) [(k, v)] : reduce xs在任何地方看起来不合理的事情。您必须检查字符串的内容，然后添加元组的第二部分。

Answer 2

让我指出，您的函数reduce与Data.Map中的函数fromListWith非常相似：

> :m Data.Map
> let reduce = toList . fromListWith (+)
> :t reduce
reduce :: (Ord k, Num a) => [(k, a)] -> [(k, a)]
> reduce [('a', 3), ('a', 1), ('b', 2), ('a', 10), ('b', 2), ('c', 1)]
[('a',14),('b',4),('c',1)]
> reduce [(c,1) | c <- "the quick brown fox jumps over the lazy dog"]
[(' ',8),('a',1),('b',1),('c',1),('d',1),('e',3),('f',1),('g',1),('h',2),('i',1),('j',1),('k',1),('l',1),('m',1),('n',1),('o',4),('p',1),('q',1),('r',2),('s',1),('t',2),('u',2),('v',1),('w',1),('x',1),('y',1),('z',1)]