View source for Tutorials/Programming Haskell/String IO

[[Category:Tutorials]]
This is part two in a series of tutorials on programming Haskell. You
can get up to speed by reading [[Tutorials/Programming Haskell/Introduction|yesterday's introductory article]]. 

Today we'll look more into the basic tools at our disposal in the
[[Haskell]] language, in particular, operations for doing I/O and playing
with files and strings.


==Administrivia==

Before we get started, I should clarify a small point raised by 
[[Tutorials/Programming Haskell/Introduction|yesterday's article]]. 
One issue I forgot to mention was that there are slight differences
between running Haskell in GHCi, the bytecode interpreter, and compiling
it to native code with GHC.

Haskell programs are executed by evaluating the special <code>main</code> definition:

<haskell>
    import Data.List

    mylength = foldr (const (+1)) 0
    main = print (mylength "haskell")
</haskell>

To compile this to native code, we would feed the source file to the compiler:

    $ ghc A.hs
    $ ./a.out
    7

For a faster turnaround, we can run the code directly through
the bytecode interpreter, GHCi, using the <tt>runhaskell</tt> program:

    $ runhaskell A.hs
    7

GHCi, the interactive Haskell environment, is a little bit different.
As it is an interactive system, GHCi must execute your code
sequentially, as you define each line. This is different to normal
Haskell, where the order of definition is irrelevant. GHCi effectively
executes your code inside a <code>do</code>-block. Therefore you can use the
<code>do</code>-notation at the GHCi prompt to define new functions:

    $ ghci
    Prelude> :m + Data.List

    Prelude> let mylength = foldr (const (+1)) 0

    Prelude> :t mylength
    mylength :: [a] -> Integer

    Prelude> mylength "haskell"
    7

For this tutorial I will be developing code in a source file, and either
compiling it as above, or loading the source file into GHCi for testing.
To load a source file into GHCi, we do:

    $ ghci
    Prelude> :load A.hs

    *Main> :t main
    main :: IO ()

    *Main> :t mylength
    mylength :: [a] -> Integer

    *Main> mylength "foo"
    3

    *Main> main
    7

Now, let's get into the code!


==I/O==

As the [https://www.oreilly.com/library/view/programming-perl-3rd/0596000278/ch01s04.html Camel Book] says:

<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
Unless you're using artificial intelligence to model a solipsistic
philosopher, your program needs some way to communicate with the
outside world.
</div>

In yesterday's tutorial, I briefly introduced <code>readFile</code>, for reading a
string from a file on disk. Let's consider now I/O in more detail.
The most common I/O operations are defined in the [http://haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html System.IO] library.

For the most basic <tt>stdin/stdout</tt> Unix-style programs in Haskell, we can
use the <code>interact</code> function:

<haskell>
    interact    ::  (String -> String) -> IO ()
</haskell>

This <i>higher-order</i> function takes, as an argument, some function for
processing a string (of type <code>String -> String</code>). It runs this function
over the standard input stream, printing the result to standard output.
A surprisingly large number of useful programs can be written this way.
For example, we can write the <tt>cat</tt> unix program as:

<haskell>
    main = interact id
</haskell>

Yes, that's it! Let's compile and run this program:

    $ ghc -O A.hs

    $ cat A.hs | ./a.out
    main = interact id

How does this work? Firstly, <code>interact</code> is defined as:

<haskell>
    interact f = do s <- getContents
                    putStr (f s)
</haskell>

So it reads a string from standard input, and writes to standard output
the result of applying its argument function to that string.

As for <code>id</code>, it has the type:

<haskell>
    id :: a -> a
</haskell>

<code>id</code> is a function of one argument, of any type (the lowercase <code>a</code> in
the type means any type can be used in that position, i.e. it is a
polymorphic function, or a <i>generic function</i> in some
other languages). <code>id</code> takes a value of some type <code>a</code>, and returns a value of
the same type. There's only one (non-trivial) function of this type:

<haskell>
    id a = a
</haskell>

So <code>interact id</code> will print to the input string to standard output
unmodified. 

Let's now write a basic version of the <tt>wc</tt> program:

<haskell>
    main    = interact count
    count s = show (length s) ++ "\n"
</haskell>

This will print the length of the input string, that is, the number of
chars:

    $ runhaskell A.hs < A.hs
    57


==Line oriented I/O==

Only a small number of programs operate on unstructured input streams.
It is far more common to treat an input stream as a list of lines. So
let's do that. To break a string up into lines, we'll use the ...
<code>lines</code> function, defined in the [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html Data.List] library:

<haskell>
    lines :: String -> [String]
</haskell>

The type, once again, tells the story. <code>lines</code> takes a string, and
breaks it up into a list of strings, splitting on newlines.
To join a list of strings back into a single string, inserting newlines,
we'd use the ... <code>unlines</code> function:

<haskell>
    unlines :: [String] -> String
</haskell>

There are also similar functions for splitting on words, namely <code>words</code>
and <code>unwords</code>. Now, an example. To count the number of lines in a file:

<haskell>
    main = interact (count . lines)
</haskell>

We can run this as:

    $ ghc -O A.hs

    $ ./a.out < A.hs
    3

Here we reuse the 'count' function from above, by <i>composing</i> it
with the lines function. 


===On composition===

This nice code reuse via composition is achieved using the <code>(.)</code> function,
pronounced <i>"compose"</i>. Let's look at how that works. (Feel free to skip
this section, if you want to just get things done).


The <code>(.)</code> function is just a normal everyday Haskell function, defined as:

<haskell>
    (.) f g x = f (g x)
</haskell>

This looks a little like magic (or line noise), but it's pretty easy. The
<code>(.)</code> function simply takes <i>two functions</i> as arguments, along with
another value. It applies the <code>g</code> function to the value <code>x</code>, and then
applies <code>f</code> to the result, returning this final value. The functions may
be of any type. The type of <code>(.)</code> is actually:

<haskell>
    (.) :: (b -> c) -> (a -> b) -> a -> c
</haskell>

which might look a bit hairy, but it essentially specifies what types of
arguments make sense to compose. That is, only those where:

<haskell>
    f :: b -> c
    g :: a -> b
    x :: a
</haskell>

can be composed, yielding a new function of type: 

<haskell>
    (f . g) :: a -> c
</haskell>

The nice thing is that this composition makes sense (and works) <i>for all types</i> <code>a</code>, <code>b</code> and <code>c</code>.

How does this relate to code reuse? Well, since our <code>count</code> function is
<i>polymorphic</i>, it works equally well counting the length of a
string, or the length of a list of strings. Our littler <tt>wc</tt> program is
the epitome of the phrase: <i>"higher order + polymorphic =
reusable"</i>. That is, functions which take other functions as
arguments, when combined with functions that work over any type, produce
great reusable "glue". You only need vary the argument function to gain
excellent code reuse (and the strong type checking ensures you can only
reuse code in ways that work).


===More on lines===

Another little example, let's reverse each line of a file (like the unix
<tt>rev</tt> command):

<haskell>
    main = interact (unlines . map reverse . lines)
</haskell>

Which when run, reverses the input lines:

    $ ./a.out < B.hs
    rahC.ataD tropmi
    ebyaM.ataD tropmi
    tsiL.ataD tropmi

So we take the input string, split it into lines, and the loop over that
list of lines, reversing each of them, using the <code>map</code> function.
Finally, once we've reversed each line, we join them back into a single
string with <code>unlines</code>, and print it out.


The <code>map</code> function is a fundamental control structure of functional
programming, similar to the <tt>foreach</tt> keyword in a number of imperative
languages. <code>map</code> however is just a function on lists, not built-in
syntax, and has the type:

<haskell>
    map :: (a -> b) -> [a] -> [b]
</haskell>

That is, it takes some function, and a list, and applies that function
to each element of the list, returning a new list as a result. Since
loops are so common in programming, we'll be using <code>map</code> a lot.
Just for reference, <code>map</code> is implemented as:

<haskell>
    map _ []     = []
    map f (x:xs) = f x : map f xs
</haskell>


==File I/O==

Operating on <tt>stdin/stdout</tt> is good for scripts (and this is how tools
like <tt>sed</tt> or <tt>perl -p</tt> work), but for "real" programs we'll at least need
to do some file I/O. The basic operations of files are:

<haskell>
readFile  :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()
</haskell>

<code>readFile</code> takes a file name as an argument, does some I/O, and returns the
file's contents as a string. <code>writeFile</code> takes a file name, a string,
and does some I/O (writing that string to the file), before returning the
void (or unit) value, <code>()</code>.


We could implement a basic <tt>cp</tt> program on files, as:

<haskell>
    import System.Environment

    main = do
        [f,g] <- getArgs
        s     <- readFile f
        writeFile g s
</haskell>

Running this program:

    $ ghc -O A.hs

    $ ./a.out A.hs Z.hs

    $ cat Z.hs
    import System.Environment

    main = do
        [f,g] <- getArgs
        s     <- readFile f
        writeFile g s

Since we're doing I/O (the type of <code>readFile</code> and <code>writeFile</code> enforce this),
the code runs inside a <code>do</code>-block, using the <i>monadic</i> <code>IO</code> type. <i>"Using the
</i>IO<i> monad"</i> just means that we wish to use an imperative, sequential order
of evaluation. (As an aside, a wide range of other monads exist, for
programming different program evaluation strategies, such as
Prolog-style backtracking, or continuation-based evaluation. All of
imperative programming is just one subset of possible evaluation
strategies you can use in Haskell, via monads).


In <code>do</code>-notation, whenever you wish to run an action, for its side
effect, and save the result to a variable, you would write:

<haskell>
    v <- action
</haskell>

For example, to run the <code>readFile</code> action, which has the side effect of
reading a file from disk, we say:

<haskell>
    s <- readFile f
</haskell>

Finally, we can use the <code>appendFile</code> function to append to an existing
file.


==File Handles==

The most generic interface to files is provided via handles. Sometimes
we need to keep a file open, for multiple reads or writes. To do this we
use the <code>Handle</code> type, an abstraction much like the underlying system's file
handles.


To open up a file, and get its handle, we use:

<haskell>
    openFile :: FilePath -> IOMode -> IO Handle
</haskell>

So to open a file for reading only, in GHCi:

<haskell>
    Prelude System.IO> h <- openFile "A.hs" ReadMode
    {handle: A.hs}
</haskell>

Which returns a handle onto the file <tt>"A.hs"</tt>. We can read a line from this handle:

<haskell>
    Prelude System.IO> hGetLine h
    "main = do"
</haskell>

To close a handle, and flush the buffer:

<haskell>
    hClose :: Handle -> IO ()
</haskell>

Once a handle is closed, we can no longer read from it:

<haskell>
    Prelude System.IO> hClose h
    Prelude System.IO> hGetLine h
    *** Exception: A.hs: hGetLine: illegal operation (handle is closed)
</haskell>

We can also flush explicitly with:

<haskell>
    hFlush :: Handle -> IO ()
</haskell>

Other useful operations for reading from handles:

<haskell>
    hGetChar     :: Handle -> IO Char
    hGetLine     :: Handle -> IO [Char]
    hGetContents :: Handle -> IO [Char]
</haskell>

To write to handles:

<haskell>
    hPutChar    :: Handle -> Char -> IO ()
    hPutStr     :: Handle -> [Char] -> IO ()
    hPutStrLn   :: Handle -> [Char] -> IO ()
    hPrint      :: Show a => Handle -> a -> IO ()
</haskell>

Some other useful actions:

<haskell>
    hSeek     :: Handle -> SeekMode -> Integer -> IO ()
    hTell     :: Handle -> IO Integer
    hFileSize :: Handle -> IO Integer
    hIsEOF    :: Handle -> IO Bool
</haskell>


==An example: spell-checking==

Here is a small example of combining the [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Set.html Data.Set]
and <tt>List</tt> data structures from yesterday's tutorial, with more I/O
operations. We'll implement a little spell-checker, building the
dictionary in a <code>Set</code> data type. First, some libraries to import:

<haskell>
    import System.Environment
    import Control.Monad
    import Data.Set
</haskell>

And the complete program:

<haskell>
    main = do
        [s] <- getArgs
        f   <- readFile "/usr/share/dict/words"
        g   <- readFile s
        let dict = fromList (lines f)
        mapM_ (spell dict) (words g)

    spell d w = when (w `notMember` d) (putStrLn w)
</haskell>

Running this program, on its own source, and it reports the following
words are not found in the dictionary:

    $ ghc -O Spell.hs -o spell

    $ ./spell A.hs
    Data.Char
    =
    <-
    (map
    toUpper
    n)
    =
    <-
    getLine
    1


===Writing the results out===

If we wanted to write the results out to a temporary file, we can do
so. Let's import a couple of other modules:

<haskell>
    import Data.Set
    import Data.Maybe
    import Text.Printf
    import System.IO
    import System.Environment
    import System.Posix.Temp
</haskell>

Refactoring the <code>main</code> definition to separate out the reading and writing phases
into their own function, we end up with the core code:

<haskell>
    main = do
        (f, g) <- readFiles
        let dict = fromList (lines f)
            errs = mapMaybe (spell dict) (words g)
        write errs

    spell d w | w `notMember` d = Just w
              | otherwise       = Nothing
</haskell>

Where reading is now its own function:

<haskell>
    readFiles = do
        [s] <- getArgs
        f   <- readFile "/usr/share/dict/words"
        g   <- readFile s
        return (f,g)
</haskell>

And writing errors out to their own file:

<haskell>
    write errs = do
        (t,h) <- mkstemp "/tmp/spell.XXXXXX"
        mapM_ (hPutStrLn h) errs
        hClose h
        printf "%d spelling errors written to '%s'\n" (length errs) t
</haskell>

Pretty simple! Running this program:

    $ ghc --make -O Spell.hs -o myspell
    [1 of 1] Compiling Main             ( Spell.hs, Spell.o )
    Linking myspell ...

    $ ./myspell Spell.hs
    67 spelling errors written to '/tmp/spell.ia8256'


==Extension: using SMP parallelism==

Finally, just for some bonus fun ... and hold on to your hat 'cause I'm
going to go fast ... we'll add some parallelism to the mix.


Haskell was designed from the start to support easy parallelisation, and
since GHC 6.6, multithreaded code will run transparently on multicore
systems using as many cores as you specify. Let's look at how we'd
parallelise our little program to exploit multiple cores. We'll use an
explicit threading model, via [http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html Control.Concurrent]. You can also make your code implicitly
parallel, using [http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Parallel-Strategies.html Control.Parallel.Strategies],
but we'll leave that for another tutorial.


Here's the source, for you to ponder. First some imports:

<haskell>
    import Data.Set hiding (map)
    import Data.Maybe
    import Data.Char
    import Text.Printf
    import System.IO
    import System.Environment
    import Control.Concurrent
    import Control.Monad
</haskell>

The entry point, modified to break the word list into chunks, and then
dispatching a chunk to each thread:

<haskell>
    main = do
        (f, g, n) <- readFiles
        let dict = fromList (lines f)
            work = chunk n (words g)
        run n dict work

    chunk :: Int -> [a] -> [[a]]
    chunk _ [] = []
    chunk n xs = (take n xs) : (chunk n (drop n xs))
</haskell>


The <code>run</code> function sets up a channel between the main thread and all
children thread (<code>errs</code>), and prints spelling errors as they arrive on
the channel from the children. It then forks off <code>n</code> children threads on
each piece of the work list:

<haskell>
    run n dict work = do
        chan <- newChan
        errs <- getChanContents chan    -- errors returned back to main thread
        mapM_ (forkIO . thread chan dict) (zip [1..n] work)
        wait n errs 0
</haskell>


The main thread then just waits on all the threads to finish, printing
any spelling errors they pass up:

<haskell>
    wait n xs i = when (i < n) $ case xs of
        Nothing : ys -> wait n ys $! i+1
        Just s  : ys -> putStrLn s >> wait n ys i
</haskell>

Each thread spell-checks its own piece of the work list. If it finds a
spelling error, it passes the offending word back over the channel to
the main thread.

<haskell>
    thread chan dict (me, xs) = do
        mapM_ spellit xs
        writeChan chan Nothing

     where
        spellit w = when (spell dict w) $
            writeChan chan . Just $ printf "Thread %d: %-25s" (me::Int) w
</haskell>

The <code>spell</code> function is simplified a little:

<haskell>
    spell d w = w `notMember` d
</haskell>

which we could also write as:

<haskell>
    spell = flip notMember
</haskell>

We modify the <tt>readFiles</tt> phase to take an additional numeric command line
argument, specifying the number of threads to run:

<haskell>
    readFiles = do
        [s,n] <- getArgs
        f     <- readFile "/usr/share/dict/words"
        g     <- readFile s
        return (f,g, read n)
</haskell>

We compile this with the GHC SMP parallel runtime system:

    $ ghc -O --make -threaded Spell.hs -o spell

Now, we can run <tt>n</tt> worker threads (lightweight Haskell threads), mapped
onto <tt>m</tt> OS threads. Since I'm using a 4-core server, we'll play
around with 4 OS threads. First, running everything in a single thread:

    $ time ./spell test.txt 1 +RTS -N1
    ...
    Thread 1: week:
    Thread 1: IO!
    ./spell test.txt 1 +RTS -N1 99% cpu 2.533 total

Ok, now we change the command line flag to run it with 4 OS threads, to
try to utilise all 4 cores:

    $ time ./spell 4 +RTS -N4
    ...
    Thread 2: week:
    Thread 3: IO!
    ./spell test.txt 4 +RTS -N4 111% cpu 2.335 total

Ok. Good... A little bit faster, uses a little bit more cpu. It turns
out however the program is bound currently by the time spent in the main
thread building the initial dictionary. Actual searching time is only
some 10% of the running time. Nonetheless, it was fairly painless to
break up the initial simple program into a parallel version.


If the program running time was extended (as the case for a server), the
parallelism would be a win. Additionally, should we buy more cores for
the server, all we need to is change the <tt>+RTS -N</tt> argument to the
program, to start utilising these extra cores.


==Next week==

In upcoming tutorials we'll look more into implicitly parallel programs,
and the use of the new high performance <code>ByteString</code> data type for string
processing.