Haskell's Function Application Operator ($)

Sometimes, Haskell’s syntax is so alien to read (to my eyes at least anyway). I’ve seen wide-spread use of the $ operator all over lots of people’s code and never really had a grasp on what it is/does. In the end, it’s really quite simple. The whitespace character has a very high precedence order, so when you’re using spaces the precedence order looks like this.

f a b c = ((f a) b) c

This is classified as being left-associative. In contrast, using the $ operator allows us to be right-associative. An example.

f $ a $ b $ c = f (a (b c))

Looking at this, it’s starting to look very much how our programming languages are structured with function calls. We’re very right-associative. Because Haskell uses the white space character to denote left-associations, it takes a lot of parenthesis to make a complex state right-associative as you need to change the precedence order by hand. This is the true power of the $ function. We can use $ to free us from parenthesising everything, so that a transformation as below occurs.

putStrLn (show num)
putStrLn $ show num

This simple scenario doesn’t illustrate exactly how much $ will help us out. Here’s another slightly more complex scenario. It becomes clear here that $ is working to make our code more readable.

sum (take 10 (cycle [1,2,3]))
sum $ take 10 $ cycle [1,2,3]

In character-space length they’re equivalent, but the second version looks less LISP-y. I guess this is what was being aimed at.

Anyway, until next time.

Unit Testing with QuickCheck

Introduction

Seems I’m forever making card games in Haskell, so it only seemed right that I try and make a library of routines and data types that will get me going quicker. Don’t get me wrong, I intend on doing something serious with Haskell one day - I just seriously lack the chops to do so right now.

As with any development process, you as a developer should write unit tests. Not only is it good practice but it also gives you a repeatable base of executions to assure you that the last change you put in won’t break your masterpiece. Today I want to talk about the QuickCheck unit testing library for Haskell.

What are we testing?

To give you an idea of the playing field we’re on, I’ll just post some of the simple routines that I have done so far. First up is the data types that will help us represent a single playing card.

-- | Card values for a standard deck             
data CardValue = Ace | Two | Three | Four | Five 
   | Six | Seven | Eight | Nine | Ten            
   | Jack | Queen | King                         
   deriving (Show, Eq, Enum)                     
                                                 
-- | Possible card suits                         
data CardSuit = Heart | Diamond | Club | Spade   
   deriving (Show, Eq, Enum)                     
                                                 
-- | A card                                      
data Card = Card CardValue CardSuit              
   deriving (Show, Eq)                           

A card has a suit and a value. Pretty straight forward. I could have made a type that wrapped an array of the Card type and called it Deck, but I’m happy just handling an array of Card. Now to build a deck and to shuffle it!

-- | Seeds a list of cards with a random value                    
seedCards :: StdGen -> [Card] -> [(Card, Int)]                    
seedCards g []     = []                                           
seedCards g (c:cs) = x:seedCards ng cs                            
   where (seed, ng) = randomR(1, 10000) g :: (Int, StdGen)        
         x          = (c, seed)                                   
                                                                  
-- | Makes an ordered deck of cards                               
makeDeck :: [Card]                                                
makeDeck = [Card v s | v <- [Ace .. King], s <- [Heart .. Spade]] 
                                                                  
-- | Makes a randomly shuffled deck of cards                      
makeShuffledDeck :: StdGen -> [Card]                              
makeShuffledDeck g = [x | c <- sorted, let x = fst c]             
   where cards  = seedCards g makeDeck                            
         sorted = sortBy (compare `on` snd) cards                 

When a deck is built with makeDeck the cards are ordered just like they are when you open a fresh deck of cards, so we need to shuffle them in order to make this game any fun! seedCards assigns a random value to each card that it is passed and then makeShuffledDeck saves the day by ordering by this random seed to give a shuffled deck.

That’s all pretty simple still and that’s where the “testable” parts stop. So, still the question: what are we testing? Well, I’m sure there are plenty of other scenarios, but for today’s purposes we’ll test the following:

• Are there 52 cards in a deck made by makeDeck?
• Are there still 52 cards in a deck after they’ve been processed by makeShuffledDeck?
• Is the deck made by makeDeck not in the same order as the deck made by makeShuffledDeck?

Great. With these three scenarios in mind, here’s how easy it is to assert these facts using QuickCheck.

