Dangerous Primes - Why Uniplate Doesn't Contain transform'

The Uniplate library contains many traversal operations, some based on functions in SYB (Scrap Your Boilerplate). SYB provides everywhere for bottom-up traversals and everywhere' for top-down traversals. Uniplate provides transform for bottom-up traversals, but has no operation similar to everywhere'. This article explains why I didn't include a transform' operation, and why I believe that most uses of everywhere' are probably incorrect.

The transform operation applies a function to every node in a tree, starting at the bottom and working upwards. To give a simple example:

data Exp = Lit Int | Add Exp Exp | Mul Exp Exp

f (Mul (Lit 1) x) = x
f (Mul (Lit 3) x) = Add x (Add x x)
f x = x

Calling transform f on the input 3 * (1 * 2) gives 2 + (2 + 2). We can write transform in terms of the Uniplate operation descend, which applies a function to every child node:

transform f x = f (descend (transform f) x)

On every application of f the argument always consists of a root node which has not yet been processed, along with child nodes that have been processed. My thesis explains how we can guarantee a transform reaches a fixed point, by calling f again before every constructor on the RHS of any clause:

f (Mul (Lit 1) x) = x
f (Mul (Lit 3) x) = f (Add x (f (Add x x)))
f x = x

Now transform f is guaranteed to reach a fixed point. The transform operation is predictable, and naturally defines bottom-up transformations matching the users intention. Unfortunately, the ordering and predictability of transform' is significantly more subtle. We can easily define transform':

transform' f x = descend (transform' f) (f x)

Here the transformation is applied to every child of the result of f. With transform every node is processed exactly once, but with transform' some nodes are processed multiple times, and some are not processed at all. The first clause of f, which returns x, does not result in the root of x being processed. Similarly, our second cause returns two levels of constructor, causing the inner Add to be both generated and then processed.

When people look at transform' the intuitive feeling tends to be that all the variables on the RHS will be processed (i.e. x), which in many cases mostly matches the behaviour of transform'. Being mostly correct means that many tests work, but certain cases fail - with our function f, the first example works, but 1 * (1 * 1) results in 1 * 1. The original version of Uniplate contained transform', and I spent an entire day tracking down a bug whose cause turned out to be a function whose RHS was just a variable, much like the first clause of f.

Before describing the solution to top-down transformations, it's interesting to first explore where top-down transformations are necessary. I have identified two cases, but there many be more. Firstly, top-down transformations are useful when one LHS is contained within another LHS, and you wish to favour the larger LHS. For example:

f (Mul (Add _ _) _) = ...
f (Add _ _) = Mul ...

Here the second LHS is contained within the first. If we perform a bottom-up transformation then the inner Add expression will be transformed to Mul, and the first clause will never match. Changing to a top-down transformation allows the larger rule to match first.

Secondly, top-down transformations are useful when some information about ancestors is accumulated as you proceed downwards. The typical example is a language with let expressions which builds up a set of bindings as it proceeds downwards, these bindings then affect which transformations are made. Sadly, transform' cannot express such a transformation.

The solution to both problems is to use the descend operation, and explicitly control the recursive step. We can rewrite the original example using descend:

f (Mul (Lit 1) x) = f x
f (Mul (Lit 3) x) = Add (f x) (Add (f x) (f x))
f x = descend f x

Here we explicitly call f to continue the transformation. The intuition that all variables are transformed is now stated explicitly. In this particular example we can also common-up the three subexpressions f x in the second clause, giving a more efficient transformation. If needed, we can add an extra argument to f to pass down information from the ancestors.

After experience with Uniplate I decided that using transform'/everywhere' correctly was difficult. I looked at all my uses of transform' and found that a few of them had subtle bugs, and in most cases using transform would have done exactly the same job. I looked at all the code on Hackage (several years ago) and found only six uses of everywhere', all of which could be replaced with everywhere without changing the meaning. I consider top-down transformations in the style of everywhere' to be dangerous, and strongly recommend using operations like descend instead.


Upcoming Workshops

Are you interested in either generics programming or Haskell? Are you going to ICFP 2010? Why not:

Submit a paper to the Workshop on Generic Programming - Generic programming is about making programs more adaptable by making them more general. This workshop brings together leading researchers and practitioners in generic programming from around the world, and features papers capturing the state of the art in this important area.

Offer a talk at the Haskell Implementors Workshop - an informal gathering of people involved in the design and development of Haskell implementations, tools, libraries, and supporting infrastructure.

I'm on the program committee for both, and look forward to receiving your contributions.

File Recovery with Haskell

Haskell has long been my favoured scripting language, and in this post I thought I'd share one of my more IO heavy scripts. I have an external hard drive, that due to regular dropping, is somewhat unreliable. I have a 1Gb file on this drive, which I'd like to copy, but is partly corrupted. I'd like to copy as much as I can.

In the past I've used JFileRecovery, which I thoroughly recommend. The basic algorithm is that it copies the file in chunks, and if a chunk copy exceeds a timeout it is discarded. It has a nice graphical interface, and some basic control over timeout and block sizes. Unfortunately, JFileRecovery didn't work for this file - it has three basic problems:

1. The timeout sometimes fails to stop the IO, causing the program to hang.


2. If the copy takes too long, it sometimes gives up before the end of the file.


3. If the block size is too small it takes forever, if it is too large it drops large parts of the file.

To recover my file I needed something better, so wrote a quick script in Haskell. The basic algorithm is to copy the the file in 10Mb chunks. If any chunk fails to copy, I split the chunk and retry it after all other pending chunks. The result is that the file is complete after the first pass, but the program then goes back and recovers more information where it can. I can terminate the program at any point with a working file, but waiting longer will probably recover more of the file.

I have included the script at the bottom of this post. I ran this script from GHCi, but am not going to turn it in to a proper program. If someone does wish to build on this script please do so (I hereby place this code in the public domain, or if that is not possible then under the ∀ n . BSD n licenses).

The script took about 15 minutes to write, and makes use of exceptions and file handles - not the kind of program traditionally associated with Haskell. A lot of hard work has been spent polishing the GHC runtime, and the Haskell libraries (bytestring, exceptions). Now this work has been done, slotting together reasonably complex scripts is simple.

