Подтвердить что ты не робот

Как разобрать матрицу целых чисел в Haskell?

Итак, я прочитал теорию, теперь пытаясь разобрать файл в Haskell - но я никуда не денусь. Это просто странно...

Вот как выглядит мой входной файл:

        m n
        k1, k2...

        a11, ...., an
        a21,....   a22
        ...
        am1...     amn

Где m, n - просто интерьеры, K = [k1, k2...] - это список целых чисел, а a11..amn - это "матрица" (список списков): A=[[a11,...a1n], ... [am1... amn]]

Вот моя быстрая версия python:

def parse(filename):
    """
    Input of the form:
        m n
        k1, k2...

        a11, ...., an
        a21,....   a22
        ...
        am1...     amn

    """

    f = open(filename)
    (m,n) = f.readline().split()
    m = int(m)
    n = int(n)

    K = [int(k) for k in f.readline().split()]

    # Matrix - list of lists
    A = []
    for i in range(m):
        row = [float(el) for el in f.readline().split()]
        A.append(row)

    return (m, n, K, A)

И вот как (не очень) далеко я попал в Haskell:

import System.Environment
import Data.List

main = do
    (fname:_) <- getArgs
    putStrLn fname --since putStrLn goes to IO ()monad we can't just apply it
    parsed <- parse fname
    putStrLn parsed

parse fname = do
    contents <- readFile fname
    -- ,,,missing stuff... ??? how can I get first "element" and match on it?

    return contents

Меня путают монады (и контекст, в который меня заталкивают!) и оператор do. Я действительно хочу написать что-то подобное, но я знаю, что это неправильно:

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

потому что содержимое не является списком, а монадой.

Любая помощь на следующем шаге будет отличной.

Итак, я просто обнаружил, что вы можете сделать:

 liftM lines . readFile

чтобы получить список строк из файла. Однако, все же этот пример только преобразует только ENTIRE файл и не использует только первую или вторую строки...

4b9b3361

ОТВЕТЫ

Ответ 1

Самая простая версия может быть:

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]])

Ответ 2

Удобное для записи решение

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 элемента в первой строке входного файла?

Ответ 3

liftM не волшебство! Вы могли бы подумать, что это делает какую-то загадочную вещь, чтобы поднять функцию f в монаду, но на самом деле она определяется как:

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

Мы могли бы использовать liftM для выполнения того, что вы хотели, а именно:

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

но то, что вы ищете, - это утверждения:

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, чтобы означать назначение переменных, а не монадическое вычисление. На самом деле пусть утверждения - это просто выражения, когда мы обесцениваем обозначение:

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

Ответ 4

Решение с использованием анализирующей библиотеки

Так как у вас, вероятно, будет множество людей, отвечающих кодом, который анализирует строки Int на [[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 (переименованный из синтаксического анализа, чтобы избежать столкновения имен) использует файл чтения библиотеки байтов, который читается в файле, упакованном в смежных байтах, а не в ячейки связанного списка. После разбора я использую небольшую стенографию, чтобы вернуть результат, если парсер вернул 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 int, даже если это означает переход к следующей строке. Мы могли бы скопировать поведение Python (не проверяя количество значений в строке) с помощью count m (manyTill sint endOfLine), или мы могли бы явно проверить для каждого конца строки и вернуть ошибку, если мы коротко на элементы.

От списков к матрице

Списки списков не являются 2-мерными массивами - характеристики пространства и производительности совершенно разные. Позвольте упаковать наш список в реальную матрицу, используя Data.Array.Repa(import Data.Array.Repa). Это позволит нам эффективно получать доступ к элементам массива, а также выполнять операции на всей матрице, опционально расширяя работу среди всех доступных ЦП.

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 с использованием производственно-ориентированных библиотек.

Ответ 5

Как насчет чего-то простого?

parse :: String -> (Int, Int, [Int], [[Int]])
parse stuff = (m, n, ks, xss)
        where (line1:line2:rest) = lines stuff
              readMany = map read . words
              (m:n:_) = readMany line1
              ks = readMany line2
              xss = take m $ map (take n . readMany) rest

main :: IO ()
main = do
        stuff <- getContents
        let (m, n, ks, xss) = parse stuff
        print m
        print n
        print ks
        print xss