Functions as types in haskell

Question

I have confusion using types which are functions.

Let say I want to implement a dictionary, which when given a and b returns Maybe b.

type Dict a b = a->Maybe b

How can I implement an insertion function for this dictionary?

insertDict :: (Eq a) => a -> b -> (Dict a b)-> (Dict a b)

I have come up with the following thing

insertDict x y mydict = \a->Just y

but it is not correct and will discard the previous dictionary.

Answer 1

You can use a "chain of responsibility" pattern: the insert function checks if the argument to the result Dict matches with its own key, otherwise it delegates on the previous Dict which received as argument.

type Dict a b = a -> Maybe b

insertDict :: (Eq a) => a -> b -> Dict a b -> Dict a b
-- Note that the k' is the argument of the result dict function
insertDict k v dict k' = if k == k' then Just v else dict k'

emptyDict :: Dict a b
emptyDict _ = Nothing

Some examples in ghci:

Λ insertDict 'a' (1::Int) emptyDict $ 'a'
Just 1
Λ insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'a'
Just 1
Λ insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'x'
Nothing

Representing maps as functions is good as a first approximation, but this representation has a number of drawbacks:

• The complexity of searching for a value is linear in the number of keys.
• Functions are pretty "opaque", which means you can't inspect or serialize the map as you could do if you had used a data type.