{-# LANGUAGE ScopedTypeVariables #-}

import Data.ByteString(hGet, hPut)
import System.IO
import System.Environment
import Control.Monad
import Control.Exception


src = "file on dodgy drive (source)"
dest = "file on safe drive (destination)"

main :: IO ()
main =
    withBinaryFile src ReadMode $ \hSrc -> 
    withBinaryFile dest WriteMode $ \hDest -> do
    nSrc <- hFileSize hSrc
    nDest <- hFileSize hDest
    when (nSrc /= nDest) $ hSetFileSize hDest nSrc
    copy hSrc hDest $ split start (0,nSrc)


copy :: Handle -> Handle -> [(Integer,Integer)] -> IO ()
copy hSrc hDest [] = return ()
copy hSrc hDest chunks = do
    putStrLn $ "Copying " ++ show (length chunks) ++ " of at most " ++ show (snd $ head chunks)
    chunks <- forM chunks $ \(from,len) -> do
        res <- Control.Exception.try $ do
            hSeek hSrc AbsoluteSeek from
            hSeek hDest AbsoluteSeek from
            bs <- hGet hSrc $ fromIntegral len
            hPut hDest bs
        case res of
            Left (a :: IOException) -> do putChar '#' ; return $ split (len `div` 5) (from,len)
            Right _ -> do putChar '.' ; return []
    putChar '\n'
    copy hSrc hDest $ concat chunks

start = 10000000
stop = 1000

split :: Integer -> (Integer,Integer) -> [(Integer,Integer)]
split i (a,b) | i < stop = []
              | i >= b = [(a,b)]
              | otherwise = (a,i) : split i (a+i, b-i)

There are many limitations in this code, but it was sufficient to recover my file quickly and accurately.

Optimising HLint

HLint is a tool for suggesting improvements to Haskell code. Recently I've put some effort in to optimisation and HLint is now over 20 times faster. The standard benchmark (running HLint over the source code of HLint) has gone from 30 seconds to just over 1 second. This blog post is the story of that optimisation, the dead ends I encountered, and the steps I took. I've deliberately included reasonable chunks of code in this post, so interested readers can see the whole story - less technical readers should feel free to skip them. The results of the optimisation are all available on Hackage, as new versions of hlint, uniplate and derive.

Before I start, I'd like to share my five guiding principles of optimisation:

• Tests - make sure you have tests, so you don't break anything while optimising.


• Profile - if you don't profile first, you are almost certainly optimising the wrong thing.


• Necessity - only start the optimisation process if something is running too slowly.


• Benchmark - use a sensible and representative test case to benchmark, to make sure you optimise the right thing.


• Optimising - to make a function faster, either call it less, or write it better.

Below are the steps in the optimisation, along with their speed improvement.


Special support for Rational in Uniplate.Data, 30s to 10s

HLint uses Uniplate extensively. HLint works over large abstract syntax trees, from the library haskell-src-exts (HSE), so a generics library is essential. There are two main variants of Uniplate - Data builds on the Scrap Your Boilerplate (SYB) instances, and Direct requires special instances. HLint uses the Data variant, as it requires no instances to be written.

One of the advantages of Uniplate is that it generally outperforms most generics libraries. In particular, the variant written on top of Data instances is often many times faster than using SYB directly. The reason for outperforming SYB is documented in my PhD thesis. The essential idea is that Uniplate builds a "hit table", a mapping noting which types can be contained within which other types - e.g. that there is potentially an Int inside Either String [Int], but there isn't an Int inside String. By consulting this mapping while traversing a value, Uniplate is able to skip large portions, leading to an efficiency improvement.

When computing the hit table it is necessary for Uniplate to create dummy values of each type, which it then traverses using SYB functions. To create dummy values Uniplate uses undefined, unfortunately given the definition data Foo = Foo !Int the value Foo undefined will be forced due to the strictness annotation, and the code will raise an error - as described in bug 243. Uniplate 1.2 had a special case for Rational, which is the only type with strict components contained within HSE. Uniplate 1.3 fixed this problem more generally by catching the exception and turning off the hit table facility on such types. Unfortunately this caused Uniplate 1.3 to turn off the hit table for HSE, causing HLint to run three times slower.

The fix was simple, and pragmatic, but not general. In Uniplate 1.4 I reinstated the special case for Rational, so now HLint makes use of the hit table, and goes three times faster. A more general solution would be to manufacture dummy values for certain types (it's usually an Int or Integer that is a strict component), or to create concrete dummy values using SYB. It's interesting to observe that if HLint used SYB as it's generics library, it would not be using the hit table trick, and would run three times slower.


Use Uniplate.Direct, 10s to 5s, reverted

Uniplate also provides a Direct version, which performs better, but requires instances to be written. In order to further improve the speed of HLint I decided to try the Direct version. The biggest hurdle to using the Direct version is that many instances need to be generated, in the case of HLint it required 677. The first step was to modify the Derive tool to generate these instances (which Derive 2.1 now does), and to write a small script to decide which instances were necessary. With these instances in place, the time dropped to 5 seconds.

Unfortunately, the downside was that compilation time skyrocketed, and the instances are very specific to a particular version of HSE. While these problems are not insurmountable, I did not consider the benefit to be worthwhile, so reverted the changes. It's worth pointing out that most users of Uniplate won't require so many instances to use the Direct versions, and that a program can be switched between Direct and Data versions without any code changes (just a simple import). I also considered the possibility of discovering which Uniplate instances dominated and using the Direct method only for those - but I did not investigate further.


Add and optimise eqExpShell, 10s to 8s

The next step was to profile. I compiled and ran HLint with the following options:

ghc --make -O1 -prof -auto-all -o hlint
hlint src +RTS -p

Looking at the profiling output, I saw that the function unify took up over 60% of the execution time:

unify :: NameMatch -> Exp -> Exp -> Maybe [(String,Exp)]
unify nm (Do xs) (Do ys) | length xs == length ys = concatZipWithM (unifyStmt nm) xs ys
unify nm (Lambda _ xs x) (Lambda _ ys y) | length xs == length ys = liftM2 (++) (unify nm x y) (concatZipWithM unifyPat xs ys)
unify nm x y | isParen x || isParen y = unify nm (fromParen x) (fromParen y)
unify nm (Var (fromNamed -> v)) y | isUnifyVar v = Just [(v,y)]
unify nm (Var x) (Var y) | nm x y = Just []
unify nm x y | ((==) `on` descend (const $ toNamed "_")) x y = concatZipWithM (unify nm) (children x) (children y)
unify nm _ _ = Nothing

The function unify is an essential part of the rule matching in HLint, and attempts to compare a rule to a target expression, and if successful returns the correct substitution. Each rule is compared to every expression in all files, which means that unify is called millions of times in a normal HLint run. Looking closely, my first suspicion was the second line from the bottom in the guard - the call to descend and (==). This line compares the outer shell of two expressions, ignoring any inner expressions. It first uses the Uniplate descend function to insert a dummy value as each subexpression, then compares for equality. To test my hypothesis that this method was indeed the culprit I extracted it to a separate function, and modified unify to call it:

eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell = (==) `on` descend (const $ toNamed "_")

I reran the profiling, and now all the time was being spent in eqExpShell. My first thought was to expand out the function to not use Uniplate. I quickly rejected that idea - there are expressions within statements and patterns, and to follow all the intricacies of HSE would be fragile and verbose.

The first optimisation I tried was to replace toNamed "_", the dummy expression, with something simpler. The toNamed call expands to many constructors, so instead I used Do an [] (an is a dummy source location), which is the simplest expression HSE provides. This change had a noticeable speed improvement.

eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell = (==) `on` descend (const $ Do an [])

My second thought was to add a quick test, so that if the outer constructors were not equal then the expensive test was not tried. Determining the outer constructor of a value can be done by calling show then only looking at the first word (assuming a sensible Show instance, which HSE has).

eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell x y =
    ((==) `on` constr) x y &&
    ((==) `on` descend (const $ Do an [])) x y
    where constr = takeWhile (not . isSpace) . show

This change had a bigger speed improvement. I found that of the 1.5 million times eqExpShell was called, the quick equality test rejected 1 million cases.

My next thought was to try replacing constr with the SYB function toConstr. There was no noticeable performance impact, but the code is neater, and doesn't rely on the Show instance, so I stuck with it. After all these changes HLint was 2 seconds faster, but eqExpShell was still the biggest culprit on the profiling report.

Write eqExpShell entirely in SYB, 8s to 8s, reverted

My next thought was to rewrite eqExpShell entirely in SYB functions, not using the Eq instance at all. The advantages of this approach would be that I can simply disregard all subexpressions, I only walk the expression once, and I can skip source position annotations entirely. Starting from the geq function in SYB, I came up with:

data Box = forall a . Data a => Box a

eqExpShellSYB :: Exp_ -> Exp_ -> Bool
eqExpShellSYB = f
    where
        f :: (Data a, Data b) => a -> b -> Bool
        f x y = toConstr x == toConstr y &&
                and (zipWith g (gmapQ Box x) (gmapQ Box y))

        g (Box x) (Box y) = tx == typeAnn || tx == typeExp || f x y
            where tx = typeOf x

typeAnn = typeOf an
typeExp = typeOf ex

Unfortunately, this code takes exactly the same time as the previous version, despite being significantly more complex. My guess is that toConstr is not as fast as the Eq instance, and that this additional overhead negates all the other savings. I decided to revert back to the simpler version.

Call eqExpShell less, 8s to 4s

Having failed to optimise eqExpShell further, I then thought about how to call it less. I added a trace and found that of the 1.5 million calls, in 1.3 million times at least one of the constructors was an App. Application is very common in Haskell programs, so this is not particularly surprising. By looking back at the code for unify I found several other constructors were already handled, so I added a special case for App.

unify nm (App _ x1 x2) (App _ y1 y2) = liftM2 (++) (unify nm x1 y1) (unify nm x2 y2)

It is easy to show that if an App (or any specially handled constructor) is passed as either argument to eqExpShell then the result will be False, as if both shells had been equal a previous case would have matched. Taking advantage of this observation, I rewrote the line with the generic match as:

unify nm x y | isOther x && isOther y && eqExpShell x y = concatZipWithM (unify nm) (children x) (children y)
    where 
        isOther Do{} = False
        isOther Lambda{} = False
        isOther Var{} = False
        isOther App{} = False
        isOther _ = True

With this change the eqExpShell function was called substantially less, it disappeared from the profile, and the speed improved to 4 seconds.

Fix Uniplate bug, 4s to 1.3s

The next step was to rerun the profiling. However, the results were very confusing - almost 70% of the execution time was recorded to three CAF's, while I could see no obvious culprit. I reran the profiler with the -caf-all flag to more precisely report the location of CAF's, and was again confused - the optimiser had rearranged the functions to make -caf-all useless. I then reran the profiler with optimisation turned off using -O0 and looked again. This time the profiling clearly showed Uniplate being the source of the CAF's. The hit table that Uniplate creates is stored inside a CAF, so was an obvious candidate.

Turning back to Uniplate, I attempted to reproduce the bug outside HLint. I enhanced the benchmarking suite by adding a method to find all the String's inside very small HSE values. The standard Uniplate benchmarks are for testing the performance of running code, and I had neglected to check the creation of the hit table, assuming it to be negligible.

testN "Module" $ Module ssi Nothing [] [] []
testN "Decl" $ FunBind ssi []
testN "Exp" $ Do ssi []
testN "Pat" $ PWildCard ssi

testN :: Biplate a String => String -> a -> IO ()
testN msg x = do
    t <- timer $ evaluate $ length (universeBi x :: [String])
    putStrLn $ "HSE for " ++ msg ++ " takes " ++ dp2 t ++ "s"

My initial worry was that at 2 decimal places I was likely to see 0.00 for all values. However, that turned out not to be a problem! What I saw was:

HSE for Module takes 0.54
HSE for Decl takes 0.86
HSE for Exp takes 2.54
HSE for Pat takes 0.32

These results surprised me. In particular, the hit table from Exp to String is a subset of the Module one, so should always be faster. The computation of the hit table is reasonably complex, and I was unable to isolate the problem. The tricky part of the hit table is that it is necessary to take the fixed point of the transitive closure of reachability - I had tried to keep track of recursive types and reach a fixed point with the minimal number of recomputations. I clearly failed, and probably had an exponential aspect to the algorithm that under certain circumstances caused ridiculously bad behaviour.

Rather than try to diagnose the bug, I decided instead to rethink the approach, and simplify the design. In particular, the fixed point of the transitive closure is now written as:

fixEq trans (populate box)

Where populate finds the immediate children of a constructor, trans takes the transitive closure based on the current state, and fixEq takes the fixed point. Using this new simpler design I was also able to compute which types contained with types recursively and cache it, meaning that now computing the hit table for Module not only computes the hit table for Exp, but does so in a way that means the result can be reused when asking about Exp. After rewriting the code I reran the benchmark:

HSE for Module takes 0.03
HSE for Decl takes 0.00
HSE for Exp takes 0.00
HSE for Pat takes 0.00

I had hoped that the rewrite would fix the performance problems, and it did. I have not diagnosed the original performance bug, but at 0.03 seconds I was satisfied. I have now released Uniplate 1.5 with the revised hit table code. With this change, the time for HLint drops to 1.3 seconds and all the CAF's went away from the profile.


Sharing computation, 1.3s to 1.2s

At this point, I was happy to finish, but decided to profile just one last time. The top function in the list was matchIdea:

matchIdea :: NameMatch -> Setting -> Exp_ -> Maybe Exp_
matchIdea nm MatchExp{lhs=lhs,rhs=rhs,side=side} x = do
    u <- unify nm (fmap (const an) lhs) (fmap (const an) x)
    u <- check u
    guard $ checkSide side u
    let rhs2 = subst u rhs
    guard $ checkDot lhs rhs2
    return $ unqualify nm $ dotContract $ performEval rhs2

This function first strips both the rule (lhs) and the expression (x) of their source position information to ensure equality works correctly. However, both the rules and expressions are reused multiple times, so I moved the fmap calls backwards so each rule/expression is only ever stripped of source position information once. With this change the runtime was reduced to 1.2 seconds.


Final Results

After all that effort, I reran the profile results and got:

parseString                    HSE.All               16.2   17.7
matchIdea                      Hint.Match            14.4    1.6
eqExpShellSlow                 HSE.Eq                 9.2   11.4
listDecl                       Hint.List              6.1    4.1
lambdaHint                     Hint.Lambda            5.1    5.6
bracketHint                    Hint.Bracket           4.1    6.4
hasS                           Hint.Extensions        4.1    5.0
monadHint                      Hint.Monad             4.1    2.9
~=                             HSE.Match              4.1    2.5
isParen                        HSE.Util               3.1    0.0

Now the largest contributor to the HLint runtime is the parsing of Haskell files. There are no obvious candidates for easy optimisations, and the code runs sufficiently fast for my purposes.

Conclusions

There is still some scope for optimisation of HLint, but I leave that for future work. One possible avenue for exploration would be turning on selected packages of hints, to see which one takes the most time - profiling on a different measure.

In optimising HLint I've found two issues in Uniplate, the first of which I was aware of, and the second of which came as a total surprise. These optimisations to Uniplate will benefit everyone who uses it. I have achieved the goal of optimising HLint, simply by following the profile reports, and as a result HLint is now substantially faster than I had ever expected.

Footnote: I didn't actually profile first, as I knew that a performance regression was caused by the upgrade to Uniplate 1.3, so knew where to start looking. Generally, I would start with a profile.

Better .ghci files

A few days ago I posted about my plan to use .ghci files for all my projects. I am now doing so in at least five projects, and it's working great. There were two disadvantages: 1) every command had to be squeezed on to a single line; 2) some names were introduced into the global namespace. Thanks to a hint from doliorules, about :{ :} I can eliminate these disadvantages.

Let's take the previous example from HLint's .ghci file:

let cmdHpc _ = return $ unlines [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test",":!del hlint-test.tix",":!.hpc\\hlint-test --help",":!.hpc\\hlint-test --test",":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3",":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3",":!hpc.exe markup hlint-test.tix --destdir=.hpc",":!hpc.exe report hlint-test.tix",":!del hlint-test.tix",":!start .hpc\\hpc_index_fun.html"]
:def hpc cmdHpc

It work's, but it's ugly. However, it can be rewritten as:

:{
:def hpc const $ return $ unlines
    [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test"
    ,":!del hlint-test.tix"
    ,":!.hpc\\hlint-test --help"
    ,":!.hpc\\hlint-test --test"
    ,":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3"
    ,":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3"
    ,":!hpc.exe markup hlint-test.tix --destdir=.hpc"
    ,":!hpc.exe report hlint-test.tix"
    ,":!del hlint-test.tix"
    ,":!start .hpc\\hpc_index_fun.html"]
:}

The :{ :} notation allows multi-line input in GHCi. GHCi also allows full expressions after a :def. Combined, we now have a much more readable .ghci file.

Using .ghci files to run projects

I develop a reasonable number of different Haskell projects, and tend to switch between them regularly. I often come back to a project after a number of months and can't remember the basics - how to load it up, how to test it. Until yesterday, my technique was to add a ghci.bat file to load the project, and invoke the tests with either :main test or :main --test. For some projects I also had commands to run hpc, or perform profiling. Using .ghci files, I can do much better.

All my projects are now gaining .ghci files in the root directory. For example, the CmdArgs project has:

:set -w -fwarn-unused-binds -fwarn-unused-imports
:load Main

let cmdTest _ = return ":main test"
:def test cmdTest

The first line sets some additional warnings. I usually develop my projects in GHCi with lots of useful warnings turned on. I could include these warnings in the .cabal file, but I'd rather have them when developing, and not display them when other people are installing.

The second line loads the Main.hs file, which for CmdArgs is the where I've put the main tests.

The last two lines define a command :test which when invoked just runs :main test, which is how I run the test for CmdArgs.

To load GHCi with this configuration file I simply change to the directory, and type ghci. It automatically loads the right files, and provides a :test command to run the test suite.

I've also converted the HLint project to use a .ghci file. This time the .ghci file is slightly different, but the way I load/test my project is identical:

:set -fno-warn-overlapping-patterns -w -fwarn-unused-binds -fwarn-unused-imports
:set -isrc;.
:load Main

let cmdTest _ = return ":main --test"
:def test cmdTest

let cmdHpc _ = return $ unlines [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test",":!del hlint-test.tix",":!.hpc\\hlint-test --help",":!.hpc\\hlint-test --test",":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3",":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3",":!hpc.exe markup hlint-test.tix --destdir=.hpc",":!hpc.exe report hlint-test.tix",":!del hlint-test.tix",":!start .hpc\\hpc_index_fun.html"]
:def hpc cmdHpc

The first section turns on/off the appropriate warnings, then sets the include path and loads the main module.

The second section defines a command named :test, which runs the tests.

The final section defines a command named :hpc which runs hpc and pops up a web browser with the result. Unfortunately GHC requires definitions entered in a .ghci file to be on one line, so the formatting isn't ideal, but it's just a list of commands to run at the shell.

Using a .ghci file for all my projects has a number of advantages:

• I have a consistent interface for all my projects.


• Typing :def at the GHCi prompt says which definitions are in scope, and thus which commands exist for this project.


• I've eliminated the Windows specific .bat files.


• The .ghci file mechanism is quite powerful - I've yet to explore it fully, but could imagine much more complex commands.

Update: For a slight improvement on this technique see this post.

Thanks to Gwern Branwen for submitting a .ghci file for running HLint, and starting my investigation of .ghci files.

Explaining Haskell IO without Monads

This tutorial explains how to perform IO in Haskell, without attempting to give any understanding of monads. We start with the simplest example of IO, then build up to more complex examples. You can either read the tutorial to the end, or stop at the end of any section - each additional section will let you tackle new problems. We assume basic familiarity with Haskell, such as the material covered in chapters 1 to 6 of Programming in Haskell by Graham Hutton.

IO Functions

In this tutorial I use four standard IO functions:

• readFile :: FilePath -> IO String -- read in a file


• writeFile :: FilePath -> String -> IO () -- write out a file


• getArgs :: IO [String] -- get the command line arguments, from the module System.Environment


• putStrLn :: String -> IO () -- write out a string, followed by a new line, to the console

Simple IO

The simplest useful form of IO is to read a file, do something, then write out a file.

main :: IO ()
main = do
   src <- readFile "file.in"
   writeFile "file.out" (operate src)

operate :: String -> String
operate = ... -- your code here

This program gets the contents of file.in, runs the operate function on it, then writes the result to file.out. The main function contains all the IO operations, while operate is entirely pure. When writing operate you do not need to understand any details of IO. This pattern of IO was sufficient for my first two years of programming Haskell.

Action List

If the pattern described in Simple IO is insufficient, the next step is a list of actions. A main function can be written as:

main :: IO ()
main = do
    x1 <- expr1
    x2 <- expr2
    ...
    xN <- exprN
    return ()

The main function starts with do, then has a sequence of xI <- exprI statements, and ends with return (). Each statement has a pattern on the left of the arrow (often just a variable), and an expression on the right. If the expression is not of type IO, then you must write xI <- return (exprI). The return function takes a value, and wraps it in the IO type.

As a simple example we can write a program that gets the command line arguments, reads the file given by the first argument, operates on it, then writes out to the file given by the second argument:

main :: IO ()
main = do
    [arg1,arg2] <- getArgs
    src <- readFile arg1
    res <- return (operate src)
    _ <- writeFile arg2 res
    return ()

As before, operate is a pure function. The first line after the do uses a pattern match to extract the command line arguments. The second line reads the file specified by the first argument. The third line uses return to wrap a pure value. The fourth line provides no useful result, so we ignore it by writing _ <-.

Simplifying IO

The action list pattern is very rigid, and people usually simplify the code using the following three rules:

1. _ <- x can be rewritten as x.


2. If the penultimate line doesn't have a binding arrow (<-) and is of type IO (), then the return () can be removed.


3. x <- return y can be rewritten as let x = y (provided you don't reuse variable names).

With these rules we can rewrite our example as:

main :: IO ()
main = do
    [arg1,arg2] <- getArgs
    src <- readFile arg1
    let res = operate src
    writeFile arg2 res

Nested IO

So far only the main function has been of type IO, but we can create other IO functions, to wrap up common patterns. For example, we can write a utility function to print nice looking titles:

title :: String -> IO ()
title str = do
    putStrLn str
    putStrLn (replicate (length str) '-')
    putStrLn ""

We can use this title function multiple times within main:

main :: IO ()
main = do
    title "Hello"
    title "Goodbye"

Returning IO Values

The functions we've written so far have all been of type IO (), which lets us perform IO actions, but not give back interesting results. To give back the value x, we write return x as the final line of the do block. Unlike the imperative language return statement, this return must be on the final line.

readArgs :: IO (String,String)
readArgs = do
    xs <- getArgs
    let x1 = if length xs > 0 then xs !! 0 else "file.in"
    let x2 = if length xs > 1 then xs !! 1 else "file.out"
    return (x1,x2)

This function returns the first two command line arguments, or supplies default values if fewer arguments are given. We can now use this in the main program from before:

main :: IO ()
main = do
    (arg1,arg2) <- readArgs
    src <- readFile arg1
    let res = operate src
    writeFile arg2 res

Now, if less than two arguments are given, the program will use default file names instead of crashing.

Optional IO

So far we've only seen a static list of IO statements, executed in order. Using if, we can choose what IO to perform. For example, if the user enters no arguments we can tell them:

main :: IO ()
main = do
    xs <- getArgs
    if null xs then do
        putStrLn "You entered no arguments"
     else do
        putStrLn ("You entered " ++ show xs)

For optional IO you make the final statement of the do block an if, then under each branch continue the do. The only subtle point is that the else must be indented by one more space than the if. This caveat is widely considered to be a bug in the definition of Haskell, but for the moment, the extra space before the else is required.

Break Time

If you've gone from understanding no IO to this point in the tutorial, I suggest you take a break (a cookie is recommended). The IO presented above is all that imperative languages provide, and is a useful starting point. Just as functional programming provides much more powerful ways of working with functions by treating them as values, it also allows IO to be treated as values, which we explore in the rest of the tutorial.

Working with IO Values

The next stage is to work with IO as values. Until now, all IO statements have been executed immediately, but we can also create variables of type IO. Using our title function from above we can write:

main :: IO ()
main = do
    let x = title "Welcome"
    x
    x
    x

Instead of running the IO with x <-, we have placed the IO value in the variable x, without running it. The type of x is IO (), so we can now write x on a line to execute the action. By writing the x three times we perform the action three times.

Passing IO Arguments

We can also pass IO values as arguments to functions. In the previous example we ran the IO action three times, but how would we run it fifty times? We can write a function that takes an IO action, and a number, and runs the action that number of times:

replicateM_ :: Int -> IO () -> IO ()
replicateM_ n act = do
    if n == 0 then do
        return ()
     else do
        act
        replicateM_ (n-1) act

This definition makes use of optional IO to decide when to stop, and recursion to continue performing the IO. We can now rewrite the previous example as:

main :: IO ()
main = do
    let x = title "Welcome"
    replicateM_ 3 x

In an imperative language the replicateM_ function is built in as a for statement, but the flexibility of Haskell allows us to define new control flow statements - a very powerful feature. The replicateM_ function defined in Control.Monad is like ours, but more general, and can be used instead.

IO in Structures

We've seen IO values being passed as arguments, so it's natural that we can also put IO in structures such as lists and tuples. The function sequence_ takes a list of IO actions, and executes each action in turn:

sequence_ :: [IO ()] -> IO ()
sequence_ xs = do
    if null xs then do
        return ()
     else do
        head xs
        sequence_ (tail xs)

If there are no elements in the list then sequence_ stops, with return (). If there are elements in the list then sequence_ gets the first action (with head xs) and executes it, then calls sequence_ on the remaining actions. As before, sequence_ is available in Control.Monad, but in a more general form. It is now simple to rewrite replicateM_ in terms of sequence_:

replicateM_ :: Int -> IO () -> IO ()
replicateM_ n act = sequence_ (replicate n act)

Pattern Matching

A much more natural definition of sequence_, rather than using null/head/tail, is to make use of Haskell's pattern matching. If there is exactly one statement in a do block, you can remove the do. Rewriting sequence_ we can eliminate the do after the equals sign, and the do after the then keyword.

sequence_ :: [IO ()] -> IO ()
sequence_ xs =
    if null xs then
        return ()
     else do
        head xs
        sequence_ (tail xs)

Now we can replace the if with pattern matching, without needing to consider the IO:

sequence_ :: [IO ()] -> IO ()
sequence_ [] = return ()
sequence_ (x:xs) = do
    x
    sequence_ xs

Final Example

As a final example, imagine we wish to perform some operation on every file given at the command line. Using what we have already learnt, we can write:

main :: IO ()
main = do
    xs <- getArgs
    sequence_ (map operateFile xs)

operateFile :: FilePath -> IO ()
operateFile x = do
    src <- readFile x
    writeFile (x ++ ".out") (operate src)

operate :: String -> String
operate = ...

IO Design

A Haskell program usually consists of an outer IO shell calling pure functions. In the previous example main and operateFile are part of the IO shell, while operate and everything it uses are pure. As a general design principle, keep the IO layer small. The IO layer should concisely perform the necessary IO, then delegate to the pure part. Use of explicit IO in Haskell is necessary, but should be kept to a minimum - pure Haskell is where the beauty lies.

Where to go now

You should now be equipped to do all the IO you need. To become more proficient I recommend any of the following:

• Write lots of Haskell code.


• Read chapters 8 and 9 of Programming in Haskell by Graham Hutton. You should expect to spend about 6 hours thinking and contemplating on sections 8.1 to 8.4 (I recommend going to a hospital A&E department with a minor injury).


• Read Monads as Containers, an excellent introduction to monads.


• Look at the documentation on the monad laws, and find where I've used them in this tutorial.


• Read through all the functions in Control.Monad, try to define them, and then use them when writing programs.


• Implement and use a state monad.

Haskell DLL's on Windows

The current section of the GHC manual on creating DLL's on Windows is fairly confusing to read, and has some bugs (i.e. 3605). Since I got tripped up by the current documentation, I offered to rewrite sections 11.6.2 and 11.6.3 (merging them in the process). Creating Windows DLL's with GHC is surprisingly easy, and my revised manual section includes an example which can be called from both Microsoft Word (using VBA) and C++. I've pasted the revised manual section as the rest of this blog post. I'll shortly be submitting it to the GHC team, so any feedback is welcome.

---

11.6.2. Making DLLs to be called from other languages

This section describes how to create DLLs to be called from other languages, such as Visual Basic or C++. This is a special case of Section 8.2.1.2, "Making a Haskell library that can be called from foreign code"; we'll deal with the DLL-specific issues that arise below. Here's an example:

Use foreign export declarations to export the Haskell functions you want to call from the outside. For example:

-- Adder.hs
{-# LANGUAGE ForeignFunctionInterface #-}
module Adder where

adder :: Int -> Int -> IO Int  -- gratuitous use of IO
adder x y = return (x+y)

foreign export stdcall adder :: Int -> Int -> IO Int

Add some helper code that starts up and shuts down the Haskell RTS:

// StartEnd.c
#include <Rts.h>

extern void __stginit_Adder(void);

void HsStart()
{
   int argc = 1;
   char* argv[] = {"ghcDll", NULL}; // argv must end with NULL

   // Initialize Haskell runtime
   char** args = argv;
   hs_init(&argc, &args);

   // Tell Haskell about all root modules
   hs_add_root(__stginit_Adder);
}

void HsEnd()
{
   hs_exit();
}

Here, Adder is the name of the root module in the module tree (as mentioned above, there must be a single root module, and hence a single module tree in the DLL). Compile everything up:

$ ghc -c Adder.hs
$ ghc -c StartEnd.c
$ ghc -shared -o Adder.dll Adder.o Adder_stub.o StartEnd.o

Now the file Adder.dll can be used from other programming languages. Before calling any functions in Adder it is necessary to call HsStart, and at the very end call HsEnd.

NOTE: It may appear tempting to use DllMain to call hs_init/hs_exit, but this won’t work (particularly if you compile with -threaded).

11.6.2.1. Using from VBA

An example of using Adder.dll from VBA is:

Private Declare Function Adder Lib "Adder.dll" Alias "adder@8" _
      (ByVal x As Long, ByVal y As Long) As Long

Private Declare Sub HsStart Lib "Adder.dll" ()
Private Declare Sub HsEnd Lib "Adder.dll" ()

Private Sub Document_Close()
HsEnd
End Sub

Private Sub Document_Open()
HsStart
End Sub

Public Sub Test()
MsgBox "12 + 5 = " & Adder(12, 5)
End Sub

This example uses the Document_Open/Close functions of Microsoft Word, but provided HsStart is called before the first function, and HsEnd after the last, then it will work fine.

11.6.2.2. Using from C++

An example of using Adder.dll from C++ is:

// Tester.cpp
#include "HsFFI.h"
#include "Adder_stub.h"
#include <stdio.h>

extern "C" {
    void HsStart();
    void HsEnd();
}

int main()
{
    HsStart();
    // can now safely call functions from the DLL
    printf("12 + 5 = %i\n", adder(12,5))    ;
    HsEnd();
    return 0;
}

This can be compiled and run with:

$ ghc -o tester Tester.cpp Adder.dll.a
$ tester
12 + 5 = 17

Please give feedback in the comments.

Reviewing View Patterns

View Patterns are an interesting extension to the pattern matching capabilities of Haskell, implemented in GHC 6.10 and above. After using view patterns in real world programs, including HLint, I've come to like them. I use view patterns in 10 of the 27 modules in HLint.

View Pattern Overview

My intuitive understanding of view patterns is given in my Approaches and Applications of Inductive Programming 2009 paper, which describes the view pattern translation as:

f (sort -> min:ascending) = ...
    ==
f v_1 | min:ascending <- sort v_1 = ...
    ==
f v_1 | case v_2 of _:_ -> True ; _ -> False = ...
    where  v_2 = sort v_1 ; min:ascending = v_2

The view pattern on the first line sorts the list elements, then binds the lowest element to min and the remaining elements to ascending. If there are no elements in the list then the pattern will not match. This can be translated to a pattern guard, which can then be translated to a case expression. This translation does not preserve the scoping behaviour of the variables, but is sufficient for all my uses of view patterns. It is important to note that the translation from view patterns to pattern guards is fairly simple, and mainly eliminates one redundant intermediate variable. However, the translation from pattern guards to case expressions and guards is substantially harder.

How I Use View Patterns

My uses of view patterns seem to fall into a few distinct categories. Here are some example code snippets (mainly from HLint), along with explanation.

1) Complex/Nested Matching

uglyEta (fromParen -> App f (fromParen -> App g x)) (fromParen -> App h y) = g == h

Every operation/match pair in a pattern guard requires a separate pattern guard, whereas view patterns can be nested very naturally. Here the abstract syntax tree for expressions has brackets, and the fromParen function unwraps any brackets to find the interesting term inside. View patterns allow us to perform nested matches, which would have required three separate pattern guards.

2) Matching on a Different Structure

isAppend (view -> App2 op _ _) = op ~= "++"

The expression tree I use in HLint has lots of expressions which apply a function to two arguments - for example App (App (Var f) x) y and InfixOp x f y. I have a type class View that maps expressions into the data type data App2 = NoApp2 | App2 String Exp Exp, allowing easy matching on a range of expressions.

3) Safe Normalisation

dismogrify (simplify -> x) = .... x ....

While working with Yhc Core for the Catch and Supero tools I often wanted to process a syntax tree after simplifying it. If you name the original tree x, and the simplified tree y, then it's an easy (and type-safe) mistake to use x instead of y. To avoid this I wrote:

dismogrify bad_x = .... x ....
   where x = simplify bad_x

Using bad_x in the expression makes the mistake easy for a human to spot. Using a view pattern makes the mistake impossible.

4) Mapping

classify (Ident (getRank -> x)) = ...

Sometimes I want to take a variable in one domain, and work with it in another. In the above example getRank converts a String to a Rank enumeration. Within the classify function I only wish to work with the rank as an enumeration, so it's convenient to never bind the string. This pattern is similar to safe normalisation, but it's purpose isn't safety - just making things a little neater.

5) Abstraction

The view pattern example in the GHC manual is all about abstraction. I have mainly used HLint in programs which don't use abstract data types, just algebraic data types which are intended to be manipulated directly. I don't think there are many data types which are both abstract and have a structural view, so I suspect this use will be less common (Data.Sequence is the only type that comes to mind).

Improvements I Suggest

I think there are three improvements that should be made to the view patterns in GHC 6.10.4:

1) Warnings

