A bit of Haskell

I’ve just started dabbling in Haskell, a pure functional language with some compelling features.

As a first exercise in this language, I eschewed the canonical greeting to the cosmos and decided to translate my algorithm for computing the likelihood of a bitmask yielding non-zero that I wrote originally in Ruby.  Here’s what it looks like in Haskell:

import Data.Bits

pmask :: Integer -> Double
pmask mask = pnonzero (bitcount mask)

pnonzero :: Integer -> Double
pnonzero onbits = 1.0 - (pzero onbits)

pzero :: Integer -> Double
pzero onbits = 1.0 / (2 ^ onbits)

bitcount :: Integer -> Integer
bitcount 0 = 0
bitcount n
  | n > 0 = 1 + (bitcount (n .&. (n - 1)))
  | otherwise = error "cannot use negative numbers"

Bit operations are not automatically included as they are in Ruby, hence the “import” statement.  A bit-and operator is thereby defined as “.&.”.  This also imports a “shift” function, but trying to use it here created enough type confusion to thwart my Haskell-novitiate brain.  Hence, I resorted to applying an exponent to 2 instead.

Speaking of types, Haskell can do type inference, but in the example above I found it necessary to specify type signatures to avoid compilation errors.  I like the fact that you can enforce type safety if you want to, but I wish the type inference was a bit smarter (or, alternatively, that I was a bit smarter to understand how it wants to work).  Type signatures are the lines containing a double-colon.  For example, the line pmask :: Integer –> Double means that pmask is the name of a function that takes an Integer argument and returns a Double.  The line following defines that function (in this case — you can place the definition anywhere).  Thus, the pmask function takes an argument named mask and returns the result of calling pnonzero with a single argument (in parentheses) which is the result of calling bitcount with mask as its argument.

I find the use of parentheses interesting.  Function arguments do not need parentheses, but you use parentheses to group a function and its arguments when they compose an argument to another function.  It makes perfectly economical sense – in practice it looks like a cross between the C (et al.) and Lisp usages.

Where Haskell starts getting interesting can be seen at the end of this example.  You’ll notice that we have two distinct definitions of the function bitcount, plus a branch in the second definition.  The former distinction is called “pattern matching”, where which function definition to use is determined by the argument passed.  The latter uses “guards” to perform boolean tests to choose the function definition.  Thus, when the argument to bitcount is 0, 0 will be returned.  When it is any other value, the second form is used.  Within that, if the argument is greater than 0, we use the recursive function definition.  Otherwise (which is a function that always returns true), we throw an error.

Whereas Ruby uses a relaxed form of the C-style semi-colons and braces to delineate statements, and Python uses significant whitespace, Haskell allows both.  But, it’s considered better form to use the significant whitespace, which is called “layout rule”.  I’m not a big fan of using indentation for anything more than readability, but so far it does not seem onerous in Haskell.

Where Haskell truly shines is in its approach to lazy evaluation, which is more radical than any I have used.  This allows things like infinite lists – for instance, [0 ..] is a list of all non-negative integers.  Naturally, evaluating that would never return, but Haskell doesn’t need to.  You can even map a function to the list, which results in another lazy infinite list, without evaluating all the members.  This eliminates the need for continuations, and makes memoization a breeze.  Consider the canonical Fibonacci function:

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

The computational complexity for any one value is roughly O(nⁿ), which means that when you ask for anything higher than about 40, you’ve got quite a wait.  We can reduce that to O(n) by memoizing previously computed results:

fibonacci =
  let fib 0 = 0
      fib 1 = 1
      fib n = fibonacci (n-2) + fibonacci (n-1)
  in  (map fib [0 ..] !!)

How elegant is that?