[Haskell-cafe] non-uniform recursive Trie

[Andres Löh]

Hi Kazu.

> I'm now studying Trie in Okasaki's "Purely Functional Data Structure".
> Attached is the program in its appendix. I cannot understand how to
> use "empty", "look" and "bind". For instance, if I type 'look "" empty',
> I got an error:
>
>> look "" empty
> <interactive>:2:1:
>     No instance for (FiniteMap m0 [Char])
>       arising from a use of `look'
>     Possible fix: add an instance declaration for (FiniteMap m0 [Char])
>     In the expression: look "" empty
>     In an equation for `it': it = look "" empty
>
> I have no idea how to determine the parameter 'm'. Suggestions would
> be appreciated.

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.

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.

Cheers,
  Andres