Sunday, November 28, 2010

map map and Type-Wrangling

So there I was, reading along in School of Expression, and one of the exercises asked me to compute the type of map map.

Well, map is of type (a->b) -> [a] -> [b].  Applying precedence rules gives (a->b) -> ([a]->[b]).  That is, map takes a function from a to b and returns a function that takes a list of a and returns a list of b.  So if we are applying map to a map, then... Well, let's start by using a' and b' for the outer call to map.  Then a' must be of the form (a->b) and b' must be of the form ([a]->[b]).  Which means that the outer map must have a type of ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]].  That must be the answer.  So I pull up GHCi and take peek at :t map map and it brings me back to earth:
 [a->b] -> [[a]->[b]]

Hmm.  Let's try this again, bottom up this time.  What's map map xs going to look like?  Well, we know that xs better be a list, so map map [a, b, c] will be [map a, map b, map c].  So our xs are mappable functions; for example, map map [(<3),(<4),(<5)].  This gives us [map (<3), map(<4), map (<5)].  This is a list of functions, each of which takes a list of Num and returns a list of Bool

So where did I go wrong in the first place?  Let's take a closer look at the first answer:  ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]].  The first argument looks suspiciously like the signature for map itself.  And [(<3),(<4),(<5)] does indeed look suspiciously like map (<) [3..5]!  But the whole expression would then be map map map (<) [3..5].  Or maybe not.  Actually it would be map map $ map (<) [3..5], a rather different creature.  Mind the dollar sign. 

In fact, as a beginning Haskell programmer, I’ve been bitten by function precedence and the $ operator more than anything else.  This results in a cryptic type error from the compiler that I’m just beginning to get familiar with.  So my advice to others is this:  if you are getting an incomprehensible type error message from the compiler, try using parentheses to group your expressions.  That will fix many of your problems (and if you have any Lisp experience, those familiar parens are like a gateway drug). 

Back to map map, and its type.  Looking at the type I derived, and paying attention to the context, it all becomes clear.  Because ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]] is the type of the outer map, which is known to have map as its first argument.  So indeed the type of the outer map in map map is  ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]], but the type of map map as a whole is [a->b] -> [[a]->[b]].  Or, what GHC said.  Duh!

Saturday, November 27, 2010

State of the Blog, and Resources for the Student of Haskell

So I've decided to learn Haskell.  This blog exists first and foremost to keep me on track.  I also hope it is of use to other Haskell newbies.

A bit about me: I have 20 years' experience in software development in scientific computing and aerospace, most of it in C/C++ on various Unix platforms.  I also have some real industry experience in Lisp, and that led to my interest in Haskell.

My Experiences So Far
I've been at this several weeks already.  Readers may find they need some Haskell experience to understand this blog.  But Haskell is a deep enough language that I am still clearly in the beginner camp. 

I began with Hudak's The Haskell School of Expression and a download of GHC to play with at lunch time.  This was fine until SOE began to use exercises that required a nonstandard library that Google couldn't seem to find.  I've not had the time to make a concerted search effort for that library, but I'm still reading the text from time to time and still gaining something from it.  The book is well-written.  Though written by an academic, the book is not pitched at an academic audience, and I find that it stays clear of the 'dry and difficult' to read category. I'm presently in Chapter 5 of this book.
Concurrently, I was working my way through Learn You a Haskell For Great Good!  This is written in an informal, easy-to-read manner.  I like it a lot, it approaches the level of the Head First books, and that's great praise coming from me (though I'm sure not all the HF books are of the same high standard).   I've made my way through the first monad chapter.  LYAH's biggest weakness IMO is that is has no full-length exercises, so be sure to assign yourself one at the end of each section.

Speaking of monads, a bit of advice to other newbies:  browsing through reddit or stackoverflow, you might be tempted to follow one of the many "how to understand monads" links.  Don't do that until you've written at least one Haskell program of a couple hundred lines or more.  I wasted a bunch of time reading monad tutorials long before I was ready for them.  My limited understanding of monads is better for having read them, but it would be better yet if I had read them later.

I have written my first real Haskell program: it parses log files and extracts and formats data.  It's the sort of program that might have as easily been written in bash or Perl, but it was a good exercise for me.  

Other Valuable Resources
The haskell-cafe and haskell-beginners mailing lists are actively used, and a great resource.  Most of the haskell-cafe topics are more advanced, but often give you an overview of some of the more advanced or nonstandard languages features.  I find it valuable but others may not find it valuable until they have written several Haskell programs.

The Haskell Reddit and the Stackoverflow Haskell tag are also quite useful.  The Programming Reddit occasionally has topics of interest to a new Haskeller.