四叉树字符串的表示

Question

我得到了一个这种形式的字符串 ppeeefpffeefe。值：

p表示父节点
e表示空节点
f表示一个全节点

可以在此处看到表示此字符串的图像：https://i.stack.imgur.com/GZppc.png

我正在 Haskell 中编写代码并尝试将此表示转换为 1024 长整数列表，其中 1 表示黑色（完整）像素，0 表示白色（空）像素，假设图像大小为 32x32像素.

这是我的代码，但 Haskell 给我带来了麻烦。我知道我需要跟踪我访问过多少父节点并以这种方式更新最高级别。我正在尝试采用 DFS 方法，但任何有用的方法都会有所帮助。

getQuad :: String -> Int -> Int -> Int -> [Int] -> [Int]
getQuad tree level highestLevel pCount result | (node == 'p') = result ++ (getQuad (drop 1 tree) (level+1) level 0 result)
                                              | (node == 'e')  = result ++ (getQuad (drop 1 tree) level highestLevel pCount (result ++ (take (getAmount level) [0,0..])))
                                              | (node == 'f') = result ++ (getQuad (drop 1 tree) level highestLevel pCount (result ++ (take (getAmount level) [1,1..])))
                                              | otherwise = result
                                               where
                                                    node = g

getNodeValue :: String -> Char
getNodeValue tree = if (length tree > 0) then tree !! 0 else 'x'

getAmount :: Int -> Int
getAmount l = 1024 `div` (4^l)

谢谢！

Answer 1

我认为您试图在一个函数中做太多事情。我建议重新开始，并明确引入单独的解析阶段（将您的 String 转换为表示它的 ADT）和生产阶段（将 ADT 的值转换为 Int 的列表）。例如，合适的 ADT 可能如下所示：

data QuadTree = Parent QuadTree QuadTree QuadTree QuadTree
              | Empty
              | Full
              deriving (Eq, Ord, Read, Show)

有多种解析技术和库。考虑到您明显的专业水平和格式的简单性，我想我可能建议您从手动编写解析器开始并忽略 error-handling。稍后你可以考虑学习 error-handling 工具，如 Maybe 或 Either 和解析组合器库，如 parsec 和朋友，以使其更灵活地适应语言的变化。

因此，手动忽略 error-handling。这是我要放置并尝试填充的骨架。我们的解析器不仅需要消耗 String，还需要能够只消耗 String 的一部分并说出剩下的：在处理嵌套父节点时，我们需要 return给外部父对象的是内部父对象未使用的字符串块。所以：

parseQuadTree :: String -> (String, QuadTree)
parseQuadTree ('p':rest) = -- TODO: exercise for the reader
parseQuadTree ('e':rest) = (rest, Empty)
parseQuadTree ('f':rest) = (rest, Full)
parseQuadTree other = error $ "parsing failed, expected a p, e, or f, but got " ++ other ++ " instead"

例如，一旦我们完成此功能，我们可能会期望以下 ghci 交换：

> parseQuadTree "e"
("", Empty)
> parseQuadTree "eef"
("ef", Empty)
> parseQuadTree "peeeeef"
("ef", QuadTree Empty Empty Empty Empty)

一旦你有了它，我就会尝试制作一个合理的二维结果表示。也许嵌套列表可以：

type Image = [[Int]]

例如，您可以将外部列表的每个元素解释为图像的一行；它的元素是该行的列。这个东西需要的三个基本操作是水平和垂直粘贴图像 side-by-side 并创建一个空白图像。

hcat, vcat :: Image -> Image -> Image
hcat = -- TODO: exercise for the reader
vcat = -- TODO: exercise for the reader

blank :: Int -> Int -> Int -> Image
blank w h pixel = -- TODO: exercise for the reader
-- OR, you could take just one size argument; we only ever need
-- square blank images in the following code

例如，一旦我们完成实施，您可能会期待这些 ghci 交换：

> :set +m
> let x = [[0, 1]
|         ,[2, 3]
|         ]
|     y = [[4, 5]
|         ,[6, 7]
|         ]
|
> hcat x y
[[0,1,4,5],[2,3,6,7]]
> vcat x y
[[0,1],[2,3],[4,5],[6,7]]
> blank 2 3 4
[[4,4],[4,4],[4,4]]

现在您可以编写一个将 QuadTree 转换为 Image 的函数。我们必须知道图像应该有多大，所以让我们把它作为函数的参数。

renderQuadTree :: Int -> QuadTree -> Image
renderQuadTree size (Parent nw ne sw se) = -- TODO: exercise for the reader; use hcat and vcat
    where subtreeSize = size `div` 2
renderQuadTree size Empty = blank size size 0
renderQuadTree size Full = blank size size 1

例如，一旦完成，我们可能会期望在 ghci 进行一些这样的交流：

> renderQuadTree 2 Empty
[[0,0],[0,0]]
> renderQuadTree 2 Full
[[1,1],[1,1]]
> renderQuadTree 2 (Parent Empty Full Full Empty)
[[0,1],[1,0]]
> renderQuadTree 4 (Parent Empty (Parent Full Empty Empty Full) Empty Full)
[[0,0,1,0],[0,0,0,1],[0,0,1,1],[0,0,1,1]]

最后我们可以制作一个 top-level 函数，将所有这些组合成一个方便的部分。

getQuad :: String -> [Int]
getQuad s = case parseQuadTree s of
    ("", t) -> concat (renderQuadTree 32 t)
    (s', _) -> error $ "parser did not consume the entire description string, leftovers are: " ++ s

四叉树字符串的表示

Representation of a quadtree string

algorithm

tree

haskell

quadtree

depth-first-search