Unification & Substitution

Question

In Haskell, I have defined a polymorphic data type Subst a with a single constructor S :: [(String, a)] -> Subst a as so:

data Subst a where
    S :: [(String, a)] -> Subst a
    deriving (Show)

I want to define a function get::String -> Subst a -> Maybe a that takes a variable name and a substitution, and returns the value for which that variable must be substituted. If the substitution is not defined on the variable, the function should return Nothing.

I've tried the following:

get :: String -> Subst a -> Maybe a
get str (S[]) = Nothing
get str (S((a,b):xs)) = if str == a then Just b
    else get str xs

But I'm getting errors. Any ideas why?

Answer 1

get str (S((a,b):xs)) = if str == a then Just b
    else get str xs

xs is a list of type [(String, a)], but the second argument of get must be a Subst a. It would work if you used a constructor to construct a value of the correct type,

get str (S((a,b):xs)) = if str == a then Just b
    else get str (S xs)

but it is simpler to use the list directly to look up the variable,

Prelude> :t lookup
lookup :: Eq a => a -> [(a, b)] -> Maybe b

so

get str (S xs) = lookup str xs

does exactly what you want.