CODEWITHSUNDEEP
haskellmapreduce
MosesA
MosesA

Reputation: 965

Haskell - Reduce list - MapReduce

I'm trying to reduce a list of tuples, where the values of a duplicate key are added together like this:

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

I tried this:

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

I'm getting this error:

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

What am I doing wrong?

Edit

This is the full program

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

Upvotes: 4

Views: 2115

Answers (2)

Stef
Stef

Reputation: 15505

Let me point out that your function reduce is extremely similar to function fromListWith from Data.Map:

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

Upvotes: 1

Sibi
Sibi

Reputation: 48664

You are doing the pattern matching wrong. The pattern match should be like this:

  ((k,v):xs)

(k,v) represents the head of the list and xs represents the tail of the list. Similarly this is problematic:

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

The type of + is this:

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

You cannot simply do (+) [(k, v)] : reduce xs which doesn't appear anywhere reasonable. You have to check the contents of the String and then add second part of the tuple.

Upvotes: 2

Related Questions