Getting type declarations for Tries right

Question

I'm using the list-tries package:

import qualified Data.ListTrie.Patricia.Map as TM
import qualified Data.ListTrie.Patricia.Set as TS
import qualified Data.Map as Map

I have a list of strings, which I want to store in a Trie-Map consisting of Trie-Sets, like this:

-- vocabs :: [String]
trie = TM.fromListWith' (flip TS.union) $ map (\v->(sort v, TS.singleton v)) vocabs

(this is for looking up a set of letters in the outer trie, then looking up a specific combination of letters in the resulting trie).

I can understand that Haskell does not know which exact type the trie has, because I have nowhere specified which type of map to use. I thought I could do this by adding the declaration

trie :: TM.TrieMap Map.Map Char (TS.TrieSet Map.Map Char)

but it seems not to be enough. I'm still getting error messages like

No instance for (Data.ListTrie.Base.Map.Map Map.Map Char) arising from a use of TrieM.fromListWith'

Possible fix: add an instance declaration for (Data.ListTrie.Base.Map.Map Map.Map Char)

In the expression: TrieM.fromListWith' TrieS.union

In the expression: …

and similar ones for the of TS.singleton, TM.lookup, TS.member and TS.findMin.

I don't seem to get the actual problem, and also don't know how to add type declaration to [inline] expressions (I've seen it a few times, but didn't get the syntax). Could you please help me out?

Answer 1

I can't reproduce the problem.

Without the signature for trie, I get - unsurprisingly - an ambiguous type variable error (well, two), for the reason stated in the question, together with a possible cause (that really is the cause, it's the monomorphism restriction), and two probable fixes (disabling the monomorphism restriction makes it compile, but giving an explicit type signature is the better fix). The error message is appended below for overinterested souls (it's from 7.6.1).

With the type signature, it compiles cleanly.

In the light of that, I cannot diagnose the problem with certainty, but experience together with the error message you got provide a probable cause.

You got a very specific message that the required instance is not in scope:

No instance for (Data.ListTrie.Base.Map.Map Map.Map Char) arising from a use of TrieM.fromListWith'

Possible fix: add an instance declaration for (Data.ListTrie.Base.Map.Map Map.Map Char)

On the other hand, the list-tries package explicitly provides such an instance.

The typical cause for such a situation is that there are two distinct classes or two distinct types involved that come from different versions of the same package.

In this case, you have likely built list-tries against one version of containers, and later installed a different version of containers, and the import qualified Data.Map as Map imports the Map.Map type from the newer package version, while the instance in list-tries is for the older version.

Check whether you have more than one version of containers installed with

ghc-pkg list containers

Check on which version of containers your list-tries depends with

ghc-pkg describe list-tries

In the depends field of the output of that, there will appear something like

containers-0.5.0.0-e49be7a240765a4edc5c09f677ec6a81

listing the package version and the ABI hash of the containers package list-tries was built with.

If the version doesn't correspond to the newest version of containers you have installed, the above situation arises unless the version of containers to use is explicitly specified when invoking GHC, either directly with a -package flag, or indirectly via a .cabal file.

If that is the case, you can

• explicitly specify the version of containers to use every time you use list-tries
• unregister the newer version(s)of containers (could break other packages)
• rebuild list-tries against the newer version of containers

---

TrieTest.hs:12:8:
    No instance for (Data.ListTrie.Base.Map.Map map0 Char)
      arising from a use of TM.fromListWith'
    The type variable `map0' is ambiguous
    Possible cause: the monomorphism restriction applied to the following:
      trie :: TM.TrieMap map0 Char (TS.TrieSet map1 Char)
        (bound at TrieTest.hs:12:1)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
    Note: there are several potential instances:
      instance Eq k =>
               Data.ListTrie.Base.Map.Map Data.ListTrie.Base.Map.AList k
        -- Defined in `Data.ListTrie.Base.Map'
      instance Ord k => Data.ListTrie.Base.Map.Map Map.Map k
        -- Defined in `Data.ListTrie.Base.Map'
      instance Enum k =>
               Data.ListTrie.Base.Map.Map Data.ListTrie.Base.Map.WrappedIntMap k
        -- Defined in `Data.ListTrie.Base.Map'
    Possible fix:
      add an instance declaration for
      (Data.ListTrie.Base.Map.Map map0 Char)
    In the expression: TM.fromListWith' (flip TS.union)
    In the expression:
      TM.fromListWith' (flip TS.union)
      $ map (\ v -> (sort v, TS.singleton v)) vocabs
    In an equation for `trie':
        trie
          = TM.fromListWith' (flip TS.union)
            $ map (\ v -> (sort v, TS.singleton v)) vocabs

TrieTest.hs:12:31:
    No instance for (Data.ListTrie.Base.Map.Map map1 Char)
      arising from a use of `TS.union'
    The type variable `map1' is ambiguous
    Possible cause: the monomorphism restriction applied to the following:
      trie :: TM.TrieMap map0 Char (TS.TrieSet map1 Char)
        (bound at TrieTest.hs:12:1)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
    Note: there are several potential instances:
      instance Eq k =>
               Data.ListTrie.Base.Map.Map Data.ListTrie.Base.Map.AList k
        -- Defined in `Data.ListTrie.Base.Map'
      instance Ord k => Data.ListTrie.Base.Map.Map Map.Map k
        -- Defined in `Data.ListTrie.Base.Map'
      instance Enum k =>
               Data.ListTrie.Base.Map.Map Data.ListTrie.Base.Map.WrappedIntMap k
        -- Defined in `Data.ListTrie.Base.Map'
    Possible fix:
      add an instance declaration for
      (Data.ListTrie.Base.Map.Map map1 Char)
    In the first argument of `flip', namely `TS.union'
    In the first argument of TM.fromListWith', namely `(flip TS.union)'
    In the expression: TM.fromListWith' (flip TS.union)