Converting a list to a data.map giving type error

Question

I am trying to convert a list to a data.map so that from a list like:

mylist = ["one","one","two","three","two","two","three","four","four","four","four","five","five","two"]

I get something like:

("one", 2)  ("two", 4) ...

I am trying following code:

import qualified Data.Map as Map
import Data.List 

list2dict [] mymap = print mymap
list2dict [y:ys] mymap = do
    if (Map.lookup y mymap) /= Nothing
    then list2dict [ys] $ Map.insert y ((Map.lookup y) + 1) mymap 
    else list2dict [ys] $ Map.insert y 1 mymap 

mylist = ["one","one","two","three","two","two","three","four","four","four","four","five","five","two"]
main = do
    list2dict (sort mylist) $ Map.empty

However, I am getting following error:

soq_list2dict.hs:5:1: error:
    • Non type-variable argument
        in the constraint: Show (Map.Map k a -> Maybe a)
      (Use FlexibleContexts to permit this)
    • When checking the inferred type
        list2dict :: forall a k.
                     (Show (Map.Map k a -> Maybe a), Show k, Ord k,
                      Num (Map.Map k a -> Maybe a), Eq (Map.Map k a -> Maybe a)) =>
                     [[k]] -> Map.Map k (Map.Map k a -> Maybe a) -> IO ()

How can this be solved?

Edit: using (y:ys) instead of [y:ys] gives following error:

soq_list2dict.hs:5:1: error:
    • Occurs check: cannot construct the infinite type: k ~ [k]
      Expected type: [[k]] -> Map.Map k (Map.Map k a -> Maybe a) -> IO ()
        Actual type: [k] -> Map.Map k (Map.Map k a -> Maybe a) -> IO ()
    • Relevant bindings include
        list2dict :: [[k]] -> Map.Map k (Map.Map k a -> Maybe a) -> IO ()
          (bound at soq_list2dict.hs:5:1)

Answer 1

You made a classic error: a non-empty list has as pattern (x:xs) (notice the empty brackets). But you make things too complicated here.

You can implement this with a foldr pattern, that can convert any (Ord a, Foldable f) => f a to a (Ord a, Integral i) => Map a i:

import Data.Map(Map, alter, empty)
import Data.Maybe(maybe)

toCounter :: (Ord a, Foldable f, Integral i) => f a -> Map a i
toCounter = foldr (alter (Just . maybe 1 (1+))) empty

We thus start with an empty map, and for each item in the Foldable, we perform an alter where, in case the item already exists (then it gives us a Just n, we return a Just (n+1), and for a Nothing we fallback on 1.

Since it works on (Ord a, Foldable f) => f a, you can make a "counter" for anything of a type that is an instance of the Ord typeclass, and is stored in a object of a type that is an instance of a Foldable. So it can count items in a list, Maybe (well this has exactly one or no item), a Tree, etc.

For example:

*Main> toCounter ["one","one","two","three","two","two","three","four","four","four","four","five","five","two"]
fromList [("five",2),("four",4),("one",2),("three",2),("two",4)]

A shorter version, that works on lists is one written by @DavidFletcher:

import Data.Map(Map, fromListWith)

toCounter :: (Ord a, Integral i) => [a] -> Map a i
toCounter = fromListWith (+) . map (flip (,) 1)

we can however use toList to let it work with Foldables as well:

import Data.Foldable(toList)
import Data.Map(Map, fromListWith)

toCounter :: (Ord a, Foldable f, Integral i) => f a -> Map a i
toCounter = fromListWith (+) . map (flip (,) 1) . toList

Answer 2

Willem Van Onsem already pointed out the first problem in a comment: you used [y:ys] instead of (y:ys). The second problem is that you used [ys] instead of just ys in two places. The third problem is that you say ((Map.lookup y) + 1), which creates a nonsensical type. (Even if you had used ((Map.lookup y mymap) + 1) instead, which is closer to correct, you still would have just gotten a different error.) This way will work instead:

list2dict (y:ys) mymap = case Map.lookup y mymap of
    Just x -> list2dict ys $ Map.insert y (x + 1) mymap
    Nothing -> list2dict ys $ Map.insert y 1 mymap

Note that I pattern-match on the Maybe rather than testing it with if and then trying to extract the value separately after that.