Category Archives: Haskell

http://www.haskell.org/

BuilderBuilder: The Model in Haskell

This post describes the first model in Haskell for the BuilderBuilder task. We will develop the model incrementally until we have rough parity with the Java version.

I’m experimenting with ways to distinguish user input from system output in transcripts of interactive sessions. This time I’m trying color, using a medium blue for output. I will appreciate feedback on whether that works for you.

Step one: defining and using a type

The simplest possible Haskell version of our model for a Java field is:

data JField = JField String String

However, the PMNOPML (“Pay Me Now Or Pay Me Later”) principle says that we’ll regret it if we stop there. In fact, later comes quickly.

We can create an instance of JField in a source file:

field1 = JField "name1" "Type1"

To do the same in a ghci session, prefix each definition with let, as in:

*Main> let field1 = JField "name1" "Type1"

Step two: showing the data

Trying to look at the instance yields a fairly opaque error message.

*Main> field1

<interactive>:1:0:
    No instance for (Show JField)
      arising from a use of `print' at <interactive>:1:0-5
    Possible fix: add an instance declaration for (Show JField)
    In a stmt of a 'do' expression: print it

Remember that in Java the default definition of toString() returns something like com.localhost.builderbuilder.JFieldDTO@53f67e; that’s also obscure at first glance. Haskell just goes a bit further, complaining that we haven’t defined how to show a JField instance. We can ask for a default implementation by adding deriving Show to a data type definition:

data JField = JField String String deriving Show

After loading that change, we get back a string that resembles the field’s defining expression:

*Main> field1
JField "name1" "Type1"

Step three: referential transparency

Our first model represented a Java class by its package, class name, and enclosed fields. The Haskell equivalent is:

data JClass = JClass String String [JField] deriving Show

The square brackets mean “list of …”, so a JClass takes two strings and a list of JField values. I’ll say more about lists in a moment, but first let’s deal with referential transparency.

We can build a class incrementally:

field1 = JField "name1" "Type1"
field2 = JField "name2" "Type2"
class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

or all at once:

class1 = JClass "com.sample.foo"
                "TestClass"
                [   JField "name1" "Type1" ,
                    JField "name2" "Type2"
                ]

and get the same result:

*Main> class1
JClass "com.sample.foo" "TestClass" [JField "name1" "Type1",JField "name2" "Type2"]

As mentioned previously, only one of those definitions of class1 can go in our program. To Haskell, name = expression is a permanent commitment. From that point forward, we can use name and expression interchangeably, because they are expected to mean the same thing. That expectation would break if we were allowed to give name another meaning later (in the same scope).

Consequently, we can define a class using previously defined fields, or we can just write everything in one definition, nesting the literal fields inside the class definition. As we’ll see later, this also has implications for how we write functions; a “pure” function and its definition are also interchangeable.

Step four: lists

The array is the most fundamental multiple-valued data structure in Java; the list plays a corresponding role in Haskell. In fact, lists are so important that there are a few syntactical short-cuts for dealing with lists.

  • Type notation: If t is any Haskell type, then [t] represents a list of values of that type.
  • Empty lists: Square brackets with no content, written as [], indicate a list of length zero.
  • Literal lists: Square brackets, enclosing a comma-separated sequence of values of the same type, represent a literal list.
  • Constructing lists: The : operator constructs a new list from its left argument (a single value) and right argument (a list of the same type).

For example, ["my","dog","has","fleas"] is a literal value that has type [String] and contains four strings. "my":["dog","has","fleas"] and "my":"dog":"has":"fleas":[] are equivalent expressions that compute the list instead of stating it as a literal value.

By representing the fields in a class with a list, we achieve two benefits:

  • The number of fields can vary from class to class.
  • The order of the fields is significant.

Step five: types and records

Given a JField, how do we get its name? Or its type? We can define functions:

fieldName (JField n _) = n
fieldType (JField _ t) = t

and do the same for the JClass data:

package   (JClass p _ _ ) = p
className (JClass _ n _ ) = n
fields    (JClass _ _ fs) = fs

but all that typing seems tiresome.

Before solving that problem, let’s note two other limitations of our current implementation:

  • Definitions using multiple String values leave us with the burden of remembering the meaning of each strings.
  • The derived show method leaves us with a similar problem; it doesn’t help distinguish values of the same type.

If you suspect that I’m going to pull another rabbit out of Haskell’s hat, you’re right. In fact, two rabbits.

Type declarations

We can make our code more readable by defining synonyms that help us remember why we’re using a particular type. By adding these definitions:

type Name     = String
type JavaType = String
type Package  = String

we can rewrite our data definitions to be more informative:

data JField = JField Name JavaType deriving Show
data JClass = JClass Package Name [JField] deriving Show

Record syntax

The second rabbit is a technique to get Haskell to do even more work for us. We represent each component of a data type as a name with an explicit type—all in curly braces, separated by commas:

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

When we use this syntax, Haskell creates the accessor functions automagically, and enables a more explicit and flexible notation to create values. All of these definitions:

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

produce equivalent results:

*Main> field1
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1a
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1b
JField {fieldName = "name1", fieldType = "Type1"}

Step last: that’s it!

We have covered quite a bit of ground! The complete source code for the model appears at the end of this post. With both Java and Haskell behind us, we have most of the basic ideas we’ll need for the Erlang and Scala versions.


Recommended reading:

Real World Haskell, which is also available
for the Amazon Kindle
or on-line at the book’s web site. I really can’t say enough good things about this book.


The current BuilderBuilder mode in Haskell, along with sample data, is this:

-- BuilderBuilder.hs

-- data declarations

type Name     = String
type JavaType = String
type Package  = String

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

-- sample data for demonstration and testing

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

field2 = JField "name2" "Type2"

class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

studentDto = JClass {
    package   = "edu.bogusu.registration" ,
    className = "StudentDTO" ,
    fields    = [
        JField {
            fieldName = "id" ,
            fieldType = "String"
        },
        JField {
            fieldName = "firstName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "lastName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "hoursEarned" ,
            fieldType = "int"
        },
        JField {
            fieldName = "gpa" ,
            fieldType = "float"
        }
    ]
}

Updated 2009-05-09 to correct formatting and add category.

Advertisements

BuilderBuilder: Haskell Preliminaries

The next step in the BuilderBuilder project is to develop a model in Haskell that is analogous to the Java model in the previous post. This post will introduce just enough Haskell to get started; the next post will get into the BuilderBuilder model.

Environment:

I’m using GHC 6.10.1, obtained from the Haskell web site. There are a variety of platform-specific binaries; I used the classic configure/make/install process on OSX. (For Java programmers, make is what we used instead of ant back in the Jurassic era.) Consult the Haskell Implementations page for details on obtaining Haskell for your preferred platform.

The complete development environment consists of two windows: one running a text editor, and the other running ghci, the interactive Haskell shell that comes with GHC.

Haskell introduction:

Use your text editor to create a file named bb1.hs with this content:

-- bb1.hs

-- simplest possible data declarations

data JField = JField String String

-- sample data for demonstration and testing

field1 = JField "id" "String"

-- sample function

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Then run ghci as follows, where user input is underlined:

your-prompt-here$ ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> helloField field1
"Hello, id, of type String"
*Main> 

We started ghci, told it to load our source file (the :l … line), and then invoked the helloField function on the sample field. Now let’s examine the Haskell features used in that code. The lines beginning with double-hyphens are comments, and will be ignored in the description.

Defining data types

Because Haskell emphasizes functions, it’s no surprise that the syntax for defining data types is very lightweight. The Java BuilderBuilder model represents a field with two strings, one for the name and one for the type. The simplest possible Haskell equivalent is:

data JField = JField String String

This defines a data type named JField. It has a constructor (also named JField) that takes two strings, distinguished only by the order in which they are written.

Defining values

The next line of code defines an instance of this type:

field1 = JField "id" "String"

The equal sign means “is defined as“. That statement defines field1 as the instance of JField constructed on the right-hand side. It is not declaring and initializing a mutable variable. Within the current scope, attempting to redefine field1 will produce an error. (More about scope later.)

Defining functions

Finally, we have a simple function that converts a JField to a String.

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Everything in Haskell has a type, including functions. The double colon means “is of type“, so the type of helloField is function from JField to String.

The value of applying helloField to a JField containing strings n and t is defined by the expression on the right-hand side. Haskell regards strings as lists of characters; the ++ operator concatenates lists of any type. The names n and t are only meaningful within that definition, similar to the local variables in this Java fragment:

public static String helloField(IJField f) {
    String n = f.getName();
    String t = f.getType();
    return "Hello, " + n + ", of type" + t;
}

Type inference

Java requires that we explicitly declare the local variables as type String. But in Haskell, because JField is specified to have two String values, the compiler can infer the types of n and t In fact, the entire first line of helloField is not necessary. The defining equation in the second line explicitly uses a JField on the left and constructs a String on the right. Therefore, the compiler can infer JField -> String as the type of the function. Haskell’s type inference allows us to write very compact code without giving up strong, static typing.

To see that in action, add the following line to the end of your bb1.hs file:

hiField (JField n _) = "Hi, " ++ n

(The underscore is a wild card, showing the presence of a second value but indicating that we don’t need it in this function.)

Reloading bb1.hs in ghci allows us to see type inference at work.

*Main> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> hiField field1
"Hi, id"
*Main> :type hiField
hiField :: JField -> [Char]

As we’ll see later in this series, Scala brings type inference to the JVM environment. Coming from the dynamic language side, the Diamondback Ruby research project is adding type inference to Ruby. So perhaps type inference is (finally) an idea whose time has come.

We’ll pick up more Haskell details along the way, but we have enough to start defining our first BuilderBuilder model. That will be the subject of the next post.


Updated 2009-05-09 to fix formatting.

Why functional programming?

The canonical answer to that question is probably “Why functional programming matters“, but here’s a specific example that makes the case nicely.

Neil Mitchell is working on Supero, an optimizing compiler for Haskell which includes some ideas from supercompilation. But that’s not important right now.

What is important is the technique Mitchell uses in the blog post at the second link above. Algebra. As in junior-high-Algebra-I-algebra. The old “if a = b then you can substitute either one for the other” kind of Algebra.

Functional programming is based on defining functions.

  def square(i: Int) = i * i

In pure functional programming, where side-effects are not allowed (or at least kept securely behind bars), you can treat that definition as an equation; wherever you see square(foo) you can rewrite it as (foo * foo) and vice versa. This applies even when foo is an arbitrarily complex expression (don’t worry about operator precedence or extra parentheses right now; that’s not the point).

The point is that you can’t do that with confidence for impure (i.e., having side-effects) languages. Consider trying that replacement in something as simple as…

  n = square(++i);

…which clearly is not the same as…

  n = ++i * ++i;

…at least in most cases. Are there any special cases where it’s the same? Would the answer be different if the enclosed expression had been i++ instead?

If you even had to think about it for one millisecond (or, like me, thought “That’s ugly! I’ll think about it later!”) that’s exactly the point. In a pure language the question can’t even come up. You’re free to do the rewriting, either way, any time.

(Fair warning: You don’t need to know Haskell to read Mitchell’s post, but it helps. Even if you don’t, it’s worth the little bit of time it takes to work through his example. The cheat sheet at the bottom of this post is a quick introduction for non-Haskell-speaking readers, or non-Haskell-reading speakers.)

Mitchell takes a simple task, breaking a string into a list of words, and shows a simple and obvious function for the task. However, that simple and obvious function ends up with redundant “is it a space?” tests against some characters. Mitchell does a bit of refactoring, using simple substitute-equals-for-equals steps, to track down and eliminate the redundance, resulting in an equivalent (still simple) function that runs faster.

All of this is based on the facts that:

  • more powerful functions can be composed out of simpler ones, and
  • pure functions ensure that the obvious substitutions work.

For me this makes a powerful demonstration of the benefits of the functional approach, whether I’m using Haskell, Scala, or even a non-FP language such as Java. (Not only does functional programming matter, knowing why functional programming matters matters as well.)


Cheat sheet

For newcomers to Haskell notation, here’s a bit of explanation. Please don’t hold the length (or any shortcomings) of my explanation against Haskell. I’m assuming a reader who’s never seen Haskell before (or any similar language), and so say something about almost every token. Feel free to skip the obvious, with my apologies.

Mitchell’s analysis works on this original function…

  words :: String -> [String]
  words string = case dropWhile isSpace string of
                     [] -> []
                     s -> word : words rest
                         where (word, rest) = break isSpace s

…which breaks a string into a list of words (strings).

The special-character soup isn’t really that bad, if you use your Captain Zowie decoder ring. It helps to know three facts:

  • indentation shows nested structure, instead of using curly braces,
  • function application doesn’t require parentheses, and
  • a Haskell String can be considered as a list of characters.

The first line…

  words :: String -> [String]

…declares the type of words as function from string to list of strings. Specifically:

  • the double-colon can be read “has type”,
  • the arrow indicates a function taking the type on the left, yielding the type on the right, and
  • the square brackets on the right read “list of”.

The second line…

  words string = case dropWhile isSpace string of

…starts the definition of words, using a parameter named string (which we already know is of type String from the first line). The phrase…

  dropWhile isSpace string

…returns a left-trimmed version of string. It applies isSpace to successive elements of string, repeating as long as the result is true, and returns what’s left (either because there’s nothing left or because a character is found for which isSpace is false). It does so without modifying the original string, just as String#substring does in Java. That left-trimmed (sub-)string is then subjected to a case analysis, by way of pattern matching.

Remember that the result of left-trimming was produced either because there were no characters left, or because a non-space character was found. Therefore, there will be two cases to consider. The line reading…

  [] -> []

… reads “if you have an empty list (of characters) then return an empty list (of Strings)”. We (and the Haskell compiler!) can infer the parenthesized types because we know that trimming a string produces the String (list of characters) being inspected, and the type declaration on the first line says that the function produces a list of String.

The last two lines address the case in which there actually were some characters left after trimming.

  s -> word : words rest
      where (word, rest) = break isSpace s

For a non-empty string s… Wait! What’s s and how do we know it’s a non-empty string? Remember that we’re in a case (glance back at the original above to see the indentation) and we’ve already eliminated the possibility that the trimmed string we’re examining is empty. So the value in hand must be non-empty. And pattern matching give us the ability to name things on-the-fly, more or less the equivalent of defining a local variable in e.g. Java. So, as I was saying before I so rudely interrupted myself…

For a non-empty string s, the result is a word followed by the words from the rest of the string, where those two things (word and rest) are constructed by breaking s at the first space (the first character for which the function isSpace returns true). The single-colon is often read as “cons”, in homage to Lisp. It constructs a list (of some type) by gluing a value (of the correct type) onto the beginning of a list (of the same type). Becuase word is a String and words rest is a list of String, the entire expression word : words rest is also a list of String.

Notice that both dropWhile and break have two arguments: another function (isSpace in both uses here) and a list. This works because dropWhile and break are higher-order functions, which take functions as arguments and use them whenever needed. If you cross your eyes and squint a little, this begins to look like design patterns in OO.


XMonad Videos

There’s a very nice talk which seems tailor-made for anyone who has seen Simon Peyton-Jones’ two-part talk on Haskell and XMonad (with slides avaliable) and wanted more, especially of the “how did they do it?” variety.

XMonad is now at 0.6.