• previous -- Monads (advanced)
• table of contents
• next -- Example - Euclid's algorithm

Haskell for Hobos -- Real World Haskell (RWH) chapter 10

The big idea

They choose as the subject an ancient and venerable format, namely "netpbm". Netpbm is a collection of file formats for (mostly) monochrome graphics:

.pbm -- P1/P4 - portable bitmap (just black and white)
.pgm -- P2/P5 - portable gray map (grey scale)
.ppm -- P3/P6 - portable pixmap (full color RGB)
.pam -- P7 - portable arbitrary map (New! -- and fancy)

The book intends to deal with P5 -- which is the binary formay for .pgm.

I rattled around and found a .pgm file test.pgm to use for this project.

ls -l test.pgm
-rw-r--r-- 1 tom tom 307215 Sep 13 22:32 test.pgm
identify test.pgm
test.pgm PGM 640x480 640x480+0+0 8-bit Grayscale Gray 307215B 0.000u 0:00.002

A quick peek at the file with my hex dumper program shows:

00000000 5035 0a36 3430 2034 3830 0a32 3535 0aff   P5 640 480 255
00000010 ffff ffff ffff ffff ffff ffff ffff ffff
00000020 ffff ffff ffff ffff ffff ffff ffff ffff

Read something, anything

The book just shows pure code to parse the image data, and procrastinates the issue of doing IO (as do most books that try to teach Haskell). We will deal with IO here, which is fairly simple, but will keep a clear separation between pure code and the code that does IO.

They use something called a "ByteString" to hold the data, and we will too. The Haskell "String" we are used to is a generic list that holds Char types. A ByteString holds an immutable sequence of 8-bit values -- just the thing to hold a raw binary file for processing. In particular we will use, as the book does, a "lazy" variant of a ByteString. A lazy bytestring does some magic in a transparent way, handling the data in "chunks" that are typically 32K in size. This allows clever things to be done that avoid needing to have a huge block of memory to hold a big ByteString.
Here is some Haskell code to get started with this:

import qualified Data.ByteString.Lazy as L

pgm_file = "test.pgm"

main = do
        input <- L.readFile pgm_file
        putStrLn pgm_file
        let len = L.length input
        putStrLn $ show len

test.pgm
307215

What is all this with dots and names like "Data.ByteString.Lazy.readFile", which we abbreviate as L.readFile?

The topic now is modules, libraries, and the import statement. The Haskell standard library is organized as a bunch of different modules. Module names always start with a capital letter. The library is organized as a hierarchy and someplace there are a bunch of directories organized just like the "dot" naming we are using. So there is a big "Data" directory, and one thing in there is a "ByteString" directory, and within that there is a "Lazy" directory.

On my linux system, this all apparently lives under /usr/lib64 -- not that you need to know or care. Deep in there I see:

.../Data/ByteString
.../Data/ByteString/Lazy

Why does the import say "qualified"? If we omitted this and just did an import, we would get the function names in the module "naked". So if the module included some special version of "length" as an example (which it does), we would have a collision with ordinary "length". When we say "qualified", the names come in with the source path prepended, requiring us to reference them as Data.ByteString.Lazy.readFile to avoid confusion (and collision) with plain old readFile. If this gets long and painful, we can append the "as L" to the import, as we do here to provide a shortened alias of our choosing. Personally, I would choose "B" instead as it speaks to me saying "bytestring".
Better yet, use "BS".

ByteStrings in some depth

• Hackage: ByteString package
• Hackage: Char8

bs = L8.pack ss - packs a plain old string into a bytestring
bs = L8.dropwhile b bs - gives the suffix after dropping bytes
b = L8.isPrefixOf s bs - a boolean, checks for "prefix" string

Back to the book

parseP5 :: L.ByteString -> Maybe (Greymap, L.ByteString)

data Greymap = Greymap }
	greyWidth :: Int
	greyHeight :: Int
	greyMax :: Int
	greyData :: L.ByteString
} deriving (Eq)

instance Show GreyMap where
	show (Greymap w h m _) = "PGM " ++
		show w ++ "x" ++ show h ++ " " ++ show m

Several helper functions are introduced to aid and abet parseP5.

matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString
matchHeader prefix str
	| prefix `L8.isPrefixOf` str
		= Just (L8.dropWhile isSpace (L.drop (L.length prefix) str ))
	| otherwise = Nothing

getNat :: L.ByteString -> Maybe ( Int, L.ByteString )
getNat s = case L8.readInt s of
	Nothing -> Nothing
	Just (num,rest)
		| num <= 0 -> Nothing
		| otherwise -> Just ( fromIntegral num, rest )

