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

March Lambda Lounge

Posted in lambdalounge by youngnh on 03.06.09

4th ever Lambda Lounge meeting happened last night, and even though I had to leave early, there was plenty going on to like so I wanted to spill some of my impressions quickly this morning. This meeting gets cooler and cooler every month. Appistry provides beer (as in free) and pizza (I had a slice with Doritos, jalapenos and pepperoni, changed my view of things) and next month the Lounge covers Factor and the long-awaited Parrot VM.  The month after that will behold a language shootout, all topics upholding the upward trend. (thanks for the correction, Alex!)

Ken Sipe opened the night with an introduction to F#. Ken mentioned that this was his first LL, but he’s obviously done the presenting thing before. His talk was a smooth sweep of the F# language. A couple of things he said rang particularly true:

  • F# is going to be big. As far as functional programming goes, most languages have power, but very few have the deep reach to actually touch developers at their desks. F# has tooling, Microsoft support and upcoming first class inclusion into the .NET platform.

Say what you want about Microsoft, but the C# language has continually impressed with a flexibility and forward progression that Java doesn’t feel like its generating anymore. With F# on the horizon and Mono making it possible to work with .NET in Linux, a lot of functional programmers may be looking Redmond’s way in the very near future.

  • F# reduces noise on the signal that syntax descended from C tends to introduce.

Ken had a couple of great slides that illustrated that if nothing else, functional programming allows the programmer to express ideas with little structure, braces, etc. surrounding them. F# source is a compressed package of the data you are working on, the operations you are performing and little else. On this point, the Ruby community’s sense of aesthetics — that something functional should be short and expressive — has made all programmers look at their production code and increased all of our appetites for terseness. Until now, our languages have been making our fingers do work, and as far as IDEs and autocomplete have come, F# really brings programmers down closer to the ideas they are expressing.

  • F#’s discriminated unions and pattern matching are killer.

These complementary features allow for a style of programming that is expressive and beautiful and instantly readable. Discriminated unions make disparate data simple to break down into component parts and associate with an overarching type. Pattern matching allows a function to introspect as deep into a type as it wants, as well as pick and choose cases to implement functionality with. Long branching if chains and switch statements have no reason for existence in F#. Ken’s exact quote was “we need this”.

It was lighthearted and exploratory. For those who know monads, Michael talked about the Maybe monad. For those of you who don’t, he stressed that monads aren’t something that you can impart knowledge of on someone else by force of will, but that everyone has to struggle with and learn for themselves. For his part on our journey, though, Easter brought props! He used a coozie, a water bottle, a two-foot length of cardboard tube, and maybe there was more, I don’t know, I had to leave after his first example of making a beverage by adding water, hops and malt. :)

Michael’s code was in Haskell and it made an excellent companion to Ken’s F# introduction as both languages share a common heritage and similar syntax. Until this is our jobs and we hate looking at Haskell or F# as much as we hate looking at Java, this is all strange and weird and promising and Easter captured that in his words, slides and examples. A lot of people asked a lot of questions at the end of Ken’s talk. I imagine the situation was similar after Michael’s. The functional space is huge, F# is only a tiny part. Monads are only a tiny part. This is certainly early-adopter territory. As many questions asked about F# were observations on various other aspects of functional programming people had encountered. This is the current spirit of the Lambda Lounge. Almost like a bunch of spies reporting back to each other on super top-secret new weapons. Until all of this is clear, the Lounge is a great place to trade intel.

cpuspeed

Posted in hardware by youngnh on 03.06.09

While putting together my answers for all of the computing power currently available to me, I came across something interesting. My primary computer is a Thinkpad T42 running Fedora 10. It has an Intel Pentium M, and according to the ‘About This Computer’ dialog, its clocked at 1.7GHz.

Imagine my surprise when I ran cat /proc/cpuinfo and found this:

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 13
model name : Intel(R) Pentium(R) M processor 1.70GHz
stepping : 6
cpu MHz : 600.000
cache size : 2048 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 2
wp : yes
flags : fpu vme de pse tsc msr mce cx8 mtrr pge mca cmov pat clflush dts acpi mmx fxsr sse sse2 ss tm pbe up bts est tm2
bogomips : 1196.11
clflush size : 64
power management:

600MHz!!?? Turns out my CPU, like most Intel CPUs have frequency scaling to cut down on power consumption and heat production when you don’t need all the raw horsepower. I must have caught my processor sleeping. The cpuspeed daemon will help you scale your CPUs frequency as it is needed. Something to think about when you’re wondering if everything is running just a tad bit slower than you think it should.

Follow

Get every new post delivered to your Inbox.