哈斯克尔中的SceneGraph遍历

Question

我想使用由Transform和Shape节点组成的Data.Tree在Haskell中实现一个简单的SceneGraph。在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)有没有更短的版本来定义这棵树？除第一个节点定义之外的所有节点定义和所有空subForests实际上都是多余的。

谢谢!

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)]
                    ]

这回答了第三点。

要遍历树，请使用递归：

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中，但它们更“统一”。简而言之，在树上使用递归是非常好的。

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

Answer 2

我喜欢将树表示为带有底层列表monad的一元列表。如果这句话让人困惑，看看代码就知道了：

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中的树的不同之处在于：

• 您可以使用现有的单体和列表函数(如scanl)来实现这些功能。
• 它们可以是一元

- For example a directory structure tree can be an IO-monadic tree which is generated as you iterate over it. Its type would be `ListT (ListT IO) FilePath`. See [http://github.com/yairchu/generator/blob/master/ListTree/src/System/Directory/ListTree.hs](http://github.com/yairchu/generator/blob/master/ListTree/src/System/Directory/ListTree.hs) for this example

​

具有0个子节点的

• 叶和节点是不同的。这在某些情况下可能是有意义的(例如，为了区分空目录和文件)
  • cons x mempty是一个叶，而cons x (joinL [])是一个具有0 children.

的节点

​