CODEWITHSUNDEEP
haskellfunctional-programminghigher-order-functions
samfrances
samfrances

Reputation: 3695

Reimplementing Map.fromListWith function

I have been trying to reimplement the Map.fromListWith function in Haskell, but I'm running up against an error I don't understand.

Here's my implementation:

fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn :: (Map.Map k a) -> (k, a) -> Map.Map k a
    foldfn m (key, val) = Map.insertWith fn key val m

Here's my error:

Lecture8.hs:33:49: error:
    • Couldn't match expected type 'a' with actual type 'a1'
      'a1' is a rigid type variable bound by
        the type signature for:
          foldfn :: forall k1 a1. Map.Map k1 a1 -> (k1, a1) -> Map.Map k1 a1
        at src/Lecture8.hs:32:15
      'a' is a rigid type variable bound by
        the type signature for:
          fromListWith_ :: forall a k.
                           (a -> a -> a) -> [(k, a)] -> Map.Map k a
        at src/Lecture8.hs:29:18
    • In the third argument of 'Map.insertWith', namely 'val'
      In the expression: Map.insertWith fn key val m
      In an equation for 'foldfn':
          foldfn m (key, val) = Map.insertWith fn key val m
    • Relevant bindings include
        val :: a1 (bound at src/Lecture8.hs:33:20)
        m :: Map.Map k1 a1 (bound at src/Lecture8.hs:33:12)
        foldfn :: Map.Map k1 a1 -> (k1, a1) -> Map.Map k1 a1
          (bound at src/Lecture8.hs:33:5)
        fn :: a -> a -> a (bound at src/Lecture8.hs:30:15)
        fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
          (bound at src/Lecture8.hs:30:1)

I have tried removing the type annotation from foldfn, which yields a different error:

Lecture8.hs:32:26: error:
    • No instance for (Ord k) arising from a use of ‘foldfn’
      Possible fix:
        add (Ord k) to the context of
          the type signature for:
            fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
    • In the first argument of ‘foldl’, namely ‘foldfn’
      In the expression: foldl foldfn Map.empty
      In an equation for ‘fromListWith_’:
          fromListWith_ fn
            = foldl foldfn Map.empty
            where
                foldfn m (key, val) = Map.insertWith fn key val m

Any help much appreciated.

Upvotes: 0

Views: 227

Answers (1)

Random Dev
Random Dev

Reputation: 52280

I think everything is all right with your implementation - you need ScopedTypeVariables to work with the type of the inner function though:

{-# LANGUAGE ScopedTypeVariables #-}

fromListWith_ :: forall a k. Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn :: Map.Map k a -> (k, a) -> Map.Map k a
    foldfn m (key, val) = Map.insertWith fn key val m

Without those scoped variables the a in foldfn :: (Map.Map k a) -> (k, a) -> Map.Map k a is assumed to be different type-variable (a bit like shadowing) - same with k of course.

Note: to have this work you need the explicit forall there too!

if you don't like this just remove the signature:

fromListWith_ :: Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn m (key, val) = Map.insertWith fn key val m

PS: you where missing a Ord k constraint too.

insertWith includes this constraint so you need to propagate it.

Upvotes: 1

Related Questions