One of the things I got myself for Christmas was Chris Reade's Elements of Functional Programming. Despite being nowhere near done with some other books I'm working through, I cracked it open today. Page three has the following gem: "From this point of view, it is argued that the assignment statement is considered harmful in high-level languages, just as the 'goto' statement was considered harmful for structured programming in the sixties (Dijkstra, 1968). Note that it is the use of assignments that takes most of the blame for not allowing separation of concerns when programming."
That's a pretty bold statement, no? However, Chris Reade is somewhat less widely read than E. Dijkstra; googling for either "assignment considered harmful" (or variants) shows no front page hits that trace back to Reade. Much as I am inclined to agree with that statement, I recognize that my opinion is rooted in many years' experience with the complexities involved in programming with traditional assignment semantics, and have not had nearly as much opportunity to see the downside of purely functional programming.
So what did I find when I googled for "assignment considered harmful?" Well, not much that was actually on topic. The functional programming outlook was represented by this blog post. From a different viewpoint, there was this paper, which looks at four different semantics for "x=y", none of which involves immutable data, and concludes that traditional assignment semantics are the worst of the four options!
Wednesday, December 29, 2010
Sunday, December 5, 2010
The Type of []
That should be "The Type of []", but it seems that blogger won't let you change the font on the heading.
Anyway, so the section of Learn You A Haskell where it introduces value constructors says this: "Value constructors are actually functions that ultimately return a value of a data type." (For example, Just is function that takes an argument of type a and returns a value of type Maybe a). That seemed pretty straightforward and I think I internalized it well on the first pass.
The LYAH section on type constructors also mentions the fact that type constructors are functions. So I kind of knew that fact but didn't really know it until I got unto the Functor section and the explanation that fmap is just a generalization of map. Because the type of fmap is (Functor f) => (a->b) -> f a -> f b. My brain began to rewind a bit, trying to figure out how [Int] fit the type signature f a with a bound to Int. Then it hit me that [] is just syntactic sugar for a type constructor, which is just a function that creates a type. I'm just so used to that class of objects being builtin language keywords that this took more than a bit of adjustment.
In other languages, list<int> myList is just a set of keywords you say to make the compiler give you a list of integers; a compiler feature or even a compiler-level function if you will. Haskell gives you the list type constructor as an actual function. EDIT: The function is evaluated at compile time, but it is nonetheless a function.
Anyway, so the section of Learn You A Haskell where it introduces value constructors says this: "Value constructors are actually functions that ultimately return a value of a data type." (For example, Just is function that takes an argument of type a and returns a value of type Maybe a). That seemed pretty straightforward and I think I internalized it well on the first pass.
The LYAH section on type constructors also mentions the fact that type constructors are functions. So I kind of knew that fact but didn't really know it until I got unto the Functor section and the explanation that fmap is just a generalization of map. Because the type of fmap is (Functor f) => (a->b) -> f a -> f b. My brain began to rewind a bit, trying to figure out how [Int] fit the type signature f a with a bound to Int. Then it hit me that [] is just syntactic sugar for a type constructor, which is just a function that creates a type. I'm just so used to that class of objects being builtin language keywords that this took more than a bit of adjustment.
In other languages, list<int> myList is just a set of keywords you say to make the compiler give you a list of integers; a compiler feature or even a compiler-level function if you will. Haskell gives you the list type constructor as an actual function. EDIT: The function is evaluated at compile time, but it is nonetheless a function.
The Haskell Road . . .
Time for another quick book report. The Haskell Road to Logic, Maths, and Programming advertises itself as a from-the-bootstraps guide to, well, logic, math, and programming. I've finished the first 4 chapters, a little more than a third of the book. What do I think so far?
It's a very good guide to the foundations of mathematics. Though I have a math degree, this is something that never really clicked for me before. The ad copy states the only knowledge the book presumes is secondary school mathematics. I don't have that perspective, but I think the book does a good job of explaining the foundations of mathematics without assuming any more knowledge than that. I'm not so sure it's as successful on the programming side -- I think there are several places where a reader with no programming experience would be quite confused about the example programs.
It seems to me that the book's real target audience is programmers who want to learn some Haskell and learn the fundamentals of logic and math and how to use formal methods in Haskell. So far, it accomplishes those goals fabulously.
It's a very good guide to the foundations of mathematics. Though I have a math degree, this is something that never really clicked for me before. The ad copy states the only knowledge the book presumes is secondary school mathematics. I don't have that perspective, but I think the book does a good job of explaining the foundations of mathematics without assuming any more knowledge than that. I'm not so sure it's as successful on the programming side -- I think there are several places where a reader with no programming experience would be quite confused about the example programs.
It seems to me that the book's real target audience is programmers who want to learn some Haskell and learn the fundamentals of logic and math and how to use formal methods in Haskell. So far, it accomplishes those goals fabulously.
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:
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!
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.
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.
Subscribe to:
Posts (Atom)