如何在Haskell中解析整数矩阵？

我对monads(以及陷阱我的上下文!)和do语句感到困惑.我真的想写这样的东西,但我知道这是错的:

firstLine <- contents.head
(m,n) <- map read (words firstLine)

因为内容不是列表 - 而是monad.

对下一步的任何帮助都会很棒.

所以我发现你可以做到:

 liftM lines . readFile

从文件中获取行列表.但是,该示例仍然仅转换整个ENTIRE文件,并且不仅使用第一行或第二行......

非常简单的版本可能是:

import Control.Monad (liftM)

-- this operates purely on list of strings
-- and also will fail horribly when passed something that doesn't 
-- match the pattern
parse_lines :: [String] -> (Int, Int, [Int], [[Int]])
parse_lines (mn_line : ks_line : matrix_lines) = (m, n, ks, matrix)
    where [m, n] = read_ints    mn_line
          ks     = read_ints    ks_line
          matrix = parse_matrix matrix_lines

-- this here is to loop through remaining lines to form a matrix
parse_matrix :: [String] -> [[Int]]
parse_matrix lines = parse_matrix' lines []
    where parse_matrix' []       acc = reverse acc
          parse_matrix' (l : ls) acc = parse_matrix' ls $ (read_ints l) : acc

-- this here is to give proper signature for read
read_ints :: String -> [Int]
read_ints = map read . words

-- this reads the file contents and lifts the result into IO
parse_file :: FilePath -> IO (Int, Int, [Int], [[Int]])
parse_file filename = do
    file_lines <- (liftM lines . readFile) filename
    return $ parse_lines file_lines

您可能希望查看Parsec以获得更好的解析,并提供更好的错误处理.

*Main Control.Monad> parse_file "test.txt"
(3,3,[1,2,3],[[1,2,3],[4,5,6],[7,8,9]])

一个易于编写的解决方案

import Control.Monad (replicateM)

-- Read space seperated words on a line from stdin
readMany :: Read a => IO [a]
readMany = fmap (map read . words) getLine

parse :: IO (Int, Int, [Int], [[Int]])
parse = do
    [m, n] <- readMany
    ks     <- readMany
    xss    <- replicateM m readMany
    return (m, n, ks, xss)

我们来试试吧:

*Main> parse
2 2
123 321
1 2
3 4
(2,2,[123,321],[[1,2],[3,4]])

虽然我提出的代码非常具有表现力.也就是说,你可以用很少的代码快速完成工作,它有一些不好的属性.虽然我认为如果你还在学习haskell并且还没有开始使用解析器库.这是要走的路.

我的解决方案的两个不良属性:

所有代码都在IO,没有什么是孤立的可测试的

错误处理非常糟糕,因为您看到模式匹配非常激进[m, n].如果我们在输入文件的第一行有3个元素会怎么样？

liftM不是魔术!您会认为将函数提升f为monad 会有一些神秘的事情,但它实际上只是定义为:

liftM f x = do
  y <- x
  return (f y)

我们实际上可以liftM用来做你想做的事,那就是:

[m,n] <- liftM (map read . words . head . lines) (readFile fname)

但你要找的是let语句:

parseLine = map read . words

parse fname = do
  (x:y:xs) <- liftM lines (readFile fname)
  let [m,n]  = parseLine x
  let ks     = parseLine y
  let matrix = map parseLine xs
  return (m,n,ks,matrix)

正如您所看到的,我们可以使用let来表示变量赋值而不是monadic计算.事实上,当我们使用符号时,让你只是让表达式:

parse fname = 
   liftM lines (readFile fname) >>= (\(x:y:xs) ->
   let [m,n]  = parseLine x
       ks     = parseLine y  
       matrix = map parseLine xs
   in return matrix )

使用解析库的解决方案

由于您可能会有许多人使用将Ints的字符串解析为[[Int]](map (map read . words) . lines $ contents)的代码进行响应,因此我将跳过它并引入其中一个解析库.如果您要为实际工作执行此任务,您可能会使用这样一个解析的库ByteString(而不是String,这意味着您的IO会将所有内容读入单个字符的链接列表中).

import System.Environment
import Control.Monad
import Data.Attoparsec.ByteString.Char8
import qualified Data.ByteString as B

首先,我导入了Attoparsec和bytestring库.您可以在hackage上查看这些库及其文档,并使用该cabal工具进行安装.

main = do
    (fname:_) <- getArgs
    putStrLn fname
    parsed <- parseX fname
    print parsed

main 基本没变.

parseX :: FilePath -> IO (Int, Int, [Int], [[Int]])
parseX fname = do
    bs <- B.readFile fname
    let res = parseOnly parseDrozzy bs
    -- We spew the error messages right here
    either (error . show) return res

parseX(从parse重命名以避免名称冲突)使用bytestring库的readfile,它以连续的字节读取打包的文件,而不是链接列表的单元格.在解析之后,如果解析器返回,则使用一点简写来返回结果,如果Right result解析器返回值,则返回错误Left someErrorMessage.

-- Helper functions, more basic than you might think, but lets ignore it    
sint = skipSpace >> int
int = liftM floor number

parseDrozzy :: Parser (Int, Int, [Int], [[Int]])
parseDrozzy = do
   m <- sint
   n <- sint
   skipSpace
   ks  <- manyTill sint endOfLine
   arr <- count m (count n sint)              
   return (m,n,ks,arr)

然后真正的工作发生在parseDrozzy.我们使用上面的帮助器获取我们的值m和n Int值.在大多数Haskell解析库中,我们必须显式处理空格 - 所以我跳过新行后n才能访问我们的ks. ks只是下一个换行符之前的所有int值.现在我们实际上可以使用先前指定的行数和列数来获取数组.

从技术上讲,最后一点arr <- count m (count n sint)不符合您的格式.它会抓住n整数,即使这意味着要进入下一行.我们可以复制Python的行为(不验证一行中的值的数量),count m (manyTill sint endOfLine)或者我们可以更明确地检查行的每一行,如果我们缺少元素,则返回错误.

从列表到矩阵

列表列表不是二维数组 - 空间和性能特征完全不同.让我们使用Data.Array.Repa(import Data.Array.Repa)将列表打包成一个真实的矩阵.这将允许我们有效地访问数组的元素以及对整个矩阵执行操作,可选地在所有可用的CPU之间分配工作.

Repa使用稍微奇怪的语法定义数组的尺寸.如果您的行和列长度在变量中m,n那么Z :. n :. m就像C声明一样int arr[m][n].对于一维示例ks,我们有:

fromList (Z :. (length ks)) ks

从改变我们类型[Int]来Array DIM1 Int.

对于二维数组,我们有:

let matrix = fromList (Z :. m :. n) (concat arr)

而从改变我们的类型[[Int]]来Array DIM2 Int.

所以你有它.使用面向生产的库将文件格式解析为高效的Haskell数据结构.