Using Haskeline

Earlier today I decided to unearth an old project of mine - figuring that the best way to learn two languages was to implement one in the other, I wrote a MUMPS interpreter in Haskell. I was learning MUMPS for work, and Haskell for fun.

Back when I wrote it, I used readline in the REPL part of the interpreter - during the cleanup I wanted to move away from readline as GHC doesn't ship with it any more, and sometimes it can be a pain to install on its own. So I switched to Haskeline. It doesn't ship with GHC either, but it's proven easier for me to install.

Haskeline has got a really friendly API, with all of the functions operating inside the InputT m monad transformer. "Great," I think, "I can just pile this on top of my existing monad transformers stack in the interpreter!"

All was not so simple, as InputT has it's own instance of MonadState and MonadReader which allows the user of the library to peer into the guts of the implementation. But I didn't want to monkey with my text entry, I just wanted it to work and get out of my way, and I wanted the rest of my code to use the MonadState instance further down the stack that I had already set up.

So I wrote a small wrapper for Haskeline that's more friendly to mtl-style monad transformer composition. As written, it only composes with MonadIO and MonadState, but it would be straightforward to do more.

My wrapper uses HaskelineT instead of InputT, and exposes the same core functions as Haskeline (except for withInterrupt). It doesn't do anything I couldn't do by peppering lifts all over the place, but this way feels a but cleaner to me - Haskeline keeps its workings to itself, and I don't have to think about the order of the layered monad transformers.

---