getBytes :: Int -> L.ByteString -> Maybe ( L.ByteString, L.ByteString )
getBytes n str = let count = fromIntegral n
                     both@(prefix,_) = L.splitAt count str
                 in if L.length prefix < count
				 	then Nothing
					else Just both

Couldn't match expected type ‘GHC.Internal.Int.Int64’ with actual type ‘Int’

The most interesting thing in this function is the both@(prefix,_) expression. This is what is called an "as pattern". The basic idea with an as pattern is to parse a tuple, but also keep a reference to the tuple itself. Here "both" retains the unparsed tuple. As patterns are more commonly used when we are using the colon to pull elements off the start of a list like this:

orig@(x:xs)

The "splitAt" function returns the tuple. Amusingly the documentation for this function says that it is equivalent to:

(take n xs, drop n xs).

The masterpiece

parseP5 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5 s =
    case matchHeader (L8.pack "P5") s of
        Nothing -> Nothing
        Just s1 ->
            case getNat s1 of
                Nothing -> Nothing
                Just (w, s2) ->
                    case getNat (L8.dropWhile isSpace s2) of
                        Nothing -> Nothing
                        Just (h, s3) ->
                            case getNat (L8.dropWhile isSpace s3) of
                                Nothing -> Nothing
                                Just (max, s4)
                                    | max > 255 -> Nothing
                                    | otherwise ->
                                        case getBytes 1 s4 of
                                            Nothing -> Nothing
                                            Just (_, s5) ->
                                                case getBytes (w*h) s5 of
                                                    Nothing -> Nothing
                                                    Just (map,s6) -> Just (Greymap w h max map, s6)

In truth, this is exactly the sort of thing Monads can handle. The book is sort of working up to this. As they say, "the style the above illustrates is not pleasing". I should say so. This is the very thing that I realized I was going to have to do when I first encountered Maybe. A key move at this point is to recognize the pattern in the above plumbing. The book introduces the following function:

(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v  >>? f = f v

parseP5 s =
    matchHeader (L8.pack "P5") s >>?
    \s -> skipSpace ((), s)      >>?
    (getNat . snd )              >>?
    skipSpace                    >>?
    \(_,s) -> getNat s           >>?
    skipSpace                    >>?
    \(w,s) -> getNat s           >>?
    skipSpace                    >>?
    \(h,s) -> getNat s           >>?
    \(max,s) -> getBytes 1 s     >>?
    (getBytes (w*h) . snd)       >>?
    \(map,s) -> Just (Greymap w h max map, s)

skipSpace :: (a, L.ByteString) -> Maybe (a, L.Bytestring)
skipSpace (a,s) = Just (a, L8.dropWhile isSpace s)

Further improvement

data ParseState = ParseState {
	string :: L.ByteString
	offset :: Int64
} deriving (Show)

As a side note (that is the name of the game in this essay). Haskell has a value called "undefined" that you can use anywhere. If you try to use it, your code blows up with an exception. It might be a handy temporary thing to use when you are writing code and have not yet decided what ought to be placed somewhere. It will compile and keep you moving along, but unlike putting the value 999 in the code, then forgetting about it and having to track down a wierd bug later, you will be stopped in your tracks.

The book also does this:

newtype Parse a = Parse {
	runParse :: ParseState -> Either String (a, ParseState)
}

Crucial to understanding this is understanding the Haskell State monad. The "Parse" type is clearly derived from and modified from the State monad. In fact what RWH is attempting to do is to sneak up on monads without frightening you by mentioning the monad word. As you will discover as we continue along, the game is to use this for chaining things together, but in a way specific to the parser we are writing.
I ended up writing a State monad page all about this.

Go and see if I make any sense in my "newtype" page, or try to ignore the details for now and just look at the return type. We have an "Either", which in Haskell is like a fancier version of Maybe. Instead of having "Nothing", we get to have an error string. So we find out that something went wrong and also what went wrong.

As far as the runParse function, the book pulls a rabbit out of its hat without explanation. Don't go running around like I did looking for a function defining runParse.

Take a look at this function, which the book says defines an identity parser.

identity :: a -> Parse a
identity a = Parse ( \s -> Right (a,s))

So, once this is done, the runParse function contained in this new Parse object will just take some argument (here called "s") and pack it up into a tuple along with a to use as a return value. What is important to note is that value of "a" is saved in this new Parse object to be returned each and every time runParse is called.

The book next presents this parse function, which is hardly less mysterious.

parse :: Parse a -> L.ByteString -> Either String a
parse parser initState =
	case runParse parser (ParseState initState 0) of
		Left err      -> Left err
		Right (result, _) -> Right result

• previous -- Monads (advanced)
• table of contents
• next -- Example - Euclid's algorithm