Writing Dynamic Programming in Haskell
From the fact that the function is the composing unit in haskell, you can quickly guess that the most intuitive way to implement dynamic programming is through memoization. Of course you can implement through state modification if you insist, but that is just coding a C program in haskell.
The core of dynamic programming is recursion, but with the exploitation of overlapping subproblem. Such that we can add another layer of data structure to memorize the previosuly calculated subproblem results. The power of haskell lies at you can just implement the brute force recursive version, then with little modification it just provides you the semantics of dynamic programming. There exists two most used library on hackage. They are data-memocombinators, and MemoTrie. Both uses the similar internal mechanism. MemoTrie is easier to use if you don’t need to memorize your own data type, data-memocombinators satisfies your need if you really want that.
The following lists six implementations of problem31 of project euler in haskell, one uses data-memocombinators, one uses MemoTrie, another from HaskellWiki exploits lazy evaluation, one uses immutable array to implement that. The rest two are from stackoverflow provided by John Lato.
import qualified Data.MemoCombinators as Memo
coins = [1,2,5,10,20,50,100,200]
sol1 = f
where f :: Int -> Int -> Int
f = Memo.memo2 Memo.integral (Memo.arrayRange (0,7)) mf
where mf :: Int -> Int -> Int
mf n k | (k >= 8) || (n < 0) = 0
| n == 0 = 1
| otherwise = (f n (k+1)) + (f (n - coins !! k) k)
main = do
print $ sol1 200 0
./sol01 +RTS -sstderr
4,901,540 bytes allocated in the heap
220,696 bytes copied during GC
82,112 bytes maximum residency (1 sample(s))
22,864 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 9 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 6.9% (7.3% elapsed)
Alloc rate 389,289,174 bytes per MUT second
Productivity 85.8% of total user, 91.4% of total elapsed
coins = [1,2,5,10,20,50,100,200]
sol2 = mf
where memo :: (Num a, Enum a) => (a -> b) -> [b]
memo f = map f (enumFrom 0)
mf :: Int -> Int -> Int
mf = \n k -> fvalue !! n !! k
fvalue = fmap memo (memo f)
f :: Int -> Int -> Int
f n k | (k >= 8) || (n < 0) = 0
| n == 0 = 1
| otherwise = (if k < 7 then mf n (k+1) else 0) + (if n - coins!!k >= 0 then mf (n - coins !! k) k else 0)
main = do
print $ sol2 200 0
./sol02 +RTS -sstderr
334,684 bytes allocated in the heap
2,096 bytes copied during GC
43,012 bytes maximum residency (1 sample(s))
26,620 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 0 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.00s ( 0.00s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 1.9% (2.3% elapsed)
Alloc rate 57,142,564 bytes per MUT second
Productivity 80.1% of total user, 94.6% of total elapsed
coins = [1,2,5,10,20,50,100,200]
sol3 = (!!) (ways [1,2,5,10,20,50,100,200])
where ways [] = 1 : repeat 0
ways (coin:coins) = n
where n = zipWith (+) (ways coins) (replicate coin 0 ++ n)
main = do
print $ sol3 200
./sol03 +RTS -sstderr
248,052 bytes allocated in the heap
2,096 bytes copied during GC
43,012 bytes maximum residency (1 sample(s))
26,620 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 0 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.00s ( 0.00s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.00s ( 0.00s elapsed)
%GC time 3.2% (4.0% elapsed)
Alloc rate 66,041,533 bytes per MUT second
Productivity 72.3% of total user, 91.1% of total elapsed
import qualified Data.MemoTrie as MT
coins = [1,2,5,10,20,50,100,200]
sol4 = f
where f :: Int -> Int -> Int
f = MT.memo2 mf
where mf :: Int -> Int -> Int
mf n k | (k >= 8) || (n < 0) = 0
| n == 0 = 1
| otherwise = (f n (k+1)) + (f (n - coins !! k) k)
main = do
print $ sol4 200 0
./sol04 +RTS -sstderr
3,992,108 bytes allocated in the heap
874,084 bytes copied during GC
185,192 bytes maximum residency (1 sample(s))
26,680 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 7 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 22.3% (24.8% elapsed)
Alloc rate 505,650,158 bytes per MUT second
Productivity 66.4% of total user, 73.3% of total elapsed
import Data.Maybe
import qualified Data.Map as M
coins = [1,2,5,10,20,50,100,200]
sol5 = mf
where memo :: (Num a, Enum a) => (a -> b) -> [b]
memo f = map f (enumFrom 0)
gwvals = fmap memo (memo f)
gwByMap :: Int -> Int -> Int -> Int -> Int
gwByMap maxX maxY = \x y -> fromMaybe (f x y) $ M.lookup (x,y) memomap
where memomap = M.fromList $ concat [[((x',y'), z) | (y',z) <- zip [0..maxY] ys] | (x',ys) <- zip [0..maxX] gwvals]
mf :: Int -> Int -> Int
mf = gwByMap 205 8
f :: Int -> Int -> Int
f n k | (k >= 8) || (n < 0) = 0
| n == 0 = 1
| otherwise = (if k < 7 then mf n (k+1) else 0) + (if n - coins!!k >= 0 then mf (n - coins !! k) k else 0)
main = do
print $ sol5 200 0
./sol05 +RTS -sstderr
1,856,632 bytes allocated in the heap
265,496 bytes copied during GC
87,788 bytes maximum residency (1 sample(s))
22,236 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 3 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 8.0% (8.7% elapsed)
Alloc rate 197,011,035 bytes per MUT second
Productivity 82.3% of total user, 89.4% of total elapsedimport Data.Array.IArray
coins = [1,2,5,10,20,50,100,200]
sol6 = ans
where ans :: Int -> Int -> Int
ans n k = table ! (n, k)
where table :: Array (Int, Int) Int
table = listArray ((0,0), (300,7)) [f i j | i <- [0..n], j <- [0..7]]
f n k | (k >= 8) || (n < 0) = 0
| n == 0 = 1
| otherwise = (if k < 7 then table ! (n, (k+1)) else 0) + (if (n - coins!!k) >= 0 then table ! ((n - coins !! k), k) else 0)
main = do
print $ sol6 200 0
./sol06 +RTS -sstderr
280,488 bytes allocated in the heap
2,096 bytes copied during GC
43,012 bytes maximum residency (1 sample(s))
26,620 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 0 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.00s ( 0.00s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.00s elapsed)
%GC time 2.4% (2.9% elapsed)
Alloc rate 51,674,281 bytes per MUT second
Productivity 78.1% of total user, 93.7% of total elapsedOne thing to notice is these two are not equivalent.
m1 = ((filter odd [1..]) !!)
m2 n = ((filter odd [1..]) !! n)This problem is related to Eta Expansion. You could probably re-evaluate a lamda function without caution. Or just checkout the discussion on stackoverflow.
Yet Another Guide to Understand Iteratee for Haskell Programmers
The concept of iteratee is currently one of topics not much material cover it. Its rising resulted from its elegancy to overcome the disadvantage of lazy IO, to which most people blame for the lack of control on resource. Although it is generally categorized as an advanced topic, I don’t think it is too difficult to get the hang of it. It is an advanced topic because in most case lazy IO can just satisfy your needs, you only need it when you run into pretty tough/big problems.
I am not going to elaborate the design of iteratee, since there are already great introductions on the web. I will just recommend a reading priority to reduce the extra difficulties ahead. Here I list three of them from richly stressing in the context to direct implementation
- Yesod Book
- Oleg Kiselyov’s talk
- John Milllikin’s tutorial
I believe following this order can ease the loading of your brain. The introduction provided by Yesod Book adress the problem from the benefit of the inverse of control, without jamming you too much about the problems of lazy IO. About lazy IO and the spirit of iteratee, Oleg’s slide give an excellent and clear explanation. It doesn’t require you a lot of background knowlege, very easy to read. And John’s tutorial can be directly correspond to concrete package on hackage, that is enumerator. That would facilitate doing experiment by yourself.
I will illustrate an example about the usage of iteratee, with accompanying testcase demonstrating the problem of lazy IO. This example is a modification from Kazu Yamamoto’s tutorial. I replace the enumerator package with the iteratee package. And instead of finding filenames matching given pattern, this example traverse the directories and print the first line of enumerated files (in ByteString.) The design of the example is intended to exhaust the limited resource, file descriptors, of naive implementation.
Print all the first lines of files in a directory Let’s look at the naive implementation first. Since the ByteString is used in the iteratee implementation, to be parallel, it imports Data.ByteString.Lazy.Char8. It also uses readFile intentionally to be an lazy IO program. Otherwise not much to address.
import Control.Monad
import Control.Monad.IO.Class
import Control.Applicative
import System.Environment
import System.Directory
import System.FilePath
import qualified Data.List as L
import qualified Data.ByteString.Lazy.Char8 as B
getValidContents :: FilePath -> IO [String]
getValidContents path =
filter (`notElem` [".", "..", ".git", ".svn"])
<$> getDirectoryContents path
isSearchableDir :: FilePath -> IO Bool
isSearchableDir dir =
(&&) <$> doesDirectoryExist dir
<*> (searchable <$> getPermissions dir)
getRecursiveContents :: FilePath -> IO [FilePath]
getRecursiveContents dir = do
cnts <- map (dir </>) <$> getValidContents dir
cnts' <- forM cnts $ \path -> do
isDirectory <- isSearchableDir path
if isDirectory
then getRecursiveContents path
else return [path]
return . concat $ cnts'
firstLine :: FilePath -> IO B.ByteString
firstLine file = do
b <- B.readFile file
return $ head . B.lines $ b
allFirstLines :: FilePath -> IO ()
allFirstLines dir = do
filepaths <- getRecursiveContents dir
l <- mapM firstLine $ filepaths
mapM_ B.putStrLn l
main = do
dir:_ <- getArgs
allFirstLines dirNext we look at the iteratee implementation. I re-implement enumDir function from Kazy’s tutorial with iteratee package. It may be a personal taste, an implementation with enumerator would be beginner friendly than an implementation with iteratee in my opinion. I also implement an enumeratee to adapt an enumerator of filepaths to an enumerator of bytestrings: firstLineE. In firstLineE I adopt enumerator and enumeratee provided by the iteratee package to reduce the work.
import Control.Monad
import Control.Monad.IO.Class
import Control.Applicative
import System.Environment
import System.Directory
import System.FilePath
import qualified Data.List as L
import qualified Data.ByteString as B
import qualified Data.Iteratee as I
import Data.Iteratee.Iteratee
import qualified Data.Iteratee.Char as EC
import qualified Data.Iteratee.IO.Fd as EIO
import qualified Data.Iteratee.ListLike as EL
getValidContents :: FilePath -> IO [String]
getValidContents path =
filter (`notElem` [".", "..", ".git", ".svn"])
<$> getDirectoryContents path
isSearchableDir :: FilePath -> IO Bool
isSearchableDir dir =
(&&) <$> doesDirectoryExist dir
<*> (searchable <$> getPermissions dir)
getRecursiveContents :: FilePath -> IO [FilePath]
getRecursiveContents dir = do
cnts <- map (dir </>) <$> getValidContents dir
cnts' <- forM cnts $ \path -> do
isDirectory <- isSearchableDir path
if isDirectory
then getRecursiveContents path
else return [path]
return . concat $ cnts'
printI :: Iteratee [B.ByteString] IO ()
printI = do
mx <- EL.tryHead
case mx of
Nothing -> return ()
Just l -> do
liftIO . B.putStrLn $ l
printI
firstLineE :: Enumeratee [FilePath] [B.ByteString] IO ()
firstLineE = mapChunksM $ \filenames -> do
forM filenames $ \filename -> do
i <- EIO.enumFile 1024 filename $ joinI $ ((mapChunks B.pack) ><> EC.enumLinesBS) EL.head
result <- run i
return result
enumDir :: FilePath -> Enumerator [FilePath] IO b
enumDir dir iter = runIter iter idoneM onCont
where
onCont k Nothing = do
(files, dirs) <- liftIO getFilesDirs
if null dirs
then return $ k (Chunk files)
else walk dirs $ k (Chunk files)
walk dirs = foldr1 (>>>) $ map enumDir dirs
getFilesDirs = do
cnts <- map (dir </>) <$> getValidContents dir
(,) <$> filterM doesFileExist cnts
<*> filterM isSearchableDir cnts
allFirstLines :: FilePath -> IO ()
allFirstLines dir = do
i' <- enumDir dir $ joinI $ firstLineE printI
run i'
main = do
dir:_ <- getArgs
allFirstLines dirTo test the effect of different implementation, I prepare three test cases.
#!/usr/bin/bash
LOGDIR=log
mkdir -p $LOGDIR
ulimit -aS > $LOGDIR/ulimit_stat.log
if [[ ! -d test01 ]]; then
mkdir -p test01
cd test01
for f in $(seq 1 500)
do
echo $RANDOM > $f
done
cd ..
fi
./allfirstlines_naive test01/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_naive_test01.log 1>/dev/null
./allfirstlines_iteratee test01/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_iteratee_test01.log 1>/dev/null
if [[ ! -d test02 ]]; then
mkdir -p test02
cd test02
for f in $(seq 1 2048)
do
echo $RANDOM > $f
done
cd ..
fi
./allfirstlines_naive test02/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_naive_test02.log 1>/dev/null
./allfirstlines_iteratee test02/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_iteratee_test02.log 1>/dev/null
if [[ ! -d test03 ]]; then
mkdir -p test03
./gen_nuclear_test test03
fi
./allfirstlines_naive test03/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_naive_test03.log 1>/dev/null
./allfirstlines_iteratee test03/ +RTS -sstderr -RTS 2> $LOGDIR/allfirstlines_iteratee_test03.log 1>/dev/nullThe first test case is the most easy one, a directory containing 500 files, and the second one is a directory containing more than 2000 files, that would possibly exhaust file descriptors. The third one add another layer of complication, with directory hierarchy containing a total of more than 2000 files, The third one is generated with a haskell script as follows:
import Control.Monad
import System.Directory
import System.Environment
layer :: Int -> IO ()
layer depth = do
if (depth <= 0)
then do mapM_ (flip writeFile "b!") (map show [1..2])
return ()
else do createDirectory "0"
setCurrentDirectory "0"
layer $ depth-1
setCurrentDirectory ".."
createDirectory "1"
setCurrentDirectory "1"
layer $ depth-1
setCurrentDirectory ".."
main = do
(dir:_) <- getArgs
setCurrentDirectory dir
putStrLn "creating ..." >> layer 10 >> putStrLn "done!"
For convenience, I write a simple Makefile to make the test command be reduced to make test, and the clean command to make clean (Note that I use ghc 7.0.2, you have to compile with -rtsopts to enable most runtime flags.)
.PHONY: clean test
test: allfirstlines_iteratee allfirstlines_naive gen_nuclear_test
bash run_test.sh
allfirstlines_naive: allfirstlines_naive.hs
ghc --make -rtsopts -O2 $@
allfirstlines_iteratee: allfirstlines_iteratee.hs
ghc --make -rtsopts -O2 $@
gen_nuclear_test: gen_nuclear_test.hs
ghc --make -O2 $@
clean:
rm -f *.o *.hi
rm -rf test01/ test02/ test03/
And my ulimit -aS is as follows to see the allowed number of open files for a process.
core file size (blocks, -c) 0
data seg size (kbytes, -d) unlimited
scheduling priority (-e) 20
file size (blocks, -f) unlimited
pending signals (-i) 401408
max locked memory (kbytes, -l) 32
max memory size (kbytes, -m) unlimited
open files (-n) 1024
pipe size (512 bytes, -p) 8
POSIX message queues (bytes, -q) 819200
real-time priority (-r) 0
stack size (kbytes, -s) 10240
cpu time (seconds, -t) unlimited
max user processes (-u) unlimited
virtual memory (kbytes, -v) unlimited
file locks (-x) unlimitedThe naive result for test case 1. We can see it is inefficient for the garbage collection time taking 21.3% of time.
./allfirstlines_naive test01/ +RTS -sstderr
30,731,840 bytes allocated in the heap
1,160,436 bytes copied during GC
8,165,024 bytes maximum residency (4 sample(s))
2,214,040 bytes maximum slop
12 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 51 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 4 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.02s ( 0.02s elapsed)
GC time 0.01s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.02s ( 0.02s elapsed)
%GC time 21.3% (21.9% elapsed)
Alloc rate 1,656,435,077 bytes per MUT second
Productivity 74.1% of total user, 76.2% of total elapsedThe iteratee benchmark for test case 1. The garbage collection time is reduced to 6.6%. It is still high because we use naive approach to enumerate files in a specific layer of directory.
./allfirstlines_iteratee test01/ +RTS -sstderr
3,222,812 bytes allocated in the heap
268,504 bytes copied during GC
266,296 bytes maximum residency (1 sample(s))
16,348 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.02s ( 0.01s elapsed)
%GC time 6.6% (7.0% elapsed)
Alloc rate 221,758,205 bytes per MUT second
Productivity 86.3% of total user, 91.9% of total elapsedtest case 2 results for naive implementation. The resource is exhausted, as expected
./allfirstlines_naive test02/ +RTS -sstderr
allfirstlines_naive: test02/1752: openFile: resource exhausted (Too many open files)
25,549,600 bytes allocated in the heap
3,387,656 bytes copied during GC
16,887,092 bytes maximum residency (5 sample(s))
4,258,052 bytes maximum slop
22 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 5 collections, 0 parallel, 0.01s, 0.01s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.05s ( 0.05s elapsed)
GC time 0.01s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.06s ( 0.06s elapsed)
%GC time 18.5% (18.7% elapsed)
Alloc rate 548,298,210 bytes per MUT second
Productivity 79.9% of total user, 80.9% of total elapsedtest case 2 for iteratee implemetation. It completes without error, but with a high percentage of GC time. As previously stated, it is because we use a naive approach to enumerate files at a specific layer.
./allfirstlines_iteratee test02/ +RTS -sstderr
13,091,456 bytes allocated in the heap
2,215,796 bytes copied during GC
1,590,196 bytes maximum residency (2 sample(s))
38,256 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 21 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 2 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.06s ( 0.06s elapsed)
GC time 0.01s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.07s ( 0.07s elapsed)
%GC time 9.2% (9.3% elapsed)
Alloc rate 216,670,627 bytes per MUT second
Productivity 89.0% of total user, 90.3% of total elapsedtest case 3 for naive case. Again, file descriptors are exhausted.
./allfirstlines_naive test03/ +RTS -sstderr
allfirstlines_naive: test03/0/1/1/1/1/1/1/1/1/0/1: openFile: resource exhausted (Too many open files)
32,198,888 bytes allocated in the heap
6,282,568 bytes copied during GC
16,901,268 bytes maximum residency (5 sample(s))
4,255,424 bytes maximum slop
22 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 50 collections, 0 parallel, 0.01s, 0.01s elapsed
Generation 1: 5 collections, 0 parallel, 0.01s, 0.01s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.13s ( 0.13s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.15s ( 0.15s elapsed)
%GC time 11.5% (11.6% elapsed)
Alloc rate 239,243,962 bytes per MUT second
Productivity 87.8% of total user, 88.2% of total elapsed
test case 3 for iteratee case. The GC time is greatly reduced since a layer is at most 2 files in it in this test case.
./allfirstlines_iteratee test03/ +RTS -sstderr
24,048,476 bytes allocated in the heap
67,792 bytes copied during GC
22,964 bytes maximum residency (1 sample(s))
20,068 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.20s ( 0.20s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.20s ( 0.20s elapsed)
%GC time 0.4% (0.4% elapsed)
Alloc rate 122,192,573 bytes per MUT second
Productivity 99.0% of total user, 99.3% of total elapsedOn one hand, this example serves as my excercise to help me understand iteratee, on the otherhand, it addresses the problem of lazy IO with such a simple concrete case, which is not seen on the web.
I list other useful links for further info.