{-# LANGUAGE FlexibleInstances
           , MultiParamTypeClasses
           , UndecidableInstances
           , GeneralizedNewtypeDeriving
  #-}

import qualified System.Console.Haskeline as H
import System.Console.Haskeline.Completion
import System.Console.Haskeline.MonadException

import Control.Applicative
import Control.Monad.State

newtype HaskelineT m a = HaskelineT {unHaskeline :: H.InputT m a}
 deriving (Monad, Functor, Applicative, MonadIO, MonadException, MonadTrans, MonadHaskeline)

runHaskelineT :: MonadException m => H.Settings m -> HaskelineT m a -> m a
runHaskelineT s m = H.runInputT s (unHaskeline m)

runHaskelineTWithPrefs :: MonadException m => H.Prefs -> H.Settings m -> HaskelineT m a -> m a
runHaskelineTWithPrefs p s m = H.runInputTWithPrefs p s (unHaskeline m)

class MonadException m => MonadHaskeline m where
    getInputLine :: String -> m (Maybe String)
    getInputChar :: String -> m (Maybe Char)
    outputStr :: String -> m ()
    outputStrLn :: String -> m ()


instance MonadException m => MonadHaskeline (H.InputT m) where
    getInputLine = H.getInputLine
    getInputChar = H.getInputChar
    outputStr = H.outputStr
    outputStrLn = H.outputStrLn


instance MonadState s m => MonadState s (HaskelineT m) where
    get = lift get
    put = lift . put

instance MonadHaskeline m => MonadHaskeline (StateT s m) where
    getInputLine = lift . getInputLine
    getInputChar = lift . getInputChar
    outputStr = lift . outputStr
    outputStrLn = lift . outputStrLn

MaybeT - The CPS Version

> {-# LANGUAGE Rank2Types #-}
> import Control.Monad

I think I finally understand writing code into continuation passing style. I've understood it at an academic level for some time - but that's different from being able to write the code.

This post presents a different implementation of the Maybe monad transformer - usually presented as so:

data MaybeT m a = MaybeT {runMaybeT :: m (Maybe a)}

which can be used to add the notion of short-circuiting failure to any other monad (sortof a simpler version of ErrorT from the MTL).
I first came across MaybeT in a page on the Haskell Wiki.
This presentation of MaybeT uses the Church encoding of the data-type:

> newtype MaybeT m a = MaybeT {unMaybeT :: forall b . m b -> (a -> m b) -> m b}

Note the similarity to the Prelude function maybe. We can unwrap the transformer like so:

> runMaybeT :: Monad m => MaybeT m a -> m (Maybe a)
> runMaybeT m = unMaybeT m (return Nothing) (return . Just)

This runMaybeT should be a drop-in replacement for the old one.
The advantage here is that we can write the Monad and MonadPlus instances without calling bind or return in the underlying monad m, and without doing any case analysis on Just or Nothing values:

> instance Monad (MaybeT m) where
>     return x = MaybeT $ \_ suc -> suc a
> 
>     m >>= k = MaybeT $ \fail suc ->
>               unMaybeT m fail $ \x ->
>               unMaybeT (k x) fail suc
>
>     fail _ = mzero

> instance MonadPlus (MaybeT m) where
>     mzero = MaybeT $ \fail _ -> fail
>
>     m `mplus` n = MaybeT $ \fail suc ->
>                   unMaybeT m (unMaybeT n fail suc) suc

It's just a matter of threading the failure and success continuations to the right place at the right time.
To show that this is equivalent to the old implementation, here's a re-write of the old MaybeT data constructor from above:

> fromMaybe :: Monad m => m (Maybe a) -> MaybeT m a
> fromMaybe m = MaybeT $ \fail suc -> do
>                res <- m
>                case res of
>                  Nothing -> fail
>                  Just x -> suc x

So anything you can do with the other version, you can do with this version. And for most things it should be a drop-in replacement.

Dependencies in Hackage, revisited

In a previous post I described how to scrape the Hackage website to do reverse lookups on package dependency data for packages hosted on Hackage.

With the release of the new HTTP library (version 4000) that code doesn't work anymore. This post presents a different solution to the problem.

Instead of pulling data out of html documents, we instead load and parse the local .tar file that cabal-install uses to do its own dependency chasing.

You'll need tar and utf8-string from Hackage.

First, the necessary imports:

> import Data.Maybe
> import Data.List

> import Codec.Archive.Tar

> import Data.ByteString.Lazy (ByteString)
> import qualified Data.ByteString.Lazy as BS

> import qualified Data.ByteString.Lazy.UTF8 as UTF8

> import System.IO
> import System.Environment

> import Distribution.Text
> import Distribution.Package
> import Distribution.PackageDescription
> import Distribution.PackageDescription.Parse

And now the 'main' method.

The first argument is the name of the package you're checking dependencies for, and the second argument is the path to the Hackage index tar-file (for me this is ~/.cabal/packages/hackage.haskell.org/00-index.tar).

> main :: IO ()
> main = do
>  [target,tarball] <- getArgs
>  withFile tarball ReadMode $ \h -> do
>        contents <- BS.hGetContents h
>        let matches = matchesFromIndex contents (== target)
>        sequence_ $ map (print . disp) matches 

And then we have the function which, given the contents of the tar-file as a ByteString, returns back the list of PackageIds which depend on the indicated package.

> matchesFromIndex :: ByteString -> (String -> Bool) -> [PackageId]
> matchesFromIndex index p =

>  let tarchive = readTarArchive index
>      cabalFiles = map UTF8.toString $ findCabalEntries tarchive
>      parseResults = map parsePackageDescription cabalFiles
>      gPckgDiscs = okayOnly parseResults
>      matches = filter (match p) gPckgDiscs

>  in map packageId matches

> okayOnly :: [ParseResult a] -> [a]
> okayOnly = mapMaybe fromOkay
>  where fromOkay (ParseOk _ a) = Just a
>        fromOkay _ = Nothing

> -- Does this package have a dependency which matches our
> -- query?
> match ::  (String -> Bool) -> GenericPackageDescription -> Bool
> match p pkg = any (matchDep p) (gPckgDeps pkg)

> -- Does this dependency match our query?
> matchDep :: (String -> Bool) -> Dependency -> Bool
> matchDep p (Dependency (PackageName name) _) = p name

There's a bit of black-magic going on here - I don't entirely understand the structure of the new 'library' and 'executable' sections of the .cabal file, but I scrape everything out which has the right type.

> gPckgDeps :: GenericPackageDescription -> [Dependency]
> gPckgDeps pkg = normalDeps ++ libDeps ++ execDeps
>  where
>   normalDeps = buildDepends $ packageDescription pkg

>   libDeps = case condLibrary pkg of
>               Nothing -> []
>               Just cndTree -> depsFromCndTree exLibDeps cndTree

>   execDeps = concatMap (depsFromCndTree exExecDeps . snd)
>                        (condExecutables pkg)

>   exLibDeps = pkgconfigDepends . libBuildInfo
>   exExecDeps = pkgconfigDepends . buildInfo

> depsFromCndTree f tree =
>   let x = condTreeData tree
    
>       parts = condTreeComponents tree
>       mdlTrees = map mdl parts
>       thrdTrees = mapMaybe thrd parts

>       trees = mdlTrees ++ thrdTrees


>   in f x ++
>      condTreeConstraints tree ++
>      concatMap (depsFromCndTree f) trees

>  where mdl (_,x,_) = x
>        thrd (_,_,x) = x

And this is the bit which takes the decoded tar-file and returns back the entries which look like they could be .cabal files.

> findCabalEntries :: TarArchive -> [ByteString]
> findCabalEntries TarArchive{archiveEntries = xs} = mapMaybe go xs

>  where go :: TarEntry -> Maybe ByteString
>        go x | fileType x /= TarNormalFile = Nothing
>             | isBoringName (fileName x) = Nothing
>             | otherwise = Just $ entryData x

>        fileType = tarFileType . entryHeader
>        fileName = tarFileName . entryHeader

>        isBoringName = not . isSuffixOf ".cabal"

Not too shabby.

Haskell Snippets

I'm a huge fan of the function mapMaybe, but once I move from the 'Maybe' monad into something more complex (such as ReaderT r Maybe) things become tricky.

First, what is mapMaybe?

Its type is: (a -> Maybe b) -> [a] -> [b]

It maps the input function over the list, and drops any values which evaluate to nothing. It's like a combination of map and filter, where the input function is given the option to either transform the input or filter it out.

But then I needed more information threaded around in my functions, and the types went from a -> Maybe b to a -> ReaderT r Maybe b.

So I needed:

> mapAlt :: Alternative f => (a -> f b) -> [a] -> f [b]

It's just like mapMaybe, except it works for any Alternative functor.

The output is still in the functor f so I can have it work for effectful monads and such, but it will always return a value (even if it's the empty list).

Here's the implementation:

> mapAlt f xs = go xs
>  where go [] = pure []
>        go (y:ys) = (pure (:) <*> f y <*> go ys)
>                <|> go ys

Links:

• mapMaybe
• Alternative

Hurrah for simple, useful functions.

HTML Scraping with TagSoup

Earlier today I wanted to know the packages on Hackage which stated a dependency on Parsec, so I wrote a command-line utility to do it. This post presents the utility.

The plan is simple: grab http://hackage.haskell.org/packages/archive/pkg-list.html, extract all of the links which look like links to packages, and then for each of the package-description pages find out if the dependency list includes parsec. If it does, print the package name.

First, a few preliminaries:

> import Data.Maybe
> import Network.HTTP
> import Network.URI
> import System.Environment
> import Text.HTML.TagSoup
> import Text.Regex.Base
> import Text.Regex.Posix.String
> import Text.Regex.Posix.Wrap

You could probably use a different Regex package if you wanted to without too much trouble.

First up, a few strings broken out of the body of the program for convenience should they need changing.

> name = "hackage-dep"
> version = "0.1.0"

> baseURIString = "http://hackage.haskell.org"
> packagesURI =
>    fromJust $ parseURI $ baseURIString ++ "/packages/archive/pkg-list.html"
> basePath = "/cgi-bin/hackage-scripts/package/"

The function parseURI comes from the Network.URI module. It converts a String to the URI datatype used by the Network.* modules.

Next, I need a few functions to fetch an HTML document given a URI:

> mkSimpleGet :: URI -> Request
> mkSimpleGet uri =
>   Request uri GET [Header HdrUserAgent (name ++ " v" ++ version)] []

> simpleGet :: URI -> IO (Result Response)
> simpleGet = simpleHTTP . mkSimpleGet

> body :: Result Response -> Either String String
> body (Right (Response (2,_,_) _ _ str)) = Right str
> body (Right (Response code _ _ _)) = Left $ printCode code
> body (Left e) = Left $ show e

> printCode :: ResponseCode -> String
> printCode (a,b,c) = show a ++ show b ++ show c

> errorString :: String -> String -> String
> errorString uri err =
>   "Error getting " ++ uri ++ "\n" ++ "Error: " ++ err

The two interesting functions here are simpleGet and body: simpleGet performs an HTTP GET request with the passed-in URI, and body extracts the body from the response if it was successful.
Now we can start on the HTML manipulation.

> type HTML = String

> links :: HTML -> [Tag]
> links = filter (~== TagOpen "a" []) . parseTags

links converts an HTML document into a list of link tags, using TagSoup.

And then the function packageInfo extracts the package name from a link to that package.

> type Package = String

> packageInfo :: Tag -> Maybe Package
> packageInfo (TagOpen "a" [])      = Nothing
> packageInfo t@(TagOpen "a" attrs) =
>     case fromAttrib "href" t of
>       [] -> Nothing
>       path -> info path
> packageInfo _ = Nothing

> packageName = "^" ++ basePath ++ "(.+)$"

> info :: String -> Maybe Package
> info str =
>     case str =~ packageName of
>       (_,_,_,[]) -> Nothing
>       (_,_,_,[package]) -> Just package
>       (_::(String,String,String,[String])) -> Nothing

And once I have a list of package names, I'll want to grab the web-page describing the package:

> packageURI :: Package -> URI
> packageURI =
>   fromJust . parseURI . ((baseURIString ++ basePath) ++)

> packageGet :: Package -> IO (Result Response)
> packageGet = simpleGet . packageURI

The idea is that I can call packageGet on an extracted Package, and then I can use the previously defined body function to get the HTML out of the HTTP response.

Now, let's get on with the main function:

> main :: IO ()
> main = do
>   arg <- (do {[arg] <- getArgs; return arg})
>      `catch`
>      (\_ -> error "Requires a single command line argument")
>   res <- simpleGet packagesURI
>   case body res of
>     Left str -> putStrLn $ errorString (show packagesURI) str
>     Right html -> findDeps (=~ arg) $ filterJust $ map packageInfo $ links html

The filterJust $ map packageInfo $ links html bit extracts a list of package names from the HTML list pulled off of hackage. The function findDeps takes this list along with a passed in testing function and prints out which packages depend on the package specified at the command line. The passed-in testing function is just a regex-match based on the single command-line argument.

> filterJust :: [Maybe a] -> [a]
> filterJust xs = [x | Just x <- xs]

> findDeps :: (String -> Bool) -> [Package] -> IO ()
> findDeps p ps = mapM_ (printIfDep p) ps

> printIfDep :: (String -> Bool) -> Package -> IO ()
> printIfDep p pTest = do
>   res <- packageGet pTest
>   case body res of
>     Left e     -> putStrLn $ errorString pTest e
>     Right html ->
>         if hasDep html p
>         then putStrLn pTest
>         else return ()

The function hasDep picks the "Dependencies" field out of the passed-in HTML text, and then returns true if the passed-in test returns true on any bit of string in the dependencies field.

> hasDep :: HTML -> (String -> Bool) -> Bool
> hasDep html p =
>     let tags = parseTags html
>         depTags = takeWhile (~/= (TagClose "tr")) $
>                   drop 1 $
>                   dropWhile (~/= (TagText "Dependencies")) $
>                   tags
>         depText = filterText depTags
>
>         filterText xs = [x | TagText x <- xs] :: [String]
>     in any p depText

After saving and compiling, executing ./Main parsec will (slowly) list all of the packages on Hackage which depend on Parsec. Success!

Exercise for the reader: Implement the above functionality by grabbing the 00-index.tar.gz off of Hackage instead of scraping HTML pages. This file contains all of the .cabal files for every version of every package hosted on Hackage. For bonus points cache the index on disk between calls.

Parsec as a monad transformer

The proposed Parsec3 package for Haskell has Parsec implemented as a monad transformer, which means I can do things like:

> data MyType
>     = Foo
>     | Baz
>     | Err
>  deriving Show

> parseMyType = (string "Foo" >> return Foo)
>           <|> (string "Baz" >> return Baz)

> parseNoBaz = callCC $ \k -> do
>                result <- parseMyType
>                validateResult k result
>                return result

> validateResult k Baz = k Err
> validateResult k _ = return ()

> manyNoBaz = parseNoBaz `sepBy` space

> test p s = flip runCont id (runPT p () "test" s)

Then, if I execute test manyNoBaz "Foo Foo Baz Foo" I get the result:

[Foo,Foo,Err,Foo]

This is a contrived example, but I think it's pretty neat.

Constraint synonyms in Haskell

Hello folks, and happy new year!

Earlier today I found myself writing the same sequence of long constraints on my type-signatures over and over again in a Haskell program I was working on. The program is still in flux, so that means the constraints may still change. As all of the functions call each-other, they need to have a similar set of constraints on their type signatures.

This means as the program evolves, I'll need to make a lot of similar changes all over the source file. I'm pretty lazy, so that doesn't sound like fun to me. At first I thought I could do something like this with regular type synonyms, but that requires all functions to share their entire type, not just a set of constraints.

There are a few ways I could've solved this problem:

• Don't use type signatures

  I'm not using any fancy type-level hacks, so the compiler doesn't really need them. But I like having them to prove to myself that I really do know what my code does, and to provide better error messages.

• CPP Macros

  I haven't tried this one - I just thought of it while writing this

• Type Classes

  Which is what this post is about

Let's say I have a number of functions whose type signatures are along the lines of:

> myFunc :: (Eq b, Show b, MyClass b, MyOtherClass b) => Int -> String -> b -> b

and I don't like typing the (Eq b, Show b, MyClass b, MyOtherClass b) part over and over again. I can define a typeclass which captures all of those constraints:

> class (Eq b, Show b, MyClass b, MyOtherClass b) => MyConstraints b

along with a rule to populate the class:

> instance (Eq b, Show b, MyClass b, MyOtherClass b) => MyContraints b

I can now re-write the type-signature for myFunc as follows:

> myFunc :: MyConstraints b => Int -> String -> b -> b

This works for the following reasons:

• Memebership in the class "MyConstraints" implies membership in all of the other classes, due to the constraint on the class defintion.
• Every type which satisfies the constraints is a member of the "MyConstraints" class.

As another check, if you load the module defining myFunc into GHCi and ask for its type at the interactive prompt, it will report it as

myFunc :: (Eq b, Show b, MyClass b, MyOtherClass b) => Int -> String -> b -> b

Which is exactly what I wanted.