Substitution Algorithm in Haskell

Question

I'm trying to write a substitution algorithm 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 = S [(String, a)]

I now want to write a function single::String -> a -> Subst a for constructing a substitution for only a single variable

This is what I tried:

single::String -> a -> Subst a
single s1 (Subst a) = s1 a

However, I'm getting this error: Not in scope: data constructor 'Subst'

Does anyone have insight to what i'm doing wrong?

Answer 1

The data constructor is not the same thing as the type constuctor

In your code the type constructor is Subst the data constructor is S

Type constructors are used to create new types, e.g. in data Foo = Foo (Maybe Int) Maybe is a type constructor, Foo is the data constructor (as well as the type constructor, but they can be named differently as you discovered). Data constructors are used to create instances of types (also don't confuse this with creating an instance of a polymorphic type, e.g. Int -> Int is an instance of a -> a).

So you need to use S when you want to pattern match in your single function. Not Subst.

Hopefully that makes sense, if not, please tell me :)

P.S. data constructors are, for all intents and purposes, functions, which means you can do the same things with them that you'd typically do with functions. E.g. you can do map Bar [a,b,c] and it will apply the data constructor to each element.

Answer 2

single :: String -> a -> Subst a
single str a = S [(str, a)]

The [(str, a)] part creates a list with one element. That element is a tuple (or "pair"), with str as the left part of the tuple and a as the right part of the tuple. The above function then wraps that single-element list in the S constructor to create a value of type Subst a.

The result is a list that contains the rule for a single substitution from str to the value a.