Haskell中的二维数组处理

Question

Haskell中的二维数组处理

5

很抱歉我的问题可能对一些人来说看起来微不足道（我是新手）。我有一个文件，其中包含一个看起来像这样的地图:

---#--###----

-#---#----##-

------------@

在这个文件中，–字符表示你可以朝这个方向移动。 #字符表示你不能朝这个方向继续移动，你应该去其他地方。 @字符表示宝藏的位置。在这种情况下，它位于右下角，但可能在地图的任何地方。所以我必须浏览这些行，看看是否能到达@。我们从左上角开始。到目前为止，我已经成功读取了文件内容。我想知道如何在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] == "@") {

  }
}

谢谢你

。

- user3841581

2

不太清楚你的问题是什么。在Haskell中，您可以使用[[Char]]或一些嵌套的Array或Vector类型来表示2D数组。您尝试过什么？有什么问题？请具体说明。 - Boyd Stephen Smith Jr.

我想通过代码来确定路径到 @ 符号。 - user3841581

1

@user3841581 做一个类似于A*路径查找算法的东西。 - ThreeFx

你是在问要使用什么算法吗？你似乎已经用Java完成了这个问题，你可以在Haskell中使用相同的算法。如果你在将Java翻译成Haskell时遇到了麻烦，你应该更具体地说明问题。 - Boyd Stephen Smith Jr.

@bheklilr 我刚刚做完了。 - user3841581

显示剩余5条评论

2个回答

1

这在很大程度上取决于你想如何使用你的二维数组。

如果你只关心顺序使用，那么简单的列表嵌套（基本上是[[Char]]）可能就足够了。

如果你关心高效地获取特定的随机坐标，我可以想象一个IntList IntList Char可能适合你；它几乎像列表嵌套，但单个单元格可以更有效地更新，并且它可以便宜地进行路径查找的随机访问。

可能类似zipper的结构最适合你。我无法（到目前为止）想象出一种既能够以廉价的方式（每个相邻单元格O(1)）进行导航以进行路径查找，又能够廉价地进行更新的这种不错的结构。

此外，你可以通过在Monad.Control.State中保持Data.Array来使用可变映射，但你必须将所有逻辑提升到这个单子中（当你需要时，这会使传递映射的副本变得复杂）。

- 9000

请给我一个简单的例子，好吗？ - user3841581

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael · Accepted Answer

在Haskell中，制作2D数组有许多方法，以下是一个相对繁琐的示例，将字符读入Data.Array数组，然后使用所谓的 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