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

I’ve fixed a bug related to upgrading GHC to version 6.12 (thanks to Cale and the folks on haskell-cafe who helped me with the issue) and got my Befunge-93 interpreter up on hackage. The program is written in haskell (as usual). You should be able to get it soon with a:

$> cabal install Befunge93

If you want to read about how I designed it you can check out the source above, or take a look at my previous blog post.

Please report any bugs to me, and I’m also very interested in patches or suggestions for performance improvements if anyone ends up being interested in this program.

EDIT: Here is the package page: http://hackage.haskell.org/package/Befunge93

I just finished an initial release of an interpreter for the befunge programming language, based on the ‘93 spec. The project was quite fun! My goal was to produce a well-designed program with performance that didn’t suck too bad. Here are some highlights:

Design

I found that writing the core functionality of the interpreter took almost no time, once I settled on the approach I would take. I used a monad transformer for the first time, StateT:

type REPL a = StateT ProgramState IO a

This let me pass around the state of the computation in the State monad while doing IO actions. This made some potentially-awkward befunge commands really easy to implement.
Read the rest of this article »

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"