A maze of twisty little Strings, all alike

This post was spurred by a recent discussion of whether or not Haskell code just works the first time you try it.  As a less-than-expert Haskeller, my answer to that is "not so much."  But even as a less than expert Haskeller, I find that my Haskell code needs much less debugging time than when I write in another language.  It feels like a difference of kind, not one of degree.  So I understand where the original claim comes from, even if I ultimately find it to be overstated.  What's great about Haskell is that it has lots of language features that support robust code.  Immutability of data gets lots of press, and deservedly so, but Haskell has many other features that help. 

What this post is about is one of the Haskell techniques that helps me write code that is more solid.  That technique is using type aliases to differentiate amongst the various kinds of strings that I am using. 

A Haskell newbie's guide to Snap, Part 3

This is a followup to Part 1 and Part 2.  Those posts covered the basics of using Snap and Heist, and their APIs for accessing data from the HTTP request and from the splice instance.  This post will show how to access SQL data with the HDBC package (in this case, we'll use PostgreSQL).  Along the way, I hope to give a better picture of how all the pieces fit together (though I'd welcome comments from experienced Snappers on how the code might be improved).  

A Haskell newbie's guide to Snap, Part 2

This post is an overdue followup to Part 1.  I'll try not to repeat much of that material; review that link if you need a refresher.  Here I'll show how to use Snap and Heist to save some data from an HTML form.  That will involve using Snap to pull POST/GET data from the request and then building HTML elements for the page with the Text.XmlHtml library. 

We'll use the same simple cheese database as our background.  This database has four columns: name, country, price, and stock.  We want to have a single page that lets us edit an existing cheese record or create a new one.  There will be two forms.  The first form lets us enter the name to edit/create, and has an Edit/Create button that fills data into the second form.  The second form has text inputs for each of the data columns, and a Save button.  When we first land on our page, we're at /cheese_template.  Pressing the Edit/Create button sends us to /cheese_template?name=Epoisses, and pressing the Save button sends us to /cheese_template?_task=save. 

A Haskell newbie's guide to the Snap framework

NOTE: the updated tutorial for Snap version 0.8 can be found here .

I've spent a bit of time working up a simple application in the Snap web framework.  This proved to be a bit of a challenge: the documentation for Snap is definitely a work in progress, and doesn't cater well to a Haskell newbie such as myself.  This account is intended to help others in my position get up to speed on Snap, by filling in some of the information that the tutorial's authors may have taken for granted.  It is not intended as a standalone introduction to Snap. If you want to use this document to help you learn Snap, I would suggest the following steps:

• Read the three Snap documents in the TUTORIAL section
• Read through this document
• Build an example application

Snap was absolutely easy to install and get running.  The API introduction walks you through creating a hello-snap app from scratch.  The app has a built-in HTTP server that serves a few simple web pages.  My goal was to create a web page that integrated data from a PostgreSQL database.  

If I Were Given a Re-do from the Beginning

I'll get to the title topic in just a minute.   But first, more about Real World Haskell.  Currently I'm a little more than halfway through the book, and still liking it quite a lot.  I'm currently halfway through the "Programming With Monads" chapter.  I'm feeling that this chapter is a little dense with text and that more incremental baby-steps exercises would do it some good.  Certainly they would do me some good.  So I'm stopping where I am until I have time to sit down and write some more monadic code.  I imagine it will take a few repetitions until I'm comfortable with it, but that seems like a fundamental skill if you want to write Haskell. 

Now for the main feature: if I had to do it all over again, here's what I would do to learn Haskell from scratch:

• Start by reading Learn You A Haskell.  All the way through.  
• Really get into some code with Write Yourself a Scheme. 
• Read Read World Haskell from the very beginning, and don't skim through the earlier chapters; they have a different and useful way of presenting the basics.  Yet I wouldn't start here; I learn best when I see a topic from a couple of different directions. I have the dead tree version of the book but there's a free PDF available here.

And here's what I would not do:

• Read Monad tutorials early in the learning process.  I wouldn't recommend it before reaching the monad chapter in Real World Haskell.  First of all, the monad sections in Learn You A Haskell and Real World Haskell are quite good.  Second, monad tutorials are more effective if they are immediately reinforced by some coding exercises. I think the best path to understanding monads is by using the damn things. 
• Read any type theory content until . . . well, past where I am now.  I have read some of this stuff and have yet to see any useful connection to actual Haskell code.  I'm sure I'll get there eventually, but I'm not there yet. 
• Do not start Haskell School of Expression unless you first find the source code and get it running. 

Finally, there's something I might do: read The Haskell Road to Maths, Logic, and Programming.  That book is rather less a book about programming Haskell and more a book about the foundations of mathematics.  If that sounds interesting, then the exercises in the book are a nice way to get some coding practice as you are coming up to speed in Haskell.

Getting More from the Type System

This blog post from Tony Morris really got me thinking about the advantages of a powerful static type system like Haskell's.  That blog post (along with others such as this one) are great pointers for getting the most mileage from the type system.

When I first started with Haskell, I was pleased with the effect that the type system had on the code-test-debug-refactor cycle by keeping the type errors at compile time -- yet not requiring lots of tedious, error-prone boilerplate to support that.  I found that code was much more likely to work with minimal debugging.  Along with the conciseness of the code, this made for a more engaging and satisfying experience at the "hacking" level.  This is more than enough reason to learn Haskell. 

But what I wasn't yet seeing was how to take it to the next level and exploit the type system at the design stage.  Those two blog posts are great examples of how to use the type system at design time.  I coded up a Haskell solution to Morris' exercise, and it was some time well spent.  Example code is below the cut, and I think it's a great little package that shows very directly how Haskell's type system adds value. 

The New Parallel Monad

So there's a new parallel monad recently out from some very major players in the Haskell scene.

Man, is it slick!  Using the factors code from the last post, it was so easy to write a program that parallelized the factorizations of different numbers.  My code took two command line arguments: the first number to factor, and the number of consecutive numbers to factor. The base version of the code was

getFactorStr :: Integer -> String
getFactorStr x = concat $ intersperse "," $
                     map show $ factors x

getFactorStrRange :: Integer -> Integer -> [String]
getFactorStrRange x y = map getFactorStr [x..y]

main = do
   args <- getArgs let start = read $ args !! 0
   let end = (start + (read $ args !! 1))
   mapM putStrLn $ getFactorStrRange start end

The parallel version isn't a lot more complicated:

getFactorStr' :: Integer -> Par String
getFactorStr' x = do
  calc <- spawn $ return $ concat $ intersperse "," $ 
             map show $ factors x
  v <- get calc
  return v 

getFactorStrRange' :: Integer -> Integer -> Par [String]
getFactorStrRange' x y = parMapM getFactorStr' [x..y]

main = do
  args <- getArgs let start = read $ args !! 0
  let end = (start + (read $ args !! 1))
  mapM putStrLn $ runPar $ getFactorStrRange' start end

Now I'm sure it took me longer than it would have taken a more experienced Haskell programmer, but whenever I got into trouble I just had to look at the types of things to find my way out. Like the baseball coach says, you've just got to keep your eye on the type.

And how did the timing work out?  On my quad-core Athlon II machine, the parallel version ran about 3.2x as fast as the sequential version (15.1 seconds vs 48.6 seconds).  This was a crude timing test -- I made no effort to control for what other processes on the system were doing. 

Playing Around with QuickCheck

So I saw the new parallel monad and I wanted to give it a spin.  A simple package that factors numbers seemed to be just the thing. It parallelizes nicely. More about that in the companion post -- this post is about my first steps with QuickCheck  I wanted to test this factor code:

factors :: Integer -> [Integer]
factors x
  | x < 2 = [1] | otherwise = sort $ factors' x 2 [1,x]

factors' :: Integer -> Integer -> [Integer] -> [Integer]
factors' x y zs
  | fromInteger y > (sqrt $ fromInteger x) = zs
  | x `mod` y == 0 && y*y /= x =
                 factors' x (y+1) (y : x `div` y : zs)
  | x `mod` y == 0 && y*y == x =
                 factors' x (y+1) (y : zs)
  | otherwise = factors' x (y+1) zs

The first lesson I learned along the way is that the result of a QuickCheck test is a Property, not a Bool; just a heads-up for other newbies. BTW, one of my favorite things about Real World Haskell is that it gives more than a passing thought to stuff like Cabal and QuickCheck. 

The test machinery was rather more involved than the code itself.  First I had to put together a list of prime numbers, then I could write code that would test factorization over primes and over products of two primes. 

sieve :: Integral a => [a] -> [a]

sieve (p:xs) = p : sieve [x | x <- xs, 0 /= x `mod` p] primes :: Integral a => [a]

primes = sieve [2..]

primesInteger = primes :: [Integer]

getPrime x = primesInteger !! (x `mod` 100)

buildAssocList :: Integral a => [a] -> [a] -> [a]

buildAssocList xs ys = sort $ nub [a*b|a <- xs,b <- ys]

propAssoc x y = x > 0 ==> y > 0 ==>

  factors (x*y) == buildAssocList (factors x)
                                  (factors y)

propPrime x = x > 0 ==>

  let prime = getPrime x in factors prime == [1,prime]

propSimple x y = x > 0 ==> y > 0 ==>

  let primeX = getPrime x

      primeY = getPrime y

  in (factors $ primeX * primeY) ==
          (sort $ nub [1,primeX,primeY,primeX*primeY])

This is all straightforward.  Getting the final piece of test code took rather more time, but it refactored down to

testDepth = 8          -- actually N-1

check :: Integer -> [Integer] -> Integer -> [Integer] -> Bool

check 0 _ _ _ = True

check y xs n ns =

  let p = getPrime (1 + abs(fromIntegral $ head xs))

      ps = factors p

      p_list = build_assoc_list ns ps

  in factors (n*p) == p_list &&
     check (y-1) (tail xs) (n*p) (p_list)

prop_complex z zs = z > 0 &&

     (fromIntegral $ length zs) >=
         (fromIntegral (z `mod` testDepth))   ==>

  check (z `mod` testDepth) zs 1 [1]

This works, though I've got to say that the prop_complex check on the length of zs is not exactly elegant.   I'd love to hear comments on how to make it more idiomatic Haskell (and that applies to all the code).

Real World Haskell on Functors

I've just hit the "Introducing Functors" section.  Though my initial love affair with the book has worn off just a little bit, I'm still liking it a lot.

The following excerpt on Functors is a really nice explanation:

class Functor f where

   fmap :: (a -> b) -> f a -> f b

We can think of fmap as a kind of lifting function, as we introduced in "Avoiding Boilerplate with Lifting" on page 223. It takes a function over ordinary values a -> b, and lifts it to become a function over containers f a -> f b, where f is the container type.

I think that viewing f as a container type is a great introduction to Functors.  I find it more accessible than the other explanation I've seen, which I talk about in this post.  Not that the other way isn't useful in it's own right, but I think I would have picked things up faster if I had seen this explanation first.

Two days into Real World Haskell . . .

and I'm loving it already!

Topics that others explain incompletely, this book covers well the first time.  Example: the indentation rule.  LYAH, much as I love it, lets you know that indentation is important and what common practice is, but leaves you without a firm grasp on all the "what ifs."  Real World Haskell lays it all out there the first time but without taking a lot of space to do it.

Having already worked my way completely through LYAH and "Write Yourself a Scheme", and written a few scripts in Haskell, I was a little tempted to skip or skim through the first few chapters of RWH.  I'm glad I didn't; there's lots of great insights in that material. 

So I've just reached the first chapter where they're really digging in to some "real-world" code: a simple JSON library.  My biggest gripe so far has been that exercises have been a little scarce, and they come at the end of the end of a section, textbook-style.  I prefer exercises integrated into the text:  they strike while the iron is hot.  See this lambda calculus introduction for an example.

On Monad Tutorials

I recently read the opinion that reading monad tutorials prematurely does little good, and is the cause of much frustration*.  I've got to agree with this; I wasted a lot of time trying to understand monad tutorials before I was ready.  There are a bazillion blog posts out there that introduce the reader to monads, all studiously linked from reddit etc.  Some of them are fine and useful if you read them when you are ready. 

When are you ready?  When you

• have worked your way through Learn You a Haskell to the point where you've read its monad chapter
• are looking for another take on monads
• have some time to spend writing some monadic code.  

The previously mentioned "Write Yourself a Scheme" was a great opportunity to learn to write monadic code from a consumers' point of view.  Now I need to find a reason to write my first monad.

*I don't recall where, or I'd link it.   

"Write You a Scheme in 48 Hours"

I just finished Write Yourself a Scheme in 48 Hours.  How was it?

Well, it positions itself as a Haskell tutorial.  In that function, I think it fails miserably.  It uses many language features with no introduction or explanation.  Given how different Haskell is from the dominant programming languages, this works badly as a tutorial.  Other Haskell features are explained in the section after they were first used -- by the time you get to the explanation, you have already hit hoogle or another tutorial to find the explanation for yourself.  In short, it is in no danger of unseating Learn You a Haskell as the Haskell tutorial of choice.

However, when used as a set of exercises after completing LYAH, "Write Yourself a Scheme" does well, very well.  WYAS seems to be a work in progress, and exercises are missing for the latter few chapters.  But I found the first few sets of exercises very instructive. I did find myself referring often to outside resources, but it's clear that the author intends that -- and at this stage of learning, it's a good thing for me. 

Next up: Real World Haskell

Another SICP Post

As I read The Structure and Interpretation of Computer Programs, I've been thinking about the stuff I used to do in my Lisp days, and how it compares with the style of a Haskell program.  Most of the differences, directly or indirectly, seem to boil down to static vs. dynamic typing (even more than strict vs. lazy). For example, Lisp has great metaprogramming facilities (macros, "runtime macros" consisting of eval plus manipulation of parse trees).  Haskell has no features that are really like that kind of macro*, and certainly has nothing like the inherently dynamic eval --- but that doesn't mean that it lacks for features that let you do many of things you would do with macros and eval.

But that doesn't mean that Haskell has a nice way to do absolutely everything that you might choose to do in Lisp.  

A Simple Experiment ...

or not.

One of the things I like to do when I'm getting to learn a new compiler is to take a couple of very simple programs and look at the assembly that the compiler produces.  I tried this with GHC and the following program, add.hs:

add' x y = x + y

main = do
   print $ add' 1 2

The result of  ghc -S add.hs  was 301 lines of assembly code. Adding an explicit type annotation for add' brought it down to 252 lines, and the code was still beyond my meager ability to take in assembly. 

Simple OO Inheritance in Scheme (SICP Redux)

Over on the reddit thread for my last blog post, there were a few requests for a more full-featured object oriented implementation.  I've been looking for a good excuse to brush up on my Lisp, so I've implemented a couple of examples.

There's no Haskell content here, so only follow the cut if you're interested in following up on the last post. 

Reason #23 you should read Abelson & Sussman

I'd forgotten just how great The Structure and Interpretation of Computer Programs is. I'm working my way through my ancient copy of the first edition. As their example of object-oriented programming in Lisp, you might expect that they would use CLOS, or maybe Symbolics Common Lisp with its nifty mixins*. No, they go for the throat:

(define (make-account balance)
  (define (withdraw amount)
     (if (>= balance amount)
         (sequence (set! balance (- balance amount))
                   balance)
          "Insufficient Funds"))
  (define (deposit amount)
     (set! balance (+ balance amount))
     balance)
  (define (dispatch msg)
     (cond ((eq? msg 'withdraw) withdraw)
           ((eq? msg 'deposit) deposit)
           (else (error "Unknown request"
                        msg))))
  dispatch)


==> (define acc (make-account 100))

==> ((acc 'withdraw) 50)
50

==> ((acc 'withdraw) 60)
Insufficient Funds

The beauty of this example is that it is the object-oriented programming model distilled right down to its essence.  It is succint and to the point.  No need to explain about how the compiler is providing syntactic sugar, it's just straight to the bare metal: an object is a collection of functions and data tied together -- a collection of related closures, really. 

Additionally, their discussion of the OO paradigm doesn't start with talk of "objects" and "messages", it starts with a well-grounded discussion of the programming model and its implications for the structure of your code.  I like that, because that's what Object-oreinted programming is.  All that business about objects, messages, and domain models -- that's how we choose to explain object-oriented programming.   

There's other great stuff in the book, of course.  This is just the bit that I'm loving right now. 

For the Lisp-challenged, here's how the code works:  make-account is a function that returns an anonymous function, let's call it mike.  In the code above, mike is given a name by being bound to acc.  The purpose of  mike is to dispatch calls to withdraw or deposit.  When you call mike, you will pass in either 'withdraw or 'deposit.  Based on which of those you pass in, mike will then return one of the mike-local functions  withdraw or deposit.  This returned function takes a number and returns a number, as shown in the last couple of interpreter commands above.  

Coming soon:  a couple of more blogs posts inspired by SICP.  So why aren't you getting inspired?  Read it already. 


*Well, other that they are using Scheme.   

More on Lambda Calculus

It's disappointing how many Lambda Calculus "tutorials" and "introductions" are really bad about actually being tutorials or introductions.  It reminds me of the book for my undergrad class in partial differential equations.  The book was thin, concise, and to the point.  I'm sure it was readily understandable...to the professor who selected it.  To the students, it was completely dense and incomprehensible.  Too many of the Lambda Calculus tutorials are like that.  Specifically, they too often use symbology and terminology without explaining it.  Hint:  if I understood it, I wouldn't be looking for an introduction to the material. 

Happily the first two links from my last article are well done, even if a bit limited in scope.  For a new student, I would recommend starting with them and then following up with this paper.  It is clearly the most newbie-friendly of any material I have found that treats the subject with any depth (though even that paper is not perfect in this regard).  For the new student, my recommendation would be to read these three pieces, in the order in which they are linked here.

Cliff's Notes squared: Lambda Calculus

I say Cliff's Notes squared, because this is the Cliff's Notes guide to the Cliff's Notes.  

Up til now, I've mostly shied away from anything that had any significant lambda calculus content -- and when I didn't shy away from it, got nothing out of it.  I read one or two "intro" pieces, but they didn't really click for me.  Happily, I've recently found some stuff that works for me.  For a gentle introduction, I can recommend the following. 

This introduction to the lambda calculus is short and sweet.  It doesn't cover a lot of ground but covers it well, and the exercises really work to give you some insight into the fundamentals.  

Another good short intro is here.  It does a great job of explaining why things are done the way they are, including strategies for manipulating lambda expressions.   The exercises are fewer and I found them to less well integrated into the text. I think it's a great companion to the first article -- it provides a bit more explanation where the first article relies a bit more on the reader's intuition.  Given that, if you find yourself stumped by a section in the first article, look here for illumination. 

These class notes are a good follow up to those two articles.  I read them straight through up to page 13, when the S-combinator threw me for a bit of a loop.  I wanted to understand it a bit better before before moving on, so I stopped there and did a bit of further research before continuing.  This was a good thing, as the class notes have introduced Combinatory Logic without letting you know that they have veered from strict Lambda Calculus.

Let me talk about a newbie's view of the formulae in Lambda Calculus and in Combinatory Logic.  The S combinator is defined as S x y z = x z (y z).  This may be a bit confusing at first, it certainly was for me.  Even though I'm pretty handy with higher order functions in practice, and function composition seems as natural as can be, I still get thrown for a loop when I see an equation like this that doesn't make sense unless it's arguments are themselves functions (see the entries on "The Type of []" and "map map and Type-Wrangling"  for similar issues).  Useful exercise: with the definitions on pages 12 and 14 of the class notes, derive the equivalencies for fst and snd on the bottom of page 14. 
 
Maybe soon I can read Edward Yang's blog and get something out of it.