在Haskell二维阵列处理 [英] 2 dimension array processing in haskell
问题描述
对不起，我的问题，这可能似乎微不足道的一些（我是新）。我有一个包含地图看起来像这样的文件：
Sorry for my question which might seem trivial to some (I'm new). I have a file which contains a map looking like this :
---#--###----
-#---#----##-
------------@
在这个文件中， - 字符表明您可以自由在朝着这个方向努力。在＃字符表明您不能在这个方向继续移动的，你应该去别的地方。在 @ 字符表示宝藏的位置。在这种情况下，它是在右下角，但它可能是在图的任何地方。所以，我必须去通过这些线路，看看我能@ 达到。在这里，我们开始在左上角。到目前为止，我已成功地读取文件的内容。我想知道如何在Haskell处理此。它将使用2维数组很容易在Java中，但我怎么能在Haskell appproach这个问题？
In this file, – characters indicate that you are free to move in this direction. The # character indicates that you cannot move any further in this direction and you should go somewhere else. The @ character indicates the location of the treasure. In this case, it is in the bottom right corner, but it could be anywhere in the map. So I have to go through these lines and see if I can reach the @. Here we are starting at the top left corner. So far I have managed to read the content of the file. And I'm wondering how to process this in Haskell. It will be easy in Java using a 2-dimensional array but how can I appproach this problem in Haskell?
例如，对于previous例如，路径是：
For example, for the previous example, the path is:
+++#--###----
-#+--#----##-
--++++++++++@
的 + 符号重新presents路径的@符号。
The + symbol represents the path to the @ symbol.
这个算法我要实现它在Java中：
This the algorithm I have to implement it in Java:
Dfs(i,j) {
if (arr[i][j+1] == "-" && i >=0 && i<=row.size && j>=0 && j<=column.size) {
Dfs(i,j+1)
} else if(arr[i][j+1] == "@") {
}
if (arr[i][j-1] == "-" && i >=0 && i<=row.size && j>=0 && j<=column.size) {
Dfs(i,j-1)
} else if(arr[i][j-1] == "@") {
}
if (arr[i+1][j] == "-" && i >=0 && i<=row.size && j>=0 && j<=column.size) {
Dfs(i+1,j)
} else if(arr[i+1][j] == "@") {
}
}
感谢您
推荐答案
有Haskell中制作二维数组的方法很多，这里是读取字符到Data.Array数组，然后搬东西约一个有点吃力的例子与所谓的状态单子：
There are many ways of making 2D arrays in Haskell, here is a somewhat laborious example of reading the chars into a Data.Array array, and then moving things about with the so-called state monad:
import Data.Array
import Control.Monad.State.Strict
main = do str <- getContents -- accepts string from stdin
let array = mkThingArray str -- we parse the string
limits = snd (bounds array) -- we remember (height,width)
initialState = ((0::Int,-1::Int),limits,array)
((position,(h,w),a)) <- execStateT findpath initialState
let chars = elems $ fmap toChar a
putStrLn ""
putStrLn $ splitText (w+1) chars
parseArray str = listArray ((0,0),(height-1, width-1)) total where
rawlines = lines str
ls = filter (not . null) rawlines
lens = map length ls
height = length ls
width = minimum lens
proper = map (take width) ls
total = concat proper
data Thing = Open | Closed | Home | Taken deriving (Show, Eq, Ord)
toThing c = case c of '-' -> Open; '#' -> Closed; '@' -> Home;
'+' -> Taken; _ -> error "No such Thing"
toChar c = case c of Open -> '-'; Closed -> '#';
Home -> '@'; Taken -> '+'
mkThingArray str = fmap toThing (parseArray str)
和使用状态变化的荒谬原始的逻辑继续：
And continuing with an absurdly primitive 'logic' of state change:
-- we begin with moveright, which may then pass on to movedown
-- and so on perhaps in a more sophisticated case
findpath = moveright
where
moveright = do ((n,m), (bound1,bound2), arr) <- get
if m < bound2
then case arr ! (n,m+1) of
Open -> do liftIO (putStrLn "moved right")
put ((n,m+1), (bound1,bound2), arr // [((n,m+1),Taken)])
moveright
Closed -> movedown
Home -> return ()
Taken -> movedown
else movedown
movedown = do ((n,m), (bound1,bound2), arr) <- get
if n < bound1
then case arr ! (n+1,m) of
Open -> do liftIO (putStrLn "moved down")
put ((n+1,m), (bound1,bound2), arr // [((n+1,m),Taken)])
moveright
Closed -> moveright
Home -> return ()
Taken -> moveright
else moveright
splitText n str = unlines $ split n [] str
where split n xss [] = xss
split n xss str = let (a,b) = splitAt n str
in if not (null a)
then split n (xss ++ [a]) b
else xss
，在这种情况下，快乐，给人输出这样
which, in this happy case, gives output like this
{-
$ pbpaste | ./arrayparse
moved right
moved right
moved right
moved down
moved right
moved right
moved down
moved right
moved right
moved right
moved right
moved right
moved right
moved right
+++#--###----
-#+++#----##-
----++++++++@
-}
逻辑则要更复杂，用 moveleft 和上移，等等，等等。但是这是应该给的想法，或想法。
The logic will have to be more sophisticated, with moveleft and moveup, etc., etc. but this is supposed to give the idea, or an idea.
编辑：这是不使用中间类型，并不会引发任何IO进入了状态机的版本。它应该在ghci中更可用，所以你可以分开更容易撕：
Here is a version that doesn't use an intermediate type and doesn't throw any IO into the state machine. It should be more usable in ghci, so you can tear it apart more easily:
import Data.Array
import Control.Monad.Trans.State.Strict
main = do str <- readFile "input.txt"
((pos,(h,w),endarray)) <- execStateT findpath
(mkInitialState str)
putStrLn $ prettyArray endarray
-- the following are just synonyms, nothing is happening:
type Pos = (Int, Int) -- Our positions are in 2 dimensions
type Arr = Array Pos Char -- Characters occupy these positions
type ArrState = (Pos, Pos, Arr) -- We will be tracking not just
-- an array of Chars but a
-- current position and the total size
parseArray :: String -> Arr
parseArray str = listArray ((1,1),(height, width)) (concat cropped) where
ls = filter (not . null) (lines str)
width = minimum (map length ls)
height = length ls
cropped = map (take width) ls -- the map is cropped to shortest line
prettyArray :: Arr -> String
prettyArray arr = split [] (elems arr)
where (ab,(h,w)) = bounds arr
split xss [] = unlines xss
split xss str = let (a,b) = splitAt w str
in if null a then unlines xss else split (xss ++ [a]) b
mkInitialState :: String -> ArrState
mkInitialState str = ((1::Int,0::Int), limits, array)
where array = parseArray str -- we parse the string
limits = snd (bounds array) -- we remember (height,width)
-- since we don't resize, tracking this could be avoided
makeStep :: Arr -> Pos -> Arr
makeStep arr (n, m) = arr // [((n,m),'+')] -- this is crude
moveRight, moveDown, findpath :: Monad m => StateT ArrState m ()
moveRight = do ((n,m),bounds,arr) <- get
put ((n,m+1), bounds, makeStep arr (n,m+1))
moveDown = do ((n,m),bounds,arr) <- get
put ((n+1,m), bounds, makeStep arr (n+1,m))
findpath = tryRight
where -- good luck for most paths ...
tryRight = do ((n,m), (_,bound2), arr) <- get
if m < bound2
then case arr ! (n,m+1) of
'@' -> return ()
'-' -> do moveRight
tryRight
_ -> tryDown
else tryDown
tryDown = do ((n,m), (bound1,_), arr) <- get
if n < bound1
then case arr ! (n+1,m) of
'@' -> return ()
'-' -> do moveDown
tryRight
_ -> tryRight
else tryRight
runInput :: String -> String
runInput str = prettyArray endarray
where ((position,(h,w),endarray)) = execState findpath (mkInitialState str)
-- If I wanted to include IO things in the state machine,
-- I would have to use execStateT not execState, which presupposes purity
test :: String -> IO ()
test str = putStrLn (runInput str)
t1 = unlines ["---#--###----"
, ""
, "-#---#----##-"
, ""
, "------------@"
] :: String
--
t2 = unlines ["---#--###----"
,""
,"---#-#----##-"
,""
,"------------@"
] :: String
这篇关于在Haskell二维阵列处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