In GHC 6.10 all view patterns are incorrectly considered overlapping (see bug #2395), so all users of view patterns need to supply -fno-warn-overlapping-patterns. This problem has been fixed in GHC 6.12, which is great news.

2) Scoping

The current scoping behaviour seems undesirable:

apply (f -> y) = ...
    where f = ...

Here the f in the view pattern isn't the f bound at the where. I suggest that the lhs of the -> can use variables from the where, in a similar manner to pattern guards. (It's possible this suggestion is misguided, as the scoping rules can be quite subtle.)

3) Implicit Patterns

The original view patterns wiki document asks what should become of (-> ...), and proposes it become (view -> ...). I like this idea as HLint already contains 12 instances of (view -> ...). The only question is which view should be used? I think there are two possible answers:

a) The view currently in scope

If the desugaring is simply to view, then people can select their imports appropriately to choose their view function. This proposal is similar to the rebindable syntax already supported, but in this case may be a legitimate default, due to several possible view interpretations. If one day everyone starts using Data.View.view, then the default could be switched. As an example (in combination with proposal 2) we could have:

uglyEta (-> App f (-> App g x)) (-> App h y) = g == h
    where view = fromParen

b) Data.View.view

In HLint I have used:

class View a b where
    view :: a -> b

I haven't needed any functional dependencies, as the matching always constrains the types sufficiently. I have mapped one source type (i.e. Exp) to several matching types (App2 and App1), but never mapped multiple source types onto one matching type. If I was to add a dependency it should be that b uniquely determines a, as usually b will have a pattern on the RHS which will constrain b already.

