1. Sergey Astanin
  2. hs-matrix-market

Commits

Sergey Astanin  committed 8f713b6

Restructured the project. Cabalized.

  • Participants
  • Parent commits 7f1414f
  • Branches default

Comments (0)

Files changed (14)

File .hgignore

View file
+syntax: glob
+dist
+*.hi
+*.o
+*~

File LICENSE

View file
+Copyright (c)2010, Sergey Astanin
+
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above
+      copyright notice, this list of conditions and the following
+      disclaimer in the documentation and/or other materials provided
+      with the distribution.
+
+    * Neither the name of Sergey Astanin nor the names of other
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

File MatrixMarket.hs

-{-# LANGUAGE FlexibleInstances, ScopedTypeVariables #-}
-
--- | Pure and composable Matrix Market reader and writer.
-module MatrixMarket where
-
-import Data.Char (toLower)
-import Data.Complex (Complex(..))
-import Data.Maybe (listToMaybe)
-import Control.Applicative ((<$>), (<*>))
-import Control.Monad (join)
-
--- | Matrix Market format representation.
-data (MValue a) => Matrix a
-  = MM
-  { mm'data :: MatrixData a
-  , mm'field :: MField
-  , mm'symmetry :: Symmetry
-  , mm'comments :: [String]
-  } deriving (Show, Eq)
-
--- | Matrix' data block.
-data (MValue a) => MatrixData a
-                = CoordinateM { coords'm :: CM a }
-                | ArrayM { array'm :: AM a }
-  deriving (Show, Eq)
-
-mm'rows :: MValue a => Matrix a -> Int
-mm'rows m =
-    case mm'data m of
-      (CoordinateM cm) -> cm'rows cm
-      (ArrayM am) -> am'rows am
-
-mm'cols :: MValue a => Matrix a -> Int
-mm'cols m =
-    case mm'data m of
-      (CoordinateM cm) -> cm'cols cm
-      (ArrayM am) -> am'cols am
-
-mm'shape :: MValue a => Matrix a -> (Int, Int)
-mm'shape m = (mm'rows m, mm'cols m)
-
--- | Coordinate format (sparse matrix).
-data (MValue a) => CM a = CM
-  { cm'rows :: Int
-  , cm'cols :: Int
-  , cm'size :: Int
-  , cm'values :: [((Int, Int), a)]
-  } deriving (Show, Eq)
-
--- | Array format (dense matrix).
-data (MValue a) => AM a = AM
-  { am'rows :: Int
-  , am'cols :: Int
-  , am'values :: [a]
-  } deriving (Show, Eq)
-
--- | Field of the matrix.
-data MField = MInt | MReal | MComplex | MPattern deriving (Eq)
-
-instance Show MField where
-    show MInt = "integer"
-    show MReal = "real"
-    show MComplex = "complex"
-    show MPattern = "pattern"
-
-numColumns :: MField -> Int
-numColumns MInt = 1
-numColumns MReal = 1
-numColumns MComplex = 2
-numColumns MPattern = 0
-
--- | Values allowed in the Matrix Market files.
-class (Num a, Show a) => MValue a where
-    typename :: a -> String
-    readval  :: [String] -> Maybe a
-    showval  :: a -> String
-
-instance MValue Int where
-  typename _ = "integer"
-  readval [s] = maybeRead s
-  readval _   = Nothing
-  showval     = show
-
-instance MValue Double where
-  typename _ = "real"
-  readval [s] = maybeRead s
-  readval _   = Nothing
-  showval     = show
-
-instance MValue (Complex Double) where
-  typename _  = "complex"
-  readval [re,im] = (:+) <$> (maybeRead re) <*> (maybeRead im)
-  readval _       = Nothing
-  showval (re :+ im) = unwords [show re, show im]
-
-maybeRead :: (Read a) => String -> Maybe a
-maybeRead s = listToMaybe (fst <$> reads s)
-
--- | Symmetry class of the matrix.
-data Symmetry = General | Symmetric | SkewSymmetric | Hermitian
-  deriving (Show, Eq)
-
--- | Parsing errors.
-data MMError
-  = NotAMatrixMarketFormat
-  | InvalidHeader String
-  | UnknownFormat String
-  | UnexpectedField String
-  | UnknownSymmetry String
-  | NoParse
-  deriving (Show, Eq)
-
--- | Make a list of non-zero entries (without symmetric entries).
-toList :: (MValue a) => Matrix a -> [((Int, Int), a)]
-toList (MM (CoordinateM cm) _ _ _) = cm'values cm
-toList (MM (ArrayM am) _ _ _) =
-    let nrs = am'rows am
-        ncs = am'cols am
-    in  zip [ (r,c) | c<-[1..ncs], r<-[1..nrs] ] $ am'values am
-
--- | Write Matrix Market format.
-dumpMM :: MValue a => Matrix a -> String
-dumpMM (MM md fld sy coms) = unlines $ header : (map ('%':) coms) ++ body
-  where
-    header =
-        let fmt = case md of
-                    (CoordinateM _) -> "coordinate"
-                    (ArrayM _) -> "array"
-            sym = case sy of
-                      General -> "general"
-                      Symmetric -> "symmetric"
-                      SkewSymmetric -> "skew-symmetric"
-                      Hermitian -> "hermitian"
-        in  "%%MatrixMarket matrix " ++ unwords [fmt, show fld, sym]
-    body = case md of
-      (CoordinateM cm) -> dumpCM cm
-      (ArrayM am) -> dumpAM am
-    dumpCM (CM rows cols size vals) =
-        unwords [show rows, show cols, show size] :
-        map (\((i,j), v) -> unwords [show i, show j, showval v]) vals
-    dumpAM (AM rows cols vals) = unwords [show rows, show cols] : map show vals
-
--- | Use this type synonym to specify the type of 'readMM' when calling.
-type ReadMatrix a = Either MMError (Matrix a)
-
--- | Parse Matrix Market format.
-readMM :: (MValue a) => String -> ReadMatrix a
-readMM mtx
-  | mtx `startsWith` "%%MatrixMarket" = readMM' mtx
-  | otherwise = Left NotAMatrixMarketFormat
-  where
-  readMM' s = r
-    where
-    r =
-      let hdr  = safeHead $ lines s
-          (clins,lins) = span (`startsWith` "%") $ lines s
-          coms = map (drop 1) (drop 1 clins)  -- comments
-          toks = concatMap words lins
-      in  case words . map toLower $ hdr of
-          ("%%matrixmarket":"matrix":fmt:field:sym:_) ->
-            let p = lookup fmt parsers
-                aval = (undefined::Either MMError (Matrix a) -> a) r
-                fi = if field == typename aval
-                     then lookup field fields :: Maybe MField
-                     else Nothing
-                ncols = numColumns <$> fi    :: Maybe Int
-                sy = lookup sym symmetries   :: Maybe Symmetry
-                d = join $ p <*> ncols <*> (Just toks)
-                m = MM <$> d <*> fi <*> sy <*> (Just coms)
-            in  case m of
-                Just m' -> Right m'
-                Nothing -> Left $
-                  case (p,fi,sy) of
-                    (Nothing,_,_) -> UnknownFormat fmt
-                    (_,Nothing,_) -> UnexpectedField field
-                    (_,_,Nothing) -> UnknownSymmetry sym
-                    _             -> NoParse
-          _ -> Left $ InvalidHeader hdr
-  --
-  parsers = [ ("coordinate", readCoords)
-            , ("array",      readArray)]
-  fields =  [ ("real", MReal)
-            , ("integer", MInt)
-            , ("complex", MComplex)
-            , ("pattern", MPattern)]
-  symmetries = [ ("general",        General)
-               , ("symmetric",      Symmetric)
-               , ("skew-symmetric", SkewSymmetric)
-               , ("hermitian",      Hermitian)]
-
--- | Read matrix in coordinate format.
-readCoords :: forall a . MValue a => Int -> [String] -> Maybe (MatrixData a)
-readCoords n (n1:n2:n3:toks) =
-  let [nrows,ncols,nsize] = map maybeRead [n1,n2,n3]
-      pts = ngroup (2+n) toks :: [[String]]
-      vals = sequence $ map (readpt n) pts :: Maybe [((Int,Int),a)]
-      cm = CM <$> nrows <*> ncols <*> nsize <*> vals :: Maybe (CM a)
-  in  CoordinateM <$> cm
-readCoords _ _ = Nothing
-
--- | Read matrix in array format.
-readArray :: forall a . MValue a => Int -> [String] -> Maybe (MatrixData a)
-readArray n (n1:n2:toks) =
-    let nrows = maybeRead n1 :: Maybe Int
-        ncols = maybeRead n2 :: Maybe Int
-        vals = sequence $ map (readval . (:[])) toks :: Maybe [a]
-        am = AM <$> nrows <*> ncols <*> vals :: Maybe (AM a)
-    in  ArrayM <$> am
-readArray _ _ = Nothing
-
-readpt :: forall a . MValue a => Int -> [String] -> Maybe ((Int,Int),a)
-readpt n (si:sj:rest)
-    | length rest /= n = Nothing
-    | otherwise =
-        let i = maybeRead si :: Maybe Int
-            j = maybeRead sj :: Maybe Int
-            v = readval rest :: Maybe a
-            coords = (,) <$> i <*> j :: Maybe (Int,Int)
-        in  (,) <$> coords <*> v     :: Maybe ((Int,Int), a)
-
-startsWith :: (Eq a) => [a] -> [a] -> Bool
-s `startsWith` prefix = all id $ zipWith (==) s prefix
-
-ngroup :: Int -> [a] -> [[a]]
-ngroup _ [] = []
-ngroup n xs = take n xs : ngroup n (drop n xs)
-
-safeHead :: [[a]] -> [a]
-safeHead [] = []
-safeHead (x:_) = x
-

File Setup.hs

View file
+import Distribution.Simple
+main = defaultMain

File array-real.mtx

-%%MatrixMarket matrix array real general
-% A 4x3 dense matrix
-4 3
-1.0
-2.0
-3.0
-4.0
-5.0
-6.0
-7.0
-8.0
-9.0
-10.0
-11.0
-12.0

File coord-complex.mtx

-%%MatrixMarket matrix coordinate complex hermitian
-5 5 7
-1 1 1.0 0
-2 2 10.5 0
-4 2 250.5 22.22
-3 3 1.5e-2 0
-4 4 -2.8e2 0
-5 5 12. 0
-5 4 0 33.32

File coord-real-freeformat.mtx

-%%MatrixMarket  MATRIX       Coordinate    Real General
-% ---------------------------------------------------------------
-% Same matrix as in Example 1
-% ---------------------------------------------------------------
-%
-% See http://math.nist.gov/MartrixMarket for more information.
-
-   5  5        8
-
-1 1  1.0
-2 2      10.5
-3 3           1.5e-2
-4 4                   -2.8E2
-5 5                            12.
-     1     4      6
-     4     2      250.5
-     4     5      33.32

File coord-real.mtx

-%%MatrixMarket matrix coordinate real general
-% A 5x5 sparse matrix with 8 nonzeros
-5 5 8
-1 1    1.0
-2 2   10.5
-4 2  250.5
-3 3    0.015
-1 4    6.0
-4 4 -280.0
-4 5   33.32
-5 5   12.0

File examples/array-real.mtx

View file
+%%MatrixMarket matrix array real general
+% A 4x3 dense matrix
+4 3
+1.0
+2.0
+3.0
+4.0
+5.0
+6.0
+7.0
+8.0
+9.0
+10.0
+11.0
+12.0

File examples/coord-complex.mtx

View file
+%%MatrixMarket matrix coordinate complex hermitian
+5 5 7
+1 1 1.0 0
+2 2 10.5 0
+4 2 250.5 22.22
+3 3 1.5e-2 0
+4 4 -2.8e2 0
+5 5 12. 0
+5 4 0 33.32

File examples/coord-real-freeformat.mtx

View file
+%%MatrixMarket  MATRIX       Coordinate    Real General
+% ---------------------------------------------------------------
+% Same matrix as in Example 1
+% ---------------------------------------------------------------
+%
+% See http://math.nist.gov/MartrixMarket for more information.
+
+   5  5        8
+
+1 1  1.0
+2 2      10.5
+3 3           1.5e-2
+4 4                   -2.8E2
+5 5                            12.
+     1     4      6
+     4     2      250.5
+     4     5      33.32

File examples/coord-real.mtx

View file
+%%MatrixMarket matrix coordinate real general
+% A 5x5 sparse matrix with 8 nonzeros
+5 5 8
+1 1    1.0
+2 2   10.5
+4 2  250.5
+3 3    0.015
+1 4    6.0
+4 4 -280.0
+4 5   33.32
+5 5   12.0

File matrix-market-pure.cabal

View file
+-- matrix-market-pure.cabal auto-generated by cabal init. For
+-- additional options, see
+-- http://www.haskell.org/cabal/release/cabal-latest/doc/users-guide/authors.html#pkg-descr.
+-- The name of the package.
+Name:                matrix-market-pure
+
+-- The package version. See the Haskell package versioning policy
+-- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for
+-- standards guiding when and how versions should be incremented.
+Version:             0.1
+
+-- A short (one-line) description of the package.
+Synopsis:            Pure and composable reader and writer of the Matrix Market format.
+
+-- A longer description of the package.
+-- Description:         
+
+-- URL for the project homepage or repository.
+Homepage:            http://bitbucket.org/jetxee/hs-matrix-market
+
+-- The license under which the package is released.
+License:             BSD3
+
+-- The file containing the license text.
+License-file:        LICENSE
+
+-- The package author(s).
+Author:              Sergey Astanin
+
+-- An email address to which users can send suggestions, bug reports,
+-- and patches.
+Maintainer:          s.astanin@gmail.com
+
+-- A copyright notice.
+-- Copyright:           
+
+Category:            Math
+
+Build-type:          Simple
+
+-- Extra files to be distributed with the package, such as examples or
+-- a README.
+-- Extra-source-files:  
+
+-- Constraint on the version of Cabal needed to build this package.
+Cabal-version:       >=1.2
+
+Library
+  -- Modules exported by the library.
+  Exposed-modules:
+     Data.MatrixMarket
+  
+  Hs-source-dirs:
+     src
+
+  -- Packages needed in order to build this package.
+  Build-depends:       
+     base >= 3 && < 5
+
+  -- Modules not exported by this package.
+  -- Other-modules:       
+  
+  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.
+  -- Build-tools:         
+  

File src/Data/MatrixMarket.hs

View file
+{-# LANGUAGE FlexibleInstances, ScopedTypeVariables #-}
+
+-- | Pure and composable Matrix Market reader and writer.
+--
+-- Usage example:
+--
+-- @
+-- rm <- 'readMM' \`liftM\` readFile \"my-real-matrix.mtx\" :: IO ('ReadMatrix' Double)
+-- case rm of
+--   Right m -> -- Do something with the matrix m
+--   Left err -> -- Report error
+-- @
+module Data.MatrixMarket
+  ( -- * Data types
+    Matrix(..)
+  , MatrixData(..)
+  , MValue(..)
+  , MField(..)
+  , Symmetry(..)
+  , CM(..)
+  , AM(..)
+  , ReadError(..)
+  , ReadMatrix
+    -- * Read and write Matrix Market
+  , readMM
+  , dumpMM
+    -- * Utility functions
+  , mm'rows, mm'cols, mm'shape
+  , toList
+  )
+  where
+
+import Data.Char (toLower)
+import Data.Complex (Complex(..))
+import Data.Maybe (listToMaybe)
+import Control.Applicative ((<$>), (<*>))
+import Control.Monad (join)
+
+-- | Matrix Market format representation.
+data (MValue a) => Matrix a
+  = MM
+  { mm'data :: MatrixData a
+  , mm'field :: MField
+  , mm'symmetry :: Symmetry
+  , mm'comments :: [String]
+  } deriving (Show, Eq)
+
+-- | Matrix' data block.
+data (MValue a) => MatrixData a
+                = CoordinateM { coords'm :: CM a }
+                | ArrayM { array'm :: AM a }
+  deriving (Show, Eq)
+
+-- | Number of rows in the matrix.
+mm'rows :: MValue a => Matrix a -> Int
+mm'rows m =
+    case mm'data m of
+      (CoordinateM cm) -> cm'rows cm
+      (ArrayM am) -> am'rows am
+
+-- | Number of columns in the matrix.
+mm'cols :: MValue a => Matrix a -> Int
+mm'cols m =
+    case mm'data m of
+      (CoordinateM cm) -> cm'cols cm
+      (ArrayM am) -> am'cols am
+
+-- | Dimensions of the matrix.
+mm'shape :: MValue a => Matrix a -> (Int, Int)
+mm'shape m = (mm'rows m, mm'cols m)
+
+-- | Coordinate format (sparse matrix).
+data (MValue a) => CM a = CM
+  { cm'rows :: Int
+  , cm'cols :: Int
+  , cm'size :: Int
+  , cm'values :: [((Int, Int), a)]
+  } deriving (Show, Eq)
+
+-- | Array format (dense matrix).
+data (MValue a) => AM a = AM
+  { am'rows :: Int
+  , am'cols :: Int
+  , am'values :: [a]
+  } deriving (Show, Eq)
+
+-- | Field of the matrix.
+data MField = MInt | MReal | MComplex | MPattern deriving (Eq)
+
+instance Show MField where
+    show MInt = "integer"
+    show MReal = "real"
+    show MComplex = "complex"
+    show MPattern = "pattern"
+
+numColumns :: MField -> Int
+numColumns MInt = 1
+numColumns MReal = 1
+numColumns MComplex = 2
+numColumns MPattern = 0
+
+-- | Values allowed in the Matrix Market files.
+class (Num a, Show a) => MValue a where
+    typename :: a -> String
+    readval  :: [String] -> Maybe a
+    showval  :: a -> String
+
+instance MValue Int where
+  typename _ = "integer"
+  readval [s] = maybeRead s
+  readval _   = Nothing
+  showval     = show
+
+instance MValue Double where
+  typename _ = "real"
+  readval [s] = maybeRead s
+  readval _   = Nothing
+  showval     = show
+
+instance MValue (Complex Double) where
+  typename _  = "complex"
+  readval [re,im] = (:+) <$> (maybeRead re) <*> (maybeRead im)
+  readval _       = Nothing
+  showval (re :+ im) = unwords [show re, show im]
+
+maybeRead :: (Read a) => String -> Maybe a
+maybeRead s = listToMaybe (fst <$> reads s)
+
+-- | Symmetry class of the matrix.
+data Symmetry = General | Symmetric | SkewSymmetric | Hermitian
+  deriving (Show, Eq)
+
+-- | Parsing errors.
+data ReadError
+  = NotAMatrixMarketFormat
+  | InvalidHeader String
+  | UnknownFormat String
+  | UnexpectedField String
+  | UnknownSymmetry String
+  | NoParse
+  deriving (Show, Eq)
+
+-- | Make a list of non-zero entries (without symmetric entries).
+toList :: (MValue a) => Matrix a -> [((Int, Int), a)]
+toList (MM (CoordinateM cm) _ _ _) = cm'values cm
+toList (MM (ArrayM am) _ _ _) =
+    let nrs = am'rows am
+        ncs = am'cols am
+    in  zip [ (r,c) | c<-[1..ncs], r<-[1..nrs] ] $ am'values am
+
+-- | Write Matrix Market format.
+dumpMM :: MValue a => Matrix a -> String
+dumpMM (MM md fld sy coms) = unlines $ header : (map ('%':) coms) ++ body
+  where
+    header =
+        let fmt = case md of
+                    (CoordinateM _) -> "coordinate"
+                    (ArrayM _) -> "array"
+            sym = case sy of
+                      General -> "general"
+                      Symmetric -> "symmetric"
+                      SkewSymmetric -> "skew-symmetric"
+                      Hermitian -> "hermitian"
+        in  "%%MatrixMarket matrix " ++ unwords [fmt, show fld, sym]
+    body = case md of
+      (CoordinateM cm) -> dumpCM cm
+      (ArrayM am) -> dumpAM am
+    dumpCM (CM rows cols size vals) =
+        unwords [show rows, show cols, show size] :
+        map (\((i,j), v) -> unwords [show i, show j, showval v]) vals
+    dumpAM (AM rows cols vals) = unwords [show rows, show cols] : map show vals
+
+-- | Use this type synonym to specify the type of 'readMM' when calling.
+type ReadMatrix a = Either ReadError (Matrix a)
+
+-- | Parse Matrix Market format.
+readMM :: (MValue a) => String -> ReadMatrix a
+readMM mtx
+  | mtx `startsWith` "%%MatrixMarket" = readMM' mtx
+  | otherwise = Left NotAMatrixMarketFormat
+  where
+  readMM' s = r
+    where
+    r =
+      let hdr  = safeHead $ lines s
+          (clins,lins) = span (`startsWith` "%") $ lines s
+          coms = map (drop 1) (drop 1 clins)  -- comments
+          toks = concatMap words lins
+      in  case words . map toLower $ hdr of
+          ("%%matrixmarket":"matrix":fmt:field:sym:_) ->
+            let p = lookup fmt parsers
+                aval = (undefined::Either ReadError (Matrix a) -> a) r
+                fi = if field == typename aval
+                     then lookup field fields :: Maybe MField
+                     else Nothing
+                ncols = numColumns <$> fi    :: Maybe Int
+                sy = lookup sym symmetries   :: Maybe Symmetry
+                d = join $ p <*> ncols <*> (Just toks)
+                m = MM <$> d <*> fi <*> sy <*> (Just coms)
+            in  case m of
+                Just m' -> Right m'
+                Nothing -> Left $
+                  case (p,fi,sy) of
+                    (Nothing,_,_) -> UnknownFormat fmt
+                    (_,Nothing,_) -> UnexpectedField field
+                    (_,_,Nothing) -> UnknownSymmetry sym
+                    _             -> NoParse
+          _ -> Left $ InvalidHeader hdr
+  --
+  parsers = [ ("coordinate", readCoords)
+            , ("array",      readArray)]
+  fields =  [ ("real", MReal)
+            , ("integer", MInt)
+            , ("complex", MComplex)
+            , ("pattern", MPattern)]
+  symmetries = [ ("general",        General)
+               , ("symmetric",      Symmetric)
+               , ("skew-symmetric", SkewSymmetric)
+               , ("hermitian",      Hermitian)]
+
+-- | Read matrix in coordinate format.
+readCoords :: forall a . MValue a => Int -> [String] -> Maybe (MatrixData a)
+readCoords n (n1:n2:n3:toks) =
+  let [nrows,ncols,nsize] = map maybeRead [n1,n2,n3]
+      pts = ngroup (2+n) toks :: [[String]]
+      vals = sequence $ map (readpt n) pts :: Maybe [((Int,Int),a)]
+      cm = CM <$> nrows <*> ncols <*> nsize <*> vals :: Maybe (CM a)
+  in  CoordinateM <$> cm
+readCoords _ _ = Nothing
+
+-- | Read matrix in array format.
+readArray :: forall a . MValue a => Int -> [String] -> Maybe (MatrixData a)
+readArray n (n1:n2:toks) =
+    let nrows = maybeRead n1 :: Maybe Int
+        ncols = maybeRead n2 :: Maybe Int
+        vals = sequence $ map (readval . (:[])) toks :: Maybe [a]
+        am = AM <$> nrows <*> ncols <*> vals :: Maybe (AM a)
+    in  ArrayM <$> am
+readArray _ _ = Nothing
+
+readpt :: forall a . MValue a => Int -> [String] -> Maybe ((Int,Int),a)
+readpt n (si:sj:rest)
+    | length rest /= n = Nothing
+    | otherwise =
+        let i = maybeRead si :: Maybe Int
+            j = maybeRead sj :: Maybe Int
+            v = readval rest :: Maybe a
+            coords = (,) <$> i <*> j :: Maybe (Int,Int)
+        in  (,) <$> coords <*> v     :: Maybe ((Int,Int), a)
+
+startsWith :: (Eq a) => [a] -> [a] -> Bool
+s `startsWith` prefix = all id $ zipWith (==) s prefix
+
+ngroup :: Int -> [a] -> [[a]]
+ngroup _ [] = []
+ngroup n xs = take n xs : ngroup n (drop n xs)
+
+safeHead :: [[a]] -> [a]
+safeHead [] = []
+safeHead (x:_) = x
+