对不起，我的问题可能看起来微不足道的一些(我是新的)。我有一个包含如下映射的文件:
---#--###----
-#---#----##-
------------@
在这个文件中，–字符表示您可以自由地朝这个方向移动。#字符表示您不能在这个方向上再移动，您应该去其他地方。@字符表示宝藏的位置。在本例中，它位于右下角，但它可以位于地图的任何位置。所以我必须穿过这些线，看看能不能到达@。我们从左上角开始。到目前为止，我已经设法阅读了文件的内容。我想知道如何在Haskell中处理这个。在Java中使用二维数组很容易，但我如何在Haskell中解决这个问题?
例如，对于前面的示例，路径为:
+++#--###----
-#+--#----##-
--++++++++++@
+符号表示到@符号的路径。
这是我在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中有许多制作2D数组的方法，这里有一个稍微费力的将字符读取到Data中的示例。数组数组，然后用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)
并继续使用状态变化的荒谬原始的"逻辑":
-- 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
，在本例中，它给出如下输出
{-
$ 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和moveup等，但这应该给出一个想法，或一个想法。
编辑:这是一个不使用中间类型的版本，也不向状态机抛出任何IO。它应该在ghci中更可用，因此您可以更容易地将其拆分:
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
这很大程度上取决于你使用2D数组的方式。
如果您只关心顺序使用，一个简单的列表列表(基本上是[[Char]])可能就可以了。
如果你关心获得特定随机坐标的效率，我可以想象IntList IntList Char可以为你工作;它几乎就像列表的列表，但是单个单元可以更有效地更新，并且它为寻路提供了廉价的随机访问。
同样，你可以通过Monad.Control.State使用一个可变的映射，例如，通过在其中保留一个Data.Array，但是你必须将所有的逻辑提升到这个单子中(这会使传递映射的副本变得复杂，当你需要它时)。