Haskell: The difficulty of embedding context (Eq a) in data declarations

Question

I write a simple hash tree structure in the following hash_lookup.hs program:

 module Main where data (Eq a) => HashTable ab = HashChildren (a, [HashTable ab]) | Hash (a, b) deriving (Show) getKey :: HashTable ab -> a getKey (HashChildren (k, hs)) = k getKey (Hash (k, h)) = k lookUp :: [a] -> HashTable ab -> Maybe (HashTable ab) lookUp [] table = return table lookUp _ (Hash _) = Nothing lookUp (p:path) (HashChildren (_, ts) ) = lookUp path ( head ( dropWhile (\x -> (getKey x) /= p) ts ) ) 

getKey is designed to retrieve the root key of the given HashTable, and lookUp accepts a list of strings and must follow the first path that it finds until it reaches the full path or works (I know this isn’t a Natural behavior for a tree, but this is what my textbook wants. "

I have two questions: 1) Why am I getting an error message telling me that a /= a (from the last line) is not valid, as there is No instance for (Eq a) (error message in the terminal), despite (Eq a) in the data declaration?

2) Besides the error I get, and the seemingly strange behavior of the search function, is this a good or idiomatic Haskell?

thanks

Answer 1

One of the common "gotchas" in Haskell is that if you put class constraints in a data declaration, each function that uses this type must also have class constraints. For this reason, your data declaration is not idiomatic in Haskell, and you must eliminate its class restriction. This does not give you anything to declare a class constraint in the data declaration anyway.

In principle, function types should repeat the class constraint. How else does the user of the function know that he must use an instance of the classes in question? Note that you can have a function f defined in terms of a function g defined in terms of h , which is defined in terms of your type HashTable ab , so f does not mention your HashTable >, but because of type dependencies it takes an argument of type a , which is indirectly and ultimately used as the first parameter of your HashTable type. f type must have class constraint, Haskell correctly points out this way and it will reject type annotations if they are missing.