title: Optimising Haskell data reading from file
body: <p>I am trying to implement Kosaraju's graph algorithm, on a <a href="http://spark-public.s3.amazonaws.com/algo1/programming_prob/SCC.zip" rel="nofollow">3.5m line file</a> where each row is two (space separated) Ints representing a graph edge.  To start I need to create a summary data structure that has the node and lists of its incoming and outgoing edges.  The code below achieves that, but takes over a minute, whereas I can see from posts on the MOOC forum that people using other languages are completing in &lt;&lt;10s.  (<code>getLines</code> is taking 10s compared to under 1s in benchmarks I read about.)</p>
  
  <p>I'm new to Haskell and have implemented an accumulation method using <code>foldl'</code> (the <code>'</code> was a breakthrough in making it terminate at all), but it feels rather imperative in style, and I'm hoping that that's the reason why it is running slow.  Moreover, I'm currently planning to use a similar pattern to conduct the depth-first-search, and I fear it will all just become too slow.</p>
  
  <p>I have found this <a href="http://community.haskell.org/~ndm/downloads/slides-faster_haskell-10_aug_2007.pdf" rel="nofollow">presentation</a> and <a href="http://neilmitchell.blogspot.be/2014/01/optimising-haskell-for-tight-inner-loop.html" rel="nofollow">blog</a> that talk about these sort of issues but at too expert a level.</p>
  
  <pre><code>import System.IO
  import Control.Monad
  import Data.Map.Strict as Map
  import Data.List as L
  
  type NodeName = Int
  type Edges = [NodeName]
  type Explored = Bool
  
  data Node = Node Explored (Edges, Edges) deriving (Show)
  
  type Graph1 = Map NodeName Node
  
  getLines :: FilePath -&gt; IO [[Int]]
  getLines = liftM (fmap (fmap read . words) . lines) . readFile
  
  getLines' :: FilePath -&gt; IO [(Int,Int)]
  getLines' = liftM (fmap (tuplify2 . fmap read . words) . lines) . readFile
  
  tuplify2 :: [a] -&gt; (a,a)
  tuplify2 [x,y] = (x,y)
  
  main = do
      list &lt;- getLines "testdata.txt"  -- [String]
      --list &lt;- getLines "SCC.txt"  -- [String]   
      let
          list' = createGraph list
      return list'
  
  createGraph :: [[Int]] -&gt; Graph1
  createGraph xs = L.foldl' build Map.empty xs
      where
          build :: Graph1-&gt; [Int] -&gt; Graph1
          build = \acc (x:y:_) -&gt;
              let tmpAcc = case Map.lookup x acc of
                  Nothing -&gt; Map.insert x (Node False ([y],[])) acc
                  Just a -&gt; Map.adjust (\(Node _ (fwd, bck)) -&gt; (Node False ((y:fwd), bck))) x acc
              in case Map.lookup y tmpAcc of
                  Nothing -&gt; Map.insert y (Node False ([],[x])) tmpAcc
                  Just a -&gt; Map.adjust (\(Node _ (fwd, bck)) -&gt; (Node False (fwd, (x:bck)))) y tmpAcc
  </code></pre>