Two Guys Arguing

Haskell n00b – value/type constructors confusion

Posted in functional programming by benjaminplee on 03.06.09

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


5 Responses

Subscribe to comments with RSS.

  1. izaak said, on 03.08.09 at 3:07 am

    I’ve been going through the (online) book as well very slowly (i have the book as well, but i find some of the comments in the online version very helpful). Wondering how you found the Graham scan questions?

    Apparently the irc channel is very helpful (I have yet to go there), but i’ve been finding to be quite helpful when I diverge from the questions.

    So far that (chapter 3) is the one i’ve gotten the most out of – the exercises seem to be less thought out in in the next couple (i’m only up to ch7, and it’s going very slowly).

    • benjaminplee said, on 03.08.09 at 5:10 pm

      Thanks for the tips/resources. Its always nice to hear about someone else who is going through the same process. Good luck with your progress.

  2. Jeff said, on 03.08.09 at 4:33 am

    A minor note – the built-in type you’re converting to and from isn’t an array, it’s a list too. In fact, its implementation is pretty much identical to your ‘List’ type, except it spells “List a” as “[a]”, “Cons” as “:”, and “Nil” as “[]”.

    • benjaminplee said, on 03.08.09 at 5:12 pm

      Thanks for pointing that out. You’re right. As soon as I read your comment I realized what I had done. While I was writing the post I was coding something up in Ruby and started getting my names confused.

  3. […] the year, and at that same time a group of very bright gentlemen that I work with had resolved to learn Haskell. Following along, I dove into the Haskell community a bit and became very impressed with the things […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s