I think my preference is for using Data.view.view, primarily because all other Haskell syntax is bound to a fixed name, rather than using the name currently in scope. However, my opinions on functional dependencies should be taken with skepticism - I'm not normally a user of functional dependencies.

4) Rejected Suggestions

I do not support the idea of implicit view patterns without some leading syntax (see bug 3583) - view patterns are nice, but I don't think they are important enough to be first-class, like they are in F# (note that F# interoperates with OO languages, so first-class view patterns are much more reasonable there).

I also do not support the idea of implicit Maybe in view patterns - Maybe should not be special, and this suggestion doesn't seem to fit with the rest of Haskell.

Conclusion

View patterns are a nice enhancement to pattern guards, increasing their compositionality and reducing the need for redundant intermediate variables. I could live without view patterns, but I don't think I should have to - the design is good, and they fit in nicely with the language. As for pattern guards, I consider them an essential part of the Haskell language that really makes a substantially difference to some pieces of code that would otherwise be rather ugly.

Edit: Fix as per Christophe's comment.

How I Use HLint

HLint is a tool for automatically suggesting improvements to your Haskell code. This post describes how I use HLint, and provides and some background on its development. Before reading this article, if you are an active Haskell programmer who has not yet tried out HLint, I suggest you perform the following steps:

cabal update && cabal install hlint
cd your-current-project
hlint . --report
# open report.html in your web browser

