Haskell swap algorithm

Question

I am trying to write a substitution algorithm in Haskell. I defined the type of polymorphic data Subst a with one constructor S::[(String, a)] -> Subst a as follows:

 data Subst a = S [(String, a)] 

Now I want to write a function single::String -> a -> Subst a to construct a substitution for only one variable

This is what I tried:

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

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

Does anyone know what I'm doing wrong?

Answer 1

A data constructor is not the same as a constuctor type

In your code, a constructor of type Subst data constructor S

Type constructors are used to create new types, for example. in data Foo = Foo (Maybe Int) Maybe is a type constructor, Foo is a data constructor (and also a type constructor, but they can be called differently, as you discovered). Data constructors are used to instantiate types (also not to be confused with instantiating a polymorphic type, for example, Int -> Int is an instance of a -> a ).

So you need to use S if you want to map the pattern in your single function. Not Subst .

Hope this makes sense, if not, tell me :)

PS data constructors are, in every sense and purpose, functions, which means that you can do the same with them as you usually do with functions. For instance. you can make map Bar [a,b,c] , and it will apply a data constructor to each element.

Answer 2

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

The [(str, a)] creates a list with one element. This element is a tuple (or "pair"), and str is the left side of the tuple, and a is the right side of the tuple. The above function then wraps this singleton list in constructor S to create a value of type Subst a.

The result is a list containing the rule for one substitution from str to a .