fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

I put together a skeleton module which should be usable for any of the problems in this year’s Google CodeJam Programming Contest (as long as they don’t adopt a new format/pattern for the problems this year). The module includes some useful parsing functions which should in the worst case be useful as a cheatsheet for those not too experienced with Parsec (*cough me). I hope it will encourage people to sign up and use Haskell in the contest!

To adapt the module to a problem, one defines the following:

1. a type Case into which we will parse a test case (i.e. problem)
2. a type SolvedCase, representing a solution to a test case
3. our algorithm :: Case -> SolvedCase
4. a Parser caseParser which can parse a single test case (n.b. not the whole file) into the Case type
5. a function formatCase :: SolvedCase -> String which brings the solution to the state where it can be prepended with the standard “Case #1: ” string

Here is the module, filled in to solve the Minimum Scalar Product practice problem. You can download the code here:

module Main
    where

import Text.ParserCombinators.Parsec
import IO hiding (try)
import System.Environment

-- PROBLEM-SPECIFIC IMPORTS --
import Data.List (sort)
import Control.Arrow
------------------------------


-- the input file will be parsed into a list of some type representing
-- individual cases to be solved by our algorithm:
type Input = [Case] 

-- our algorithms will produce a list of some type SolutionCase:
type Solution = [SolvedCase] 

-- we convert each solved case into a String, which is zipped with
--  the standard "Case #x: " strings for the final output
type Output = [String]





-- --------------- BEGIN EDITING --------------- --



-- DEFINE A TYPE TO REPRESENT A SINGLE UNSOLVED TEST CASE: --
type Case =
    -- EXAMPLE: a pair of lists of Ints (our "vectors"):
    ([Int],[Int])


-- DEFINE A TYPE TO REPRESENT A SINGLE SOLVED TEST CASE: --
type SolvedCase = 
    -- EXAMPLE: our Minimum Scalar Product as an Int:
    Int


     -- -- -- ALGORITHMS -- -- --


-- SOLVE A TEST CASE HERE:
algorithm :: Case -> SolvedCase
algorithm = 
    -- EXAMPLE: simply sort both lists, reverse one, and combine:
    sum . uncurry (zipWith (*)) . (reverse . sort *** sort)



    -- -- -- PARSING INPUT -- -- --


-- DEFINE PARSER FOR A TEST CASE: --
caseParser :: Parser Case
caseParser = do
     -- EXAMPLE: parses a case consisting of 3 lines: the first describes the
     --  number n of elements in the following two lines, the next two lines
     -- have n space-separated elements:
    w <- word
    let n = read w
    as <- count n word
    bs <- count n word
    return  (map read as, map read bs)



     -- -- -- FORMAT OUTPUT -- -- --


-- DEFINE A FUNCTION FROM AN INDIVIDUAL SolvedCase -> String.
formatCase :: SolvedCase -> String
formatCase sol = 
    -- EXAMPLE: nothing to speak of here:
    show sol
    
  

-- --------------- STOP EDITING --------------- --



    --------------------
    -- IO BOILERPLATE --
    --------------------


main = do
    
     -- pass the input file name to our program:
    (f:_) <- getArgs
    file  <- readFile f

     -- start parsing, solve problem, and prepare output:
    let inp  = parseWith mainParser file
        solution        = map algorithm inp
        solutionStrings = map formatCase solution
        outp = zipWith (++) prefixes solutionStrings
    
     -- write the prepared output to screen:
    putStr $ unlines outp


-- dies with error, or returns some datatype with our parsed data:
parseWith p = either (error . show) id . parse p "" 

-- to begin parsing, we read in a line containing the number of test cases
-- to follow. We parse them with caseParser, returning a list:
mainParser :: Parser Input
mainParser = do
    n  <- word
    ms <- count (read n) caseParser 
    return ms
    <?> "mainParser"

-- strings to prepend to output:
prefixes = [ "Case #" ++ show n ++ ": " | n <- [1..]]





    ---------------------
    -- VARIOUS PARSERS --
    ---------------------


-- -- LINE PARSERS -- --


-- a single line String, up to the newline:
wholeLine :: Parser String
wholeLine = manyTill anyChar (try newline) <?> "wholeLine"

-- parse a String with whitespace-separated values into [String]
whiteSepLine = manyTill spaceSepWord newline <?> "whiteSepLine"


-- -- WORD PARSERS -- --


-- a single word followed by whitespace (space, newline, etc.):
word = do
    w <- many1 nonWhite
    spaces
    return w
    <?> "word"

-- a single word followed by one or more ' ' characters (won't consume '\n')
spaceSepWord = do
    w <- many1 nonWhite
    many (char ' ')
    return w
    <?> "spaceSepWord"

-- e.g. "hello:world" ---> ("hello","world")
-- won't consume newlines
twoWordsSepBy c = do
    x <- manyTill nonWhite (try$ char c)
    y <- many1 nonWhite
    many (char ' ')
    return (x,y)
    <?> "twoWordsSepBy"


-- -- CHARACTER PARSERS -- --


-- nonWhitespace character:
nonWhite = noneOf " \v\f\t\r\n" <?> "nonWhite"

I’ve released my first package, up now on hackage (haddock docs should be generated soon). The module provides a simple data structure that mirrors a directory tree, and some useful functions for doing IO on directories of files. You can read more about it here.

It’s very likely there are some bugs, especially related to cross platform issues with file names and paths. The module is also fairly bare, so please send me any requests for functionality that I haven’t thought of, as well as any bugs you might find.

You can install it with:

$ cabal install directory-tree

And get the source with:

$ darcs get http://coder.bsimmons.name/code/DirectoryTree/

I hope this is useful to someone!

UPDATE: I’ve just released this as my first package on hackage. You can read more and write any comments here.

I just put together a library that provides a simple tree data structure to represent the structure of files and directories in the OS. It provides some simple IO functions like readDirectory (analogous to readFile) which “opens” a directory, returning a DirTree of Strings in the IO monad.

The nice thing is that by defining a simple instance for Traversable (and the default instances for Foldable and Functor that we get for free) we get a whole array of nice functions which we can apply to directory structures! For example, we can combine all the text in a directory of files with:

combineFiles :: FilePath -> IO [Char]
combineFiles d = do (_ :/ t) <- readDirectory d
                    return $ F.foldr1 (++) t

(the (_:/t) portion ignores the base directory returned). The DirTree type also includes a constructor for handling failures. Here is the type definition:

data DirTree a = Dir { name     :: FileName,
                       contents :: [DirTree a]  } --files + directories
               | File { name :: FileName,
                        file :: a }
               | Failed { name :: FileName,
                          err  :: Exception }
                 deriving (Show, Eq)

I have created a file with three examples:

1. in the first we simulate the command darcs initialize to illustrate creating a directory of files by hand, and writing it to disk.
2. second, we show combining several different directories from around the filesystem and assembling the into a new tree structure.
3. lastly, we use our readDirectoryWith (with Data.ByteString.readFile), and our Foldable instance to hash all the files in a directory structure (with Thomas DuBuisson’s pureMD5 package) and compare it to the hash of a different directory to see if the contents match exactly

There are probably bugs, and there are many useful functions I can think of to add if people think this is useful. I would be interested in hearing your thoughts on the interface, on any functionality you would like added, and anything else!

You can get the module and examples.hs with:

$ darcs get http://coder.bsimmons.name/code/DirectoryTree/