runTests = do                                                      
   quickCheck ((length (makeDeck)) == 52)                          
   quickCheck (\n -> length (makeShuffledDeck (mkStdGen n)) == 52) 
   quickCheck (\n -> makeShuffledDeck (mkStdGen n) /= makeDeck)    
                                                                   
main :: IO ()                                                      
main = runTests                                                    

As it should be, these tests read rather humanly. And after running this suite of tests we end up with the following results:

+++ OK, passed 1 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.

Hold on! 100 tests? We only defined 3 tests though. How can this be? You’ll see that for the second and third tests actually have an anonymous function passed to them. Because both of these depend on a random number generator (to shuffle the deck), I’ve passed in mkStdGen’s integer that it maps to a generator from the function’s parameter list. QuickCheck grabbed hold of this and rather than just running 1 test, it went ahead and gave the anonymous function 100 random values. That’s much better coverage for what is seemingly the cost of defining the test as an anonymous method. Immediately you can see the power of unit testing with such a simple framework and how you can be productive relatively quickly.

Blurring the lines between Haskell and C

Introduction

Being able to use parts of code that you have written in different languages in your environment of choice is a great productivity booster. For those particular problems you can really pick the tool that you need. Haskell and C are no exception to this. The Haskell website has a great little write-up on the topic. In today’s post, I’m going to run you through the steps that I followed to get this running.

Write your Haskell

The compilation process depends on your Haskell code being written first as GHC will generate some stub code for you. Here’s a very simple and crude prime number tester:

{- LANGUAGE ForeignFunctionInterface #-}                      
module Prime where                                            
                                                              
import Foreign.C.Types                                        

-- | Take a boolean and convert it to an integer
bool_to_int :: Bool -> Int                                    
bool_to_int False = 0                                         
bool_to_int True = 1                                          

-- | Brute force division style prime number testing
is_prime :: Int -> Int                                        
is_prime x = bool_to_int ptest                                
   where divisible = [n | n <- [3,5..(x-1)], x `mod` n == 0]  
         ptest     = length (divisible) == 0                  

-- | Interface exposed into C land
is_prime_hs :: CInt -> CInt                                   
is_prime_hs = fromIntegral . is_prime . fromIntegral          
                                                              
-- | Export symbols into C land                                                                                                                            
foreign export ccall is_prime_hs :: CInt -> CInt              

Ignoring my method of primes testing, you can see some interesting pieces in this Haskell source. On the first line we’re enabling a GHC extension for the ForeignFucntionInterface. This allows us to export symbols to other languages. We have our implementation actually in the function is_prime with is_prime_hs being the callable wrapper from outside, in this case C. The last line actually exports our wrapper as a callable function.

Haskell compilation

You’ve got your Haskell module ready for compilation, but it’s going to be a little bit different. This source is supporting another application rather than containing a main function of its own.

$ ghc -c -O prime.hs

This command will compile our file only -c and optimise -O. A stub header file is generated for us (thanks to our FFI instructions on the first line of our Haskell file) that we can include in our main program.

Write your C

It’s now time to call our prime function. There is a little bit of administration fluff that we have to go through in order to get there, but it’s really not much to worry about. Take note that we’re including our stub header file that was generated for us in our Haskell compilation step.

#include <HsFFI.h>                    
#ifdef __GLASGOW_HASKELL__            
#include "Prime_stub.h"               
extern void __stginit_Prime(void);    
#endif                                
                                      
#include <stdio.h>                    
                                      
int main(int argc, char *argv[]) {    
   int i;                             
   
   /* FFI initialization */
   hs_init(&argc, &argv);  

#ifdef __GLASGOW_HASKELL__            
   hs_add_root(__stginit_Prime);      
#endif                                

   /* determine if 13 is prime */
   i = is_prime_hs(13);               
   printf("is 13 prime? %d\n", i);    
  
   /* determine if 21 is prime */
   i = is_prime_hs(21);               
   printf("is 21 prime? %d\n", i);    
                                 
   /* teardown FFI */

   hs_exit();                         
   return 0;                          
}                                     

So that’s pretty straight-forward C code in the end. It’s a little awkward at first to look at the #define rigmarole at the top of the file, but you’ll soon see straight past it. You can see at the top of the file that we’ve got an external symbol representing the module, Primes. This is used as a secondary initialisation step after we start up FFI (with hs_init). The call to hs_add_root is the extra initialisation required (per module we import - I’m led to believe) that we do for GHC’s sake. Your C code is written, it’s now time to compile, link and execute! Compilation to produce an executable looks like this.

$ ghc --make -no-hs-main -optc-O call_prime.c Prime -o test

We’re telling ghc that we want to make --make our executable -o test that doesn’t have a main routine in haskell source -no-hs-main and optimised by the c compiler -optc-O. We should have an executable, ready to go:

$ ./test
is 13 prime? 1
is 21 prime? 0

It’s not fireworks, but it’s functional.

Bridging Science and Art with Ruby

Introduction

Having a love for music and technology at the same time can be a dangerous business. You can really fool yourself into thinking that you can boil art down into algebraic or procedural recipes that you can just turn the handle on. The frustration sets in when it’s just not that black-and-white. In this post, I’ve put some Ruby code together that takes in an array of musical intervals and attempts to give that array of intervals a name.

In music, this is better known as a chord or arpeggio.

Assumptions

As above, I want an array of intervals in so this is going to take shape in the form of an integer array. These integers will be the individual distances (in semi-tones) from the root which will start at 0. For reference, here’s a chart that I used during development.

</div><div>
Intervals that are emphasised, didn’t really factor into the overall solution as they add nothing to the chord’s quality or extension. Well, this may not be entirely true, some jazz-heads have probably already got their cross-hairs locked onto me, ready to flame away.

Gathering facts

First of all, we need the array of intervals into our class. We’ll always assume that there is a root and if there isn’t one, we’ll pop one into the array for good measure.

class Chord

   def initialize(intervals)
      if not intervals.include?(0)
         intervals = [0] + intervals
      end

      @intervals = intervals
   end
   
end

We’re now managing an array of intervals. What we need to do is ask questions of that array so we can gather information about our chord. The following methods ask the important questions in the first octave.

def minor?
   @intervals.include?(3)
end

def major?
   @intervals.include?(4)
end

def has_fourth?
   @intervals.include?(5)
end

def has_tritone?
   @intervals.include?(6)
end

def has_augmented_fifth?
   @intervals.include?(8)
end

def has_sixth?
   @intervals.include?(9)
end

def dominant?
   @intervals.include?(10)
end

def has_major_seven?
   @intervals.include?(11)
end

With just this base information we can find a lot out about the chord, but it’s not nearly enough. We need to be sure. The best part about putting these basic building blocks in place is that our methods are going to read a little more human from now on. Here are some more fact finders.

def diminished?
   self.minor? and self.has_tritone?
end

def augmented?
   self.major? and self.has_augmented_fifth?
end

def has_third?
   self.minor? or self.major?
end

def suspended?
   not self.has_third? and (self.has_second? or self.has_fourth?)
end

def has_seventh?
   self.dominant? or self.has_major_seven?
end

Finally we have a couple more tests that we need to conduct on the array in the upper octave, otherwise none of the jazz-guys are going to get their chords! These again will form syntactic sugar for the main feature, to_s.

def has_minor_ninth?
   @intervals.include?(13)
end

def has_ninth?
   @intervals.include?(14)
end

def has_augmented_ninth?
   @intervals.include?(15)
end

def has_eleventh?
   @intervals.include?(17)
end

def has_sharp_eleventh?
   @intervals.include?(18)
end

def has_minor_thirteenth?
   @intervals.include?(20)
end

def has_thirteenth?
   @intervals.include?(21)
end

Piecing it together

It’s good that we know so much about our chord. It means that we can ask questions and make decisions based on the outcomes of these questions. Upon reflection, I did have another idea on assembling those fact-finding methods into a more flexible but highly-unhuman set of methods that when you asked about a particular interval, you’d get back either :flat, :natural or :sharp. Perhaps I’ll try it in another revision; I digress. All the facts are in front of us, let’s construct a string from these facts. Now here’s where the awkward bridge between science and art starts to burn a little, then a lot. Questions must not only be asked of the array, but they have to be asked in the right order otherwise you’ll get a different result.</div><div>
</div><div>That’s naming for you though. It doesn’t read pretty, but here it is.

def to_s

   quality = "Major " if self.major?
   quality = "Minor " if self.minor?
   quality = "Augmented " if self.augmented? and not self.has_seventh?
   quality = "Diminished " if self.diminished? and not self.has_seventh?

   extensions = ""

   if not self.suspended?

      if (self.major? and self.has_major_seven?) or
         (self.minor? and self.dominant?)
         extensions = "Seventh "
      else
         if self.dominant?
            quality = "Seventh "
         end
      end

   else
      quality = "Suspended "
      extensions = "Second " if self.has_second?
      extensions = "Fourth " if self.has_fourth?
   end

   if self.has_sixth?
      if self.has_tritone?
         quality = "Diminished "
         extensions = "Seventh "
      else
         extensions += "Sixth "
      end
   end

   if not self.diminished? or self.has_seventh?
      extensions += "Flat Five " if self.has_tritone?
   end

   if not self.augmented? or self.has_seventh?
      extensions += "Sharp Five " if self.has_augmented_fifth?
   end

   if self.has_seventh?
      extensions += "Flat Nine " if self.has_minor_ninth?

      if self.has_ninth?
         if self.dominant?
            quality = ""
            extensions = "Ninth "
         else
            extensions += "Nine"
         end
      end

      if self.has_eleventh?
         if self.dominant?
            quality = ""
            extensions = "Eleventh "
         else
            extensions += "Eleven"
         end
      end

      if self.has_thirteenth?
         if self.dominant?
            quality = ""
            extensions = "Thirteenth "
         else
            extensions += "Thirteen"
         end
      end

      extensions += "Sharp Nine " if self.has_augmented_ninth?
      extensions += "Sharp Eleven " if self.has_sharp_eleventh?
   end

   extensions = extensions.strip()
   chord_name = quality.strip()
   chord_name += " " if chord_name.length > 0 and extensions.length > 0
   chord_name += extensions if extensions.length > 0

   chord_name
end

Woosh. That was a lot of if-treeing. There has to be a better way of doing this, but by my calculations using this code I’ve covered the following use-cases off:

• Major
• Minor
• Diminished
• Diminished Seventh
• Augmented
• Seventh
• Minor Seventh
• Major Seventh
• Suspended Second
• Suspended Fourth
• Seventh Flat 5
• Seventh Sharp 5
• Major Seventh Flat 5
• Major Seventh Sharp 5
• Minor Seventh Flat 5
• Minor Seventh Sharp 5
• Ninth
• Eleventh
• Thirteenth

There’s a few chords there, but there are just so many more and this code may work for them. Those other cases just haven’t made it into my unit tests yet.

Plans

I really want to make this part of a bigger application that I’m writing at the moment. I was motivated to write a unit like this because I didn’t want chord definitions just sitting in a database, I wanted the application to do the think work. Possibilities from here also reach into inversions and slash chords. It would be easy to permute the list of intervals and enumerate all of the inversion scenarios.

Anyway, until next time!

Clojure and Leiningen quickstart

Introduction

Clojure is the modern LISP. Clojure is an elegant, dynamic programming language that runs a-top the JVM. In today’s post, I’ll show you how to get started with Clojure & Leiningen.

Getting installed

I’ve written this article from the perspective of a Debian user. Translating these steps into your own native environments should be as easy as re-structuring the installation steps to target your package manager of choice. Installing Clojure & Leiningen was a simple as this:

$ sudo apt-get install clojure leiningen

You’re done. You should now have Clojure and Leiningen at your disposal.

Initial steps

You’ll want to kick the tires on this puppy, so from your bash prompt fire up the REPL environment and try a few commands:

$ clojure
Clojure 1.2.1
user=> (+ 2 4)
6
user=> (print "Clojure is installed!")
Clojure is installed!nil
user=> (if (= 1 1) (print "Yes, 1 does equal 1") (print "Mathematics just stopped working"))
Yes, 1 does equal 1nil

Alright! Enough of this already. Let’s generate a project. Leiningen is a painless way to get started on your Clojure project. All you have to do, is issue the following commands and you’ve got a project ready to go:

$ lein new projname

Where projname is the name of your project. For this test, I just called mine “myproj”. If you have a look inside the directory that Leiningen has just generated for you, you’ll see the following sub-directories:

lib         - holds your programs dependencies
project.clj - a clojure file describing your project 
README      - duh! 
src         - your source files 
test        - any tests for your application

This is a pretty neat-and-tidy layout, ready for you to start coding.

Bulding and running and cleaning, oh my!

Leiningen also makes it very easy to build, run and cleanup your project. Here’s how. From within your project directory:

# Build your project
$ lein compile

# Clean any built files
$ lein clean

# Run your project
$ lein run

Too easy.