Haskell 中的 SceneGraph 遍历

Question

我想使用 Data.Tree 由 Transform 和 Shape 节点组成。在 SceneGraph 中，空间变换在遍历时累积并应用于形状以进行渲染。

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double
data SceneNode = XFormNode Transform | ShapeNode Shape

假设我们有一个场景，其中有一个物体移动到右侧，并由底部的正方形和顶部的圆形组成，

^
|
|  ()
|  []
0----->

我想出了这个树定义：

let tree = Node (XFormNode (vector2 10 0))
                [Node (ShapeNode (Square 10)) []
                ,Node (XFormNode (vector2 0 10))
                      [Node (ShapeNode (Circle 10)) []]
                ]

渲染将是这样的：

render :: Position2 -> Shape -> IO ()
render p (Circle r) = drawCircle p r
render p (Square a) = drawSquare p a

我的问题是：

1）如何做您定义了一个 traverse 函数来累积转换并调用渲染任务吗？

2）如何避免进行遍历IO？

3）是否有一个更短的版本来定义这棵树？除了第一个 Node 定义和所有空 subForest 之外的所有内容实际上都是多余的。

谢谢你！

Answer 1

矛盾的是，Data.Tree 在 Haskell 中并不经常使用，因为定义自定义树类型非常容易。在你的情况下，我将实现场景图（树）如下：

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double
data Scene     = Transform Transform [Scene] | Shape Shape

你的例子变成

example :: Scene
example = Transform (vector2 10 0)
                    [ Shape (Square 10)
                    , Transform (vector2 0 10) [Shape (Circle 10)]
                    ]

这个答案第3点。

要遍历树，请使用递归：

render :: Position2 -> Scene -> IO ()
render p (Transform v scenes) = mapM_ (render (p+v)) scenes
render p (Shape (Circle r))   = drawCircle p r
render p (Shape (Square a))   = drawSquare p a

有更多通用的遍历可用，例如在Data.Traversable，但它们更“统一”。简而言之，在树上使用递归是完全没问题的。

关于第 2 点，一旦您决定应该在 IO monad 中渲染圆形和正方形，您就无能为力了。

Answer 2

我喜欢将树表示为带有底层列表单子的单子列表。如果这句话令人困惑，只需看看代码：

import Control.Applicative (liftA2)
import Control.Monad.ListT (ListT) -- "List" in hackage
import Data.List.Class (cons, joinL, lastL, scanl) -- "List" in hackage
import Data.Monoid (mempty)
import Data.Tensor (Vector2 (..)) -- "Tensor" in hackage
import Prelude hiding (scanl)

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double deriving Show
data SceneNode = XFormNode Transform | ShapeNode Shape deriving Show

tree :: ListT [] SceneNode
tree
    = cons (XFormNode (Vector2 10 0))
    $ joinL
        [ cons (ShapeNode (Square 10)) mempty
        , cons (XFormNode (Vector2 0 10)) $ cons (ShapeNode (Circle 10)) mempty
        ]

traverseStep :: (Transform, SceneNode) -> SceneNode -> (Transform, SceneNode)
traverseStep (ta, _) n@(XFormNode tb) = (liftA2 (+) ta tb, n)
traverseStep (t, _) n = (t, n)

ghci> lastL $ scanl traverseStep (Vector2 0 0, XFormNode (Vector2 0 0)) tree
[ (Vector2 10.0 0.0,  ShapeNode (Square 10.0))
, (Vector2 10.0 10.0, ShapeNode (Circle 10.0))
]

这些树与 Data.Tree 中的树不同之处在于：

• 您可以使用 monad 和列表的现有函数（例如 scanl）。

• 它们可以是一元的

  • 例如，目录结构树可以是 IO 单子树，它是在迭代它时生成的。其类型为ListT (ListT IO) FilePath。请参阅 http://github.com/yairchu对于此示例，/generator/blob/master/ListTree/src/System/Directory/ListTree.hs
• 叶节点和具有 0 个子节点的节点是不同的东西。这在某些情况下可能有意义（例如区分空目录和文件）
  • cons x mempty 是叶子，cons x (joinL []) 是具有 0 个子节点的节点。