The original purpose of HLint was to help teach beginners. When helping with the functional programming course at York, I used to wander round the students, looking at their code, and suggesting improvements. After three years helping with the same course, I found myself regularly suggesting the same improvements. For example, the pattern if a then True else b came up a lot, which can be written more succinctly as a || b. Of course, having turned myself into a pattern recognition tool, the obvious step was to automate myself - and HLint is the result.

I am no longer at a University, and so the way I use HLint has changed. Often on the Haskell Cafe mailing list people ask for code reviews - intermediate level Haskellers trying to gain knowledge from those around them. The suggestions resulting from a code review are often split into two categories. There are small-scale suggestions about things such as using a better library function, and large-scale suggestions about what the structure of the program should be. Often it is useful to tackle the small-scale issues, tidying and polishing what is already there, before investigating any large-scale issues. Unfortunately reviewers are often short of time, so they may not get round to making large-scale suggestions. The hope is that HLint can automate much of the small-scale suggestions, allowing clever people to use their time more effectively on the more complex problems.

Another reason to use HLint is one of developer pride. Some developers do not react well to criticism, and take comments about their code in a very personal way. Worse still, if you declare that some small syntactic pattern is the "wrong way to do it", then you can inadvertently end up just point out the failings. In contrast, if HLint is run first, then the human suggestions are typically deeper, and are design trade-offs that can be debated.

