Parsing large matrices in Haskell

Question

I have recently started learning Haskell, I'm testing what I've learnt using the Google KickStart code challanges.

The problem I am looking at essentially asks to read square matrices from standard input and sum the elements on the diagonals parallel to the main diagonal. I have written a simple program to solve the problem, this passes the first test but not the second. The problem seems to be that the input in the second test is much larger than the first and the parsers I have written are either too slow or use too much memory.

The input is formatted as a sequence of matrices

n
a11 ... a1n
...
an1 ... ann

My first attempt using builtin function

type Matrix = [[Int]]

parseInput:: String -> [Matrix]
parseInput = parseInput' . lines
    where
        parseInput':: [String] -> [Matrix]
        parseInput' [] = []
        parseInput' (i:is) = let (m,rest) = splitAt (read i) is in
                                 (map ((map read).words) m) : (parseInput' rest)

main = do
    input <- getContents
    let result = show $ parseInput input
    putStr result

The second attempt using the parsec library

import Text.Parsec
import Text.Parsec.String (Parser)

type Row = [Int]
type Matrix = [[Int]]

matrixSize::(Integral a, Read a) => Parser a
matrixSize = do
    n <- ( many1 digit ) <* newline
    return $ read n

matrixRow:: Parser Row
matrixRow = do
    row <- (sepBy1 (many1 digit) (char ' ')) <* (newline <|> (eof >> return ' '))
    return $ map read row

parseMatrix:: Parser Matrix
parseMatrix = do
    n <-  matrixSize
    mat <- count n matrixRow
    return mat

parseInput:: Parser [Matrix]
parseInput = (many1 parseMatrix)

prepareInput:: String -> [Matrix]
prepareInput input = case parse parseInput "" input of
                       Right l -> l
                       Left _ -> []

main = do
    input <- getContents
    let result = show $ prepareInput input
    putStr result

According to Google website the second test instance contains at most 100 matrices of which 10 are of size at most 1000 with elements of size at most 10^7, the remaining matrices are smaller of size at most 100.

I have generated a random test file with 10 large matrices of size at most 1000 and it turns out to be roughly 30MB in size. Running either parser on the test file takes roughly 13s on my machine and the second uses more than 1GB of memory. Both fail the requirements for running on the server: the first exceeds 20s execution time and the second fails the memory constraint of 1GB.

Is there a better way for parsing large files? Is there any inefficiency that can be solved in my code?

Any advice will be greatly appreciated!

Parsing large matrices in Haskell

0 Answers