😊

Haskellで蟻本やるぜ2(Lake Counting)

4 min read

前回の続き。
今回からArray解禁。ループも使っちゃうぞ。蟻本の「2-1 Lake Counting」をやる。
今日のパクリもとは、ここだ。

以下がコード

-- Lake Counting (POJ No.2386)
-- https://lvs7k.github.io/posts/2018/11/pccb-easy-1/
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed (UArray)
import Data.Array.IArray
import Data.Char
import Data.STRef
import qualified Data.Set as S
import Data.Typeable

solve :: Int -> Int -> [String] -> Int
solve n m xss = runST $ do
    as <- newListArray ((1, 1), (n, m)) (concat xss) :: ST s (STUArray s (Int, Int) Char)
    refc <- newSTRef 0
    forM_ [1 .. n] $ \i -> do
        forM_ [1 .. m] $ \j -> do
            c <- readArray as (i, j)
            when (c == 'W') $ do
                dfs as (i, j)
                modifySTRef' refc (+ 1)
    readSTRef refc
    where
        dfs as (i, j) = do
            c <- readArray as (i, j)
            case c of
                '.' -> return ()
                _   -> do
                    writeArray as (i, j) '.'
                    mapM_ (dfs as) next
            where
                next = do
                    s <- [i - 1, i, i + 1]
                    t <- [j - 1, j, j + 1]
                    guard (inRange ((1, 1), (n, m)) (s, t))
                    return (s, t)

rInt :: String -> Int
rInt str = read str :: Int

main :: IO ()
main = do 
    n <- rInt <$> getLine
    m <- rInt <$> getLine
    inp <- getContents
    let garden = lines inp
    -- print (typeOf garden)
    print garden
    print $ solve n m garden

これをmain.hsで作成して、data.txtを作っておき

10
12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

実行する。

stack runghc main.hs < data.txt

だがしかし、そう簡単にはいかない。。エラーになっちゃう。

main.hs:27:9: error:
    • Non type-variable argument in the constraint: MArray a Char m
      (Use FlexibleContexts to permit this)
    • When checking the inferred type
        dfs :: forall (m :: * -> *) (a :: * -> * -> *).
               MArray a Char m =>
               a (Int, Int) Char -> (Int, Int) -> m ()
      In an equation for ‘solve’:
          solve n m xss
            = runST
                $ do as <- newListArray ((1, 1), (n, m)) (concat xss) ::
                             ST s (STUArray s (Int, Int) Char)
                     refc <- newSTRef 0
                     forM_ [1 .. n] $ \ i -> ...
                     ....
            where
                dfs as (i, j)
                  = do c <- readArray as ...
                       ....
                  where
                      next = ...
   |
27 |         dfs as (i, j) = do
   |         ^^^^^^^^^^^^^^^^^^...

ちょっと状態系モナドを調べてきます。。

solve :: Int -> Int -> [String] -> Int
solve n m xss = runST $ do
    as <- newListArray ((1, 1), (n, m)) (concat xss) :: ST s (STUArray s (Int, Int) Char)
    refc <- newSTRef 0
    forM_ [1 .. n] $ \i -> do
        forM_ [1 .. m] $ \j -> do
            c <- readArray as (i, j)
            when (c == 'W') $ do
                dfs as (i, j)
                modifySTRef' refc (+ 1)
    readSTRef refc
  where
    dfs as (i, j) = do
        c <- readArray as (i, j)
        case c of
            -- '.' -> return ()
            _   -> do
                -- writeArray as (i, j) '.'
                mapM_ (dfs as) next
      where
        next = do
            s <- [i - 1, i, i + 1]
            t <- [j - 1, j, j + 1]
            guard (inRange ((1, 1), (n, m)) (s, t))
            return (s, t)

コメントアウトしている箇所を有効にするとビルドエラーになる。型が合わない。
'.'が駄目なようだがなぜだろう。。

Discussion

ログインするとコメントできます