Haskell n00b – value/type constructors confusion
As I slowly attempt to teach myself Haskell and the basics of functional programming, I will try and post some of my thoughts and confusions as they come. If anyone sees me doing something wrong, please speak up. My ego is not tied to the code I post so much as the fact that someone read it and took the time to respond.
As I was reading chapter 3 of Real World Haskell yesterday, I got myself all turned around. And, like any good man driving a car, I refused to ask for directions and kept driving around until things started to look familiar again.
The task at hand was to write a function which would convert the List data type the authors defined earlier in the chapter to a native array.
data List a = Cons a (List a)
| Nil
deriving (Show)
fromList (x:xs) = Cons x (fromList xs)
fromList [] = Nil
The authors also gave an example of a function which would convert arrays to Lists. My job was to create the reverse. My first attempt is below:
fromList2 List a b = a : (fromList2 b)
fromList2 Nil = []
This had some potential, but doesn’t compile complaining about a lack of a data constructor ‘List‘. My confusion was around the difference between the type constructor and the value constructor. List is the type constructor for the List type. Cons is the value constructor for an object who type happens to be a List type. Coming from a Java/C# background, when I first read about pattern matching, I immediately assumed it was matching against the type of objects. Well, that’s true and false. In Java the type and value of something are two different things. In Haskell, they are linked and can not change. Therefore, when writing a pattern matching function, we need to look at the value of the parameter (ie the value constructor and values) and NOT the “type”. I should have realized this when I wrote the second line. Nil is not the same kind of construct as List, which should have set of a red flag for me.
To make things even more confusing, when I wrote the above code to try and test my new function, I head already read the author’s comments about how since type constructors and value constructors are really two different things and can never be used where the other was intended, they are normally named the same (Cons was used for readability). Normally, and how I typed it out at first without realizing it, it would be written with both constructors named the same – List.
The other confusing thing for me was the difference between type variables and “normal” variables. When defining the new abstract type List, ‘a‘ represents a type variable, or a place holder for the type of the actually object passed in. Since nothing within the definition of a List needs to know the type of the parameter, we can get away with it being unknown until creation time. When defining a function, the variable no longer represents the objects type, but the object itself. Haskell is strongly and statically typed, but doesn’t require you to specificy exactly what type a variable is. It inferes it from how you use it.
Thus, the correct anser is:
fromList2 (Cons x xs) = x : (fromList2 xs)
fromList2 Nil = []
Trying to work with the type constructors, value constructors, type variables, etc all at once was a bit much. The way I really figured this out was to build up to it with another example. Here is the code I wrote which taught me what I was doing wrong above. Maybe it will help someone else someday.
myListOrgChart = Cons "ben" (Cons "boss" (Cons "ceo" Nil))
listOrgChart = fromList2 myListOrgChart
data Person = Employee Int String Person
| Consultant String
| NoOne
deriving (Show)
name (Employee _ name _) = name
name (Consultant name) = name
managerName (Employee _ _ manager) = name manager
managerName (Consultant name) = name
orgChart (Employee _ name manager) = name : orgChart manager
orgChart (Consultant name) = name : name : []
orgChart NoOne = []
ceo = Employee 1 "ceo" NoOne
boss = Employee 2 "boss" ceo
ben = Employee 3 "ben" boss
joe = Consultant "joe"
benOrgChart = orgChart ben
1 comment