CODEWITHSUNDEEP
listhaskelltypes
user4035
user4035

Reputation: 23729

Can't match expected type with actual type for list construction

Problem: having a typeclass MapLike, looking like a map type, implement an instance for MapLike for the type ListMap. ListMap is defined as a list of pairs (key, value). For each key there must be only 1 value. insert function changes the old value to the new one if the key is contained in the map.

It implemented it partially, but for insert function I get an error:

error:

• Couldn't match expected type ‘[ListMap k0 v0]’
              with actual type ‘ListMap k v’
• In the second argument of ‘(:)’, namely ‘t’
  In the expression: (ListMap (k, v) : t)
  In the expression:
    let t = insert key val (ListMap xs) in (ListMap (k, v) : t)

I don't understant what's wrong, I am checking whether the key is in the head of the list. If it's there, we change the value and cons it with the tail. If it's not there, we get the list with exchanged or concatenated key/value pair and add a head to it. What's wrong?

import Prelude hiding (lookup)
import qualified Data.List as L

class MapLike m where
    empty :: m k v
    lookup :: Ord k => k -> m k v -> Maybe v
    insert :: Ord k => k -> v -> m k v -> m k v
    delete :: Ord k => k -> m k v -> m k v
    fromList :: Ord k => [(k,v)] -> m k v
    fromList [] = empty
    fromList ((k,v):xs) = insert k v (fromList xs)

newtype ListMap k v = ListMap { getListMap :: [(k,v)] }
    deriving (Eq,Show)

instance MapLike ListMap where
  empty = ListMap []
  lookup key (ListMap []) = Nothing
  lookup key (ListMap ((k, v):xs)) | key == k = Just v
                                   | otherwise = lookup key (ListMap xs)
  insert key val (ListMap []) = ListMap [(key, val)]
  insert key val (ListMap ((k, v):xs)) | key == k = ListMap ((k, val):xs)
                                       | otherwise = let (ListMap t) = insert key val (ListMap xs) in
                                           (ListMap (k, v):t) -- <-?

Upvotes: 0

Views: 47

Answers (1)

Lee
Lee

Reputation: 144136

ListMap (k, v):t is parsed as ((ListMap (k, v)) : t). Since (:) has type a -> [a] -> [a], and ListMap constructs a ListMap k v, t must have type [ListMap k v] to typecheck. Since t (correctly) has type [(k, v)] the check fails. You also have another error, namely that (k, v) does not have the required type of [(k, v)] to be used as an argument to the ListMap constructor.

You can fix both of these by ensuring the parse you want, either:

ListMap ((k, v):t)

or

ListMap $ (k,v):t

Upvotes: 6

Related Questions