HLint is not designed as a tool to fix existing code, but more as a tool to promote learning, thus pre-emptively fixing future code. I do not intend people to slavishly apply the hints given by HLint - each hint should be carefully considered. For example, the darcs project uses HLint, but has decided that they are not interested in eta reduction hints, so have used HLint's ignoring facility.

One use of HLint is to provide an easy mechanism to start participating in an open source project. One of the largest hurdles in project participation is writing your first patch. Many projects have different conventions and requirements, plus there is usually a large code base that needs to be learnt. A good first step might be to run HLint over the code. While many of the hints suggested by HLint might be design decisions, or minor issues, there are likely to be a few more unambiguous improvements. As a simple example, taking the xmonad code base and applying HLint shows that the import Data.Maybe statements in XMonad\Core.hs could be combined. This would be a perfect first patch for a budding xmonad developer.

HLint can be used in many ways, but my two golden rules for HLint usage are:

1. Do not blindly apply the output of HLint


2. Never review code that hasn't had HLint applied

Draft paper on Derive, comments wanted

It's been a long time since I last blogged (about 3 months). Since then I've had a paper on Firstify accepted in to the Haskell Symposium (I'll post the final version to my website shortly). I've also been writing a paper on Derive to go with my invited talk at Approaches and Applications of Inductive Programming (co-located with ICFP this year). I have to submit a final version by the 22nd of June (6 days time), but any comments on this draft would be gratefully received - either add them as comments to this post or send an email to ndmitchell AT gmail DOT com.

Download link: http://community.haskell.org/~ndm/temp/derive_draft.pdf

Title: Deriving a DSL from One Example

Abstract: Given an appropriate domain specific language (DSL), it is possible to describe the relationship between Haskell data types and many generic functions, typically type class instances. While describing the relationship is possible, it is not always an easy task. There is an alternative -- simply give one example output for a carefully chosen input, and have the relationship derived.

When deriving a relationship from only one example, it is important that the derived relationship is the intended one. We identify general restrictions on the DSL, and on the provided example, to ensure a level of predictability. We then apply these restrictions in practice, to derive the relationship between Haskell data types and generic functions. We have used our scheme in the Derive tool, where over 60% of type classes are derived from a single example.

Home page: http://community.haskell.org/~ndm/derive/

Darcs repo: http://community.haskell.org/~ndm/darcs/derive

The work presented in this paper will become the basis of Derive 2.0. Many thanks for any comments!

Concise Generic Queries

A few weeks ago David Miani asked how to write concise queries over a data type. The answer is certainly generic programming, a technique that I feel is underused in the Haskell community. I suggested David look at Uniplate, but he found greater success with SYB. Sean Leather gave a solution using EMGM. One of the advantages of Uniplate is conciseness, so I decided to tackle the same problem and compare.

A full description of the task, including data type definitions, is at Sean's blog. From a data type representing structured files (tables, headings, paragraphs) find a heading with a particular name then within that heading find a paragraph starting with "Description". The rest of this post contains solutions using Uniplate, EMGM (taken from Sean) and SYB (from David). The SYB solution is slightly different from the EMGM or Uniplate solutions, but they all do roughly the same generic operations. It is entirely possible that the EMGM/SYB solutions could be improved, but that is a job for other people.

Uniplate Solution

The Uniplate solution is:

projDesc :: String -> OrgFileP -> Maybe String
projDesc name p = listToMaybe [y |
 OrgHeadingP _ x ys <- universeBi p, name == x,
 ParagraphP y <- universeBi ys, "Description" `isPrefixOf` y]

The code can be read as:

• Line 1: Type signature, given a name and a file, return the paragraph if you find one


• Line 3: Find a heading with the right name


• Line 4: Find a paragraph below that heading, whose name starts with "Description"


• Line 2: Pick the paragraph

I find this code to be a clear, concise and simple description of the problem. The thought process to come up with the solution was as follows: You want to search, or perform a query. The first question is whether this is a deep (all nodes) or shallow (just the children) query - David doesn't say but the example seems to imply deep. If it's deep use universeBi. Operations are combined with a list comprehension that finds an element, check it has the necessary properties (the name), then performs more operations. The result is the code you see above.

EMGM Solution

Sean's solution can be found at his blog:

projDesc :: String -> OrgFileP -> Maybe String
projDesc name file = do
  hdg <- G.firstr (headings name file)
  para <- firstPara hdg
  if para =~ "Description" then return para else Nothing

headings :: String -> OrgFileP -> [OrgHeadingP]
headings name = filter check . G.collect
  where
    check (OrgHeadingP _ possible _) = name == possible

firstPara :: OrgHeadingP -> Maybe String
firstPara hdg = paraStr =<< G.firstr (G.collect hdg)
  where
    paraStr (ParagraphP str) = Just str
    paraStr _                = Nothing

This solution isn't bad, but is more verbose than the Uniplate solution. Perhaps it could be rewritten with list comprehensions? It seems that G.collect is similar to universeBi - although I am not sure.

SYB Solution

David's SYB solution can be found here along with another solution using different combinators.

eitherOr :: Either a b -> Either a b -> Either a b
eitherOr x@(Right _) _ = x
eitherOr  _ y  = y

getP14Desc :: OrgElement -> Either ErrString String
getP14Desc org = everything eitherOr (Left descError `mkQ` findDesc) =<<
                 everything eitherOr (Left findError `mkQ` findP14) org
    where
      findP14 h@(Heading {headingName=name})
          | name == "Project14" = Right h
      findP14 _ = Left findError

      findDesc (Paragraph {paragraphText=text})
          | text =~ "Description" = Right text
      findDesc _ = Left findError

      descError = "Couldn't find description for project"
      findError = "Couldn't find project."

Summary

The relative merits of each solution are highly subjective, but I believe the Uniplate solution is concise. The Uniplate solution is a simple translation of the problem, without any clever steps, so hopefully other users (who didn't write the library!) will be able to achieve similar results. The Uniplate solution required only one function from the Uniplate library, so has a small learning curve. Even if you don't choose Uniplate, generic programming techniques are very useful, and can make your code concise and robust.

Website move

Today I spotted that I could no longer push to my darcs repos hosted at York University. A little more checking showed that my home page had also been removed - I guess that's what happens when you are no longer a student there (although a warning email before would have been nice...). So I am pleased to announce my new website address:

http://community.haskell.org/~ndm/

Thanks to the wondrous Haskell community for providing all the resources I needed to move my website with no human intervention at haste. Expect my darcs repos to move somewhere shortly too.

I have now submitted the final bound copies of my thesis, and have uploaded a copy to my website (I had uploaded it to York, but didn't get chance to announce it!). I should say a great thank you to everyone who helped with my work/thesis, in particular Colin Runciman for supervising me for six years, and Detlef Plump and Simon Peyton Jones for examining me and really helping improve the final document with their comments.

The thesis has four content chapters, corresponding to Uniplate, Supero, Firstify and Catch. I have submitted a paper to ICFP 09 which expands/clarifies the Firstify work, which I'll upload as a draft shortly. For the other chapters, the version in the thesis is an improvement on the version in any papers I've published.

Hoogle package search

Recently on the Haskell mailing list there has been some discussions of which packages Hoogle searches by default. One person remarked that it was unfortunate that the network package isn't searched by default. There are lots of packages on Hackage, and Hoogle needs to decide how to cope with so much choice. There are a number of questions that I need to answer in Hoogle:

1. What packages should Hoogle search by default? All of hackage? The base libraries? Only the packages a user has installed? Only packages that make it in to the Haskell Platform?


2. What groups of packages should Hoogle have available? Each package individually? All packages which compile on Windows? All packages by a certain author? All packages whose minor version number is even?


3. What UI should Hoogle show? Should there be checkboxes for each os's package? Should their be a checkbox for each compiler/version? Should their be no UI but some documentation?

And these questions present a number of trade offs:

• The packages have to be divided under sensible and clear lines - I don't want to (and shouldn't) arbitrate divisions like "good" or "popular".


• The more packages you search, the less relevant the results will be.


• The fewer packages you search, the more chance that you miss something.


• The more UI that is added the more confusing things get.


• My development time for Hoogle derives Bounded, Finite and increasingly also derives Small.

Thoughts and suggestions are very welcome. I've set up a wiki page to track peoples thoughts, please make your view and arguments known: http://haskell.org/haskellwiki/Hoogle/Packages.

(As an aside, I recently found that dolphin friendly tuna is actually really harmful to the environment, far more harmful than dolphin unfriendly tuna. Read more here.)

Monomorphism and Defaulting

Haskell has some ugly corners - not many, but a few. One that many people consider exceptionally ugly is the monomorphism restriction. In this post I'm going to discuss three related issues - Constant Applicative Forms (CAFs), the monomorphism restriction and defaulting. But before we start, lets take a simple example.

Computing Pi

Haskell already provides the pi function which represents the value of pi, but lets assume it didn't. Taking a quick look at Wikipedia we can see that one way of computing Pi is the Gregory-Leibniz series. We can calculate pi as:

pi = (4/1) + (-4/3) + (4/5) + (-4/7) + (4/9) + (-4/11) ...

So let's write that as a Haskell program:

pie = sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]

Here the constant 1000000 gives the accuracy of our approach, increasing this value will give a higher precision. As it currently stands, the Haskell library says pi = 3.14159265358979 and our program says pie = 3.14159165358977. Thirteen matching digits should be suffient for most uses of pi :-)

CAFs

The disadvantage of our pie function is that (under Hugs) it takes about 4 seconds to evaluate. If we are performing lots of calculations with pi, calculating pie each time will be a serious problem. CAFs are the solution!

A CAF is a top-level constant, which doesn't take any arguments, and will be computed at most once per program execution. As a slight subtlety, if the constant has class constraints on it (i.e. is Num a => a, instead of a) then it isn't a CAF because the class constraints act like implicit arguments. Our pie function above doesn't take any arguments, so is a CAF.

Defaulting

While pie doesn't have any class constraints, the right-hand side of pie does! Take a look in Hugs:

Main> :t sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]
:: (Enum a, Fractional a) => a

Main> :t pie
:: Double

The right-hand side works for any Enum and Fractional type, for example Float, but pie is restricted to Double. The reason is the defaulting mechanism in Haskell - if a type can't be nailed down precisely, but is one of a handful of built-in classes, then it will default to a particular type. This feature is handy for working at an interactive environment, but can sometimes be a little unexpected.

Monomorphism restriction

Without defaulting the compiler would infer the type of pie as ::(Enum a, Fractional a) => a. However, such a definition would be rejected by the monomorphism restriction. The monomorphism restriction states that a function with no explicit arguments, but with class constraints, must be given a type annotation. This rejects functions like:

snub = sort . nub

To fix the problem there are two solutions:

snub i_hate_the_evil_mr = (sort . nub) i_hate_the_evil_mr

snub :: Ord a => [a] -> [a]
snub = sort . nub

For a function like pie only the second approach is applicable. The addition of dummy arguments to avoid the monomorphism restriction is sufficiently common that the HLint tool never suggests eta-reduction if the argument is named mr.

Conclusion

So why was the monomorphism restriction first introducted? For a function with no explicit arguments, the programmer might think they had written a CAF, but class constraints may substantially degrade the performance. Defaulting reduces the number of cases where the monomorphism restriction would otherwise bite, but it is still useful to be aware of the ugly corners.

There are proposals afoot to remove the monomorphism restriction and to increase the power of the default mechanism - hopefully both will be included in to Haskell'.

Small scripts with Haskell

Normally I give blog posts detailing the fun, interesting or advanced stuff I do with Haskell. But that isn't a real representation of my programming life! Most of the time I am doing small scripts that do little tasks, so I thought I'd describe one of those. This post is written as Literate Haskell, which means you can save the whole contents as a .lhs file and run it in GHCi or Hugs.

The task I had to complete was to take a directory of files, and for each file foo.txt generate the files foo_m1.txt to foo_m3.txt, where each one file is a block of lines from the original delimited by a blank line. i.e. given the file with the lines ["","1","1","","2","","3"], the numbers "1" would go in foo_m1.txt etc.

This blog post isn't how I actually wrote the original script - I didn't use literate Haskell (since I find it ugly), I didn't give explicit import lists (since they are needlessly verbose), I didn't give type signatures (but I should have) and I didn't split the IO and non-IO as well (but again, I should have). It is intended as a guide to the simple things you can easily do with Haskell. Now on to the code...

> import System.FilePath(takeExtension, dropExtension, (<.>), (</>))
> import System.Directory(getDirectoryContents)
> import Data.Char(isSpace)
> import Control.Monad

First, let's import some useful modules. To find more about a particular function just use Hoogle and search for it, but a quick summary:

takeExtension "foo.txt" = ".txt"
dropExtension "foo.txt" = "foo"
"foo" <.> "txt" = "foo.txt"
"bar" </> "foo.txt" = "bar/foo.txt"
getDirectoryContents "C:\Windows" = running "dir C:\Windows" at the command prompt
isSpace ' ' = True

Every Haskell program starts with a main function, which is an IO action. For this program, we are going to keep all the IO in main, and only use other pure functions. With most file processing applications its best to read files from one directory, and write them to another. That way, if anything goes wrong, its usually easy to recover. In this case we read from "data" and write to "res".

> main :: IO ()
> main = do
>     files <- getDirectoryContents "data"
>     forM_ files $ \file -> when (takeExtension file == ".txt") $ do
>         src <- readFile $ "data" </> file
>         forM_ (zip [1..] (splitFile src)) $ \(i,x) ->
>              writeFile ("res" </> dropExtension file ++ "_m" ++ show i <.> "txt") x

Or in some kind of pseudo-code:

main =
    set files to be the list of files in the directory "data"
    for each file in files which has the extension ".txt"
    {
        set src to be the result of reading the file
        for each numbered result of splitFile
        {
            write out the value from splitFile to the location "res/file_m#.txt"
            where # is the 1-based index into the list of results
        }
    }

We can now move on to the pure bits left over. We want a function splitFile that takes a file, and splits it in to three chunks for each of the blocks in the file. When processing text, often there will be stray blank lines, and the term "blank lines" will also apply to lines consisting only of spaces. The code is below:

> splitFile :: String -> [String]
> splitFile xs = map (tabify . unlines) [s1,s2,s3]
>     where
>         xs2 = dropWhile null $ map (dropWhile isSpace) $ lines xs
>         (s1,_:rest) = break null xs2
>         (s2,_:s3) = break null $ dropWhile null rest

And now presented more as a list of steps:

• split the text in to lines


• for each line drop all the leading spaces from it


• drop all the leading blank lines


• break on the first empty line, the bits before are chunk 1


• drop all leading blank lines for the rest


• break on the first empty line in the rest, before is chunk 2, after is chunk 3


• for each of the chunks, put the lines back together, then tabify them

The tabify requirement was added after. The person decided that all continuous runs of spaces should be converted to tabs, so the file could better be loaded in to a spread sheet. Easy enough to add, just a simple bit of recursive programming:

> tabify (' ':xs) = '\t' : tabify (dropWhile (== ' ') xs)
> tabify (x:xs) = x : tabify xs
> tabify [] = []

And again in English:

• if you encouter a space, drop it and all successive spaces, and write out a tab


• otherwise just continue onwards

Haskell is a great language for writing short scripts, and as the libraries improve it just keeps getting better.

FsCheck changes

Kurt Schelfthout has just released FsCheck 0.4, a tool similar to QuickCheck but for F#. While working at my internship for Credit Suisse I spent a little bit of time modifying FsCheck to include automatic generators (so you don't have to describe how to generate arbitrary values) and failure shrinking (so the counter-examples are smaller). Both these changes have now been incorporated in to the main FsCheck tool. It is really nice to see the work being contributed back, and that big companies are taking the time to get the necessary legal clearance etc.

I find shrinking to be a particularly potent feature. In one real-world task I struggled to debug a test failure for 8 hours, before shrinking was available. Attacking the same example with FsCheck and shrinking made the reason for the test failure immediately obvious.

mapM, mapM_ and monadic statements

In my last post on F# I mentioned that do mapM f xs; return 1 caused a space leak, and that the programmer should have written mapM_. I also proposed that monadic statements should work more like in F# where non-unit return values can't be ignored. Various people seemed to misunderstand both points, so I thought I'd elaborate.

mapM as a Space Leak

First, I should clarify what I understand as a space leak. A space leak is not a memory leak in the C sense. A space leak is when a computation retains more live memory than necessary for some period of time. One sign of a possible space leak is that lots of memory is retained by garbage collection.

Comparing mapM and mapM_ on the following program:

main = do
    mapM* putChar (replicate 10000 'a')
    return ()

The mapM_ variant has a maximum heap residency of 2Kb, while the mapM variant has 226Kb. Given an input list of length n, the residency of mapM_ is O(1), while mapM is O(n).

The exact reasons for the space leak are quite detailed, and I'm not going to attempt to cover them. My intuition is that the return list is wrapped in the IO monad, and therefore can't be deallocated until the IO action finishes. In summary, unless you are going to use the end result of a monadic map, always use mapM_.

Monadic Statements

In the above example it would be nice if the compiler had complained. You generated a value, but you didn't use it. Fortunately, it is a very easy fix - change the type of monadic bind (>>) :: Monad m => m a -> m b -> b to Monad m => m () -> m b -> m b. Now, if a monadic statement generates a value that isn't (), you get a type error. The above examples with mapM would be rejected by the type checker.

But what if we really wanted to call mapM? There are two options. The first is to bind the result, for example do _ <- mapM f xs; return 1. The second option, which F# favours, is do ignore $ mapM f xs ; return 1, with the auxiliary ignore :: Monad m => m a -> m (). I prefer the second option, as it clearly states that you want to ignore the result of a computation. You could even write a rule ignore . mapM f == mapM_ f.

F# from a Haskell perspective

I've recently started a full-time job at Standard Chartered. Before that I was doing an internship with Credit Suisse, where I spent a reasonable amount of time doing F# programming. Before I started F# I had 6 years of Haskell experience, plenty of C# experience, but little exposure to ML. I've now had 3 months to experiment with F#, using an old version (the one before the latest Community Technology Preview) and here are my impressions.

F# is a functional language from Microsoft, previously a Microsoft Research language, which is moving towards a fully supported language. F# is based on ML, and some (perhaps many) ML programs will compile with F#. At the same time, F# has complete access to the .NET framework and can interoperate with languages such as C#. F# is a hybrid language - at one extreme you can write purely functional ML, and at the other extreme you can write imperative C#, just using a different syntax. F# seems to be designed as a practical language - it isn't elegant or small, but does interoperate very nicely with every .NET feature.

The Language

The F# language is based on ML, with the addition of indentation based layout, and many of the weaknesses in F# come from ML. F# is certainly more verbose than Haskell: in some places you need an extra keyword (often a let); pattern matching is not nearly as complete; the indentation isn't as natural as Haskell. However there are some nice syntactic features in F# that are not in Haskell, including generalised list/array/sequence comprehensions and active patterns.

The type checker in F# is powerful, but unpredictable. I often get surprised by where type annotations need to go, particularly when working with .NET object types. The tuple type is treated specially in many cases, and this also leads to surprise - inserting or removing a pair of brackets can effect the type checker. Much of this complexity is necessary to manage the interaction with .NET, but it does complicate the language. Unfortunately, even with the advanced type features in F#, there are no type classes. The lack of type classes precludes the standard implementation of things such as Uniplate and QuickCheck. However, F# does have some nice reflection capabilities, and often entirely generic implementations can be given using reflection. There is certainly an interesting design trade-off between reflection based operations and type classes, something I have looked at in the past and hope to explore again in future.

F# is an impure language, which offers some practical benefits from Haskell, but also encourages a less functional style. In Haskell I sometimes work within a localised state monad - F# makes this much more natural. The impurity also allows simple interaction with .NET. Having programmed with an impure language I did find myself reaching for localised state much more often - and was occasionally tempted into using global state. In most cases, this state became problematic later. Before using F# I thought purity was a good thing, now I'm convinced that purity is a good thing but that impurity is often very useful!

Haskell could learn some things from F#. Every statement in F# must either be bound to a value or evaluate to (). In Haskell it is possible to write do mapM f xs; return 1. Any experienced Haskell programmer should spot that the mapM is a space leak (it should be mapM_), but the type system doesn't enforce it. In F# the type system does. The change in Haskell is simple, and in my opinion, desirable.

The Platform

F# is a fully fledged member of the .NET platform. You can write a class in VB.NET, write a derived class in F#, and then derive from that class in C#. All the languages can produce and consume the same libraries. This integration with .NET allows companies that already use the Microsoft tools to easily migrate - even on a function by function basis. However, the combination of both an imperative framework and a functional language at some times leads to confusing choices. All of the standard .NET libraries work with arrays, but for a functional program the list is a more natural type. F# provides both, and it was never clear which I should use where, leading to lots of conversions. The .NET libraries are very powerful, but often are overly imperative. For example, the XSD libraries (Xml Schema Description) are very imperative - you have to create objects, mutate properties, then make calls. However, in Haskell, I probably wouldn't have had any XSD support, certainly nothing as well-supported as in .NET.

The Tool Chain

The most impressive aspect of F# is the integration with the Visual Studio environment. F# contains a debugger, profiler, auto-completion, identifier lookup and many other tools. While other functional languages have some of these tools, the Visual Studio environment tends to have very refined and polished implementations. The integration with F# is sometimes a little fragile, or at least was in the version I was using, but the tools are already very powerful and are likely to continue to improve.

Overall

The F# language isn't the most beautiful language ever, but it's not bad. The integration with .NET is incredible, and while this requires compromises in the language, the benefits are considerable. I still prefer Haskell as a language, but for many users the tool chain is a more important consideration, and here F# excels.

This post was brought to you by Ctrl and v, as the computer I am currently using doesn't have a # key!

Update: I'd recommend reading Vesa Karvonen's comment below - he has additional perspectives on F# from a more ML perspective.

Enabling Reply To All in Outlook

Update: See http://neilmitchell.blogspot.com/2011/12/enabling-reply-to-all-in-outlook.html for an updated version of this functionality.

Some companies lock down the use of Outlook by disabling the Reply To All button. This makes it harder to manage email, and requires manually copying email addresses to get the same effect. But using a bit of Office VBA, it is possible to make a functioning Reply To All button. The following solution has been tested in Outlook 2003, but should work for older versions as well.

First, enable macros in Outlook. Go to Tools, Macro, Security and select Medium or Low security.

Second, add a Reply To All action. Go to Tools, Macro, Visual Basic Editor and put the following code in the text editor.

Option Explicit

Public Sub ReallyReplyAll()
Dim o As MailItem
Set o = Application.ActiveExplorer.Selection.Item(1)
o.ReplyAll.Display
End Sub

Finally, add a toolbar button to invoke the action. Go to Tools, Customise, Commands, Macros, and drag and drop the command Project1.ThisOutlookSession.ReallyReplyAll on to the toolbar. You can put this command exactly where you used to have Reply To All, and give it the same icon/name.

To test, select an email and click on the button you just added, it should do exactly what Reply To All would have done. There are some minor limitations to this method:

• 
  The button will not disable itself when it isn't applicable, i.e. when there are no emails selected. You will still be able to click on the button, but it won't do anything.
  
• 
  If you select a medium level of macro security, you will have to go through a security confirmation the first time you click Reply To All in an Outlook session.
  

If possible, try to educate the person in charge that Reply To All is perfectly good email etiquette, and that people should be trusted to use it responsibly. However, if that fails, the above method is a useful fallback.

General Updates

It's been a little while since I last posted. I've recently got back from ICFP 2008, and quite a few people asked me what I was doing now. I've also got a few comments on a a few other things. The following as a section of disjointed paragraphs on a variety of topics, both academic and personal.

Catch Talk

I gave a talk at the Haskell Symposium, about Catch. A video of the talk is now online.

Generics Talk

Alexey gave a talk about generic programming libraries at the Haskell Symposium. I was particularly interested in this talk as it is somewhat like a competition between libraries, where Uniplate is one of the competitors. One thing I noticed is that the Uniplate version of the SYB example in the talk can be written as one single lexeme, namely uniplateBi. The talk was much more about generics libraries, while Uniplate is probably more accurately described as a traversal library, so issues such as conciseness of code were left out. One thing I did disagree with from the talk was the assertion that Uniplate requires Template Haskell and Data/Typeable deriving. In reality Uniplate requires neither, but if they are present, then you have the option of using them to write even less code.

From a combination of the paper and the talk I think its fair to conclude that if Uniplate does what you want, its a pretty good choice. This fits well with the Uniplate philosophy of giving up a small amount of power, to allow a massive simplification, while still being powerful enough for most tasks.

PhD/Work

I've had my PhD viva (passed with minor corrections), and have nearly finished making the minor corrections. I'll update my website with a revised copy of the thesis shortly. I'm currently working at Credit Suisse on a three month internship. I'm not working on Haskell stuff, but instead am doing F# programming. To get a feel for some of the things that are done by Credit Suisse I recommend looking at Ganesh's ICFP talk/paper and Howard's CUFP talk. Disclaimer: Nothing I say on this blog, or anywhere public, has anything to do with Credit Suisse, but are my personal thoughts.

Personal Life

I've just moved to Cambridge, and got engaged to my girlfriend (now fiancee), Emily King. I'll be commuting to Credit Suisse for the next two months.

My Libraries/Tools

Now I'm working full-time (long hours plus a long commute), its hard for me to put the same amount of time into updating and maintaining my Haskell libraries and tools. I will still be accepting patches and answering questions, but probably not fixing too many bugs at any great speed. I'm still maintaining my bug tracker, so feel free to add bugs, fix bugs, or comment on bugs. If anyone has any particular interest in a tool, I'd consider taking on a co-maintainer to reduce some of the maintenance burden.

Well Typed

There is now a Haskell consultancy, Well Typed, comprising of Duncan Coutts and Ian Lynagh. These are two very good Haskell hackers, who are now selling their knowledge and experience. Between them, they've had substantial experience with GHC, Cabal, Hackage, ByteString, TemplateHaskell and numerous Haskell libraries. They've also taught lots of students Haskell, and helped lots of beginners on IRC and mailing lists. If I want help with Haskell, or with the general infrastructure and tools, they are usually the first people I approach. I strongly recommend that anyone needing Haskell help in a commercial environment get in contact with them - they can help you get the most out of Haskell. Disclaimer: I haven't been asked to write this section, and haven't checked with Ian/Duncan first, but I do wish them luck!