[Haskell-cafe] non-uniform recursive Trie

Kazu Yamamoto ( 山本和彦 ) kazu at iij.ad.jp
Mon Oct 29 09:52:16 CET 2012


> The code you've listed shows how to go from an already existing
> instance of class FiniteMap to an instance for the same class that
> adds a trie structure on top of the underlying finite map
> implementation. You have to add a "base instance" to the code so that
> it can work. For example, by importing Data.Map and adding an
> "instance FiniteMap Data.Map.Map Char" with the appropriate
> definitions.

Thank you.

I added the following:

instance FiniteMap Map Char where
    empty = M.empty
    look = M.lookup
    bind = M.insert

> You'll also need to add extra type information to "empty" in your
> example expression so that GHC can know which instance you actually
> want.

Is the follwing what you mean?

> look "bar" $ bind "bar" 1 $ (empty :: Trie (Map Char) String Int)
Just 1


FiniteMap uses another finite map, Data.Map in this case. I wonder why
we can call it bootstrapping...


More information about the Haskell-Cafe mailing list