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.