HaskellでArray操作

haskell

Haskell使ってはじめてArray操作したのでメモ。
STモナドをつかったのもはじめてだけども。
使い方があってるのかは保証しない。

arrayパッケージのhackageのページ
http://hackage.haskell.org/package/array-0.4.0.0

  • インターフェイスとしてはImmutablな IArrayクラス とMutableな MArrayクラスがある
  • IArrayとしては Array と アンボックスされてる UArray がある
  • MArrayとして IOArray とか STArrayとかある。それそれアンボックスされてるVersionがある。(IOUArray,STUArray)
  • MArrayとIArrayを相互変換には freeze、thaw とかがある。
  • thawとかfreezeしたときにコピーが発生してるんでないかと思う。
    • freezeしたときはコピーするんだろか。
  • アクセスする際の添字としてはIxクラスであればつかえて、初期化する際に最小値と最大値を指定する。(多次元配列とか簡単につくれる)
    • array関数とかに *1 とか渡してやれば 12x12の配列ができる。

折角なので書いたコードも添付しとく

  • 書いたコードはプログラミングコンテストチャレンジブックのLake Coutingを元にhaskellに書き換えた。
  • 数えた数を保存するのにStateモナドつかってたらうまくいかなかった。どうせSTの中なので新しいSTRefつくった。どうするのがよいのかよくわかってない。
  • solveの中で破壊的な操作があるけれでも、その変更は外に出ないの参照透明性は維持できる。と信じている。
  • whenが連続するのをなんとかする方法をしりたいけど、今回は保留。
  • STモナドはIOモナドみたいに副作用がおこせて、STをはずすこともできるが、その変わり別の制限がある程度に認識している(つまりよくわかってない)
  • 入力はIOUArrayで構築して UArray に変換しておいて、問題をとく場合はSTUArrayにして処理したという感じ。

問題の内容は

大きさがN×Mの庭があります。そこに雨が振り、水溜りができました。
水溜りは8近傍で隣接している場合につながっているとみなします。
全部でいくつの水溜りがあるでしょうか？
(8近傍とは、次のWに対する*の部分を指します)

***
*W*
***

制約 N,M <= 100

入力データは以下のように想定

  • 1行目がN
  • 2行目がM
  • それ移行が庭
10
12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
module Main where

import Control.Monad (forM_,when)
import Control.Monad.ST (ST,runST)
import Data.Array.ST (STUArray)
import Data.Array.IO (freeze,thaw,writeArray,getBounds,readArray,newArray,IOUArray)
import Data.Array.Unboxed (UArray,bounds,array)
import Data.Ix (inRange,range)
import Data.STRef (newSTRef,readSTRef,writeSTRef)

type Point = (Int,Int)
type Field = UArray Point Char
type STField s = STUArray s Point Char
type IOField = IOUArray Point Char

main = do
  n <- getInt
  m <- getInt
  let r = ((1,1),(n,m))
  field <- newArray r ' ' :: IO IOField
  forM_ [1..n] $ \x -> do
    forM_ [1..m] $ \y -> do
      c <- getChar
      writeArray field (x,y) c
    getChar
  f <- freeze field
  print . solve $ f
  where
    getInt :: IO Int
    getInt = fmap read $ getLine

dfs :: STField s -> Point -> ST s ()
dfs f p@(x,y) = do
  writeArray f p '.'
  b <- getBounds f
  forM_ r $ \p1 -> do
    when (p /= p1 && inRange b p1) $ do
      c <- readArray f p1
      when (isWater c) $ do
        dfs f p1
  where
    r = range ((x-1,y-1),(x+1,y+1))

solve :: Field -> Int
solve field = runST $ do
      f <- thaw field :: ST s (STField s)
      solve' f
        where
          solve' :: STField s -> ST s Int
          solve' f = do
            ref <- newSTRef 0
            forM_ r $ \p -> do
              c <- readArray f p
              when (isWater c) $ do
                dfs f p
                x <- readSTRef ref
                writeSTRef ref (x+1)
            readSTRef ref
          r = range $ bounds $ field

isWater :: Char -> Bool
isWater = (=='W')

-- サンプルデータ
ar :: Field
ar = array ((1,1),(2,2)) [((1,1), 'W'),((2,2), 'W')]

*1:1,1),(12,12