Haskell 将 RoseTree 限制为深度 n

Question

我的代码获取一个游戏状态并尝试return一个游戏状态列表。

我希望将树的深度限制为深度n。

为此我编写了这段代码

applyMoves :: Maybe GameState  -> [Maybe GameState]
applyMoves g = map (applyMove (f g)) (legalMoves (f g))
  where 
    f :: Maybe GameState -> GameState
    f (Just x) = x 

othelloTree :: Maybe GameState -> Int -> RoseTree (Maybe GameState)
othelloTree (state) 0   = RoseNode (state) []
othelloTree state depth = RoseNode (state) (myMap' (othelloTree) (applyMoves state) (depth-1))
  where 
    myMap' :: (a->Int->c)->[a]->Int->[c]
    myMap' _ [] 0 = []
    myMap' _ [] _ = []
    myMap' f (x:xs) 0  = []
    myMap' f (x:xs) i = (f (x) (i)) : myMap' f xs (i-1)

此代码编译但不编译深度 n 处的所有节点 return。相反，它只有 returns 一些深度为 n 的节点。这让我困惑了很多天，因为代码应该 return 树的深度不只是树的一部分。

任何帮助或指导将不胜感激!!

Answer 1

我假设你的定义是

data RoseTree a = RoseNode a [RoseTree a]

您要做的是构建游戏树，然后将树截断到深度 n。但是您的代码实际上并没有这样做。

假设 applyMoves state = [move1, move2, move3] 和 depth = 2.

然后myMap' othelloTree [move1, move2, move3] 1 = [othelloTree move1 1].

您正在丢弃有关 move2 和 move3 的信息。

最好的方法是先构建树，然后限制它的深度。

limitDepth :: Int -> RoseTree a -> RoseTree a
limitDepth 0 (RoseNode a _) = RoseNode a []
limitDepth n (RoseNode a children) = RoseNode a (fmap (limitDepth (n - 1)) children)

makeTree :: Maybe GameState -> RoseTree (Maybe GameState)
makeTree state = RoseNode state (fmap makeTree (applyMoves state))

othelloTree :: Int -> Maybe GameState -> RoseTree (Maybe GameState)
othelloTree n = limitDepth n . makeTree

这种方法之所以有效，是因为懒惰。

郑重声明，我认为您几乎肯定在 Maybe 方面做错了事。我强烈怀疑正确的方法是

import Data.Maybe (catMaybes)

-- Given a state, return a list of all states that can be achieved by applying one legal move.
applyMoves :: GameState -> [GameState]
applyMoves state = catMaybes $ fmap (applyMove state) (legalMoves state)

makeTree :: GameState -> RoseTree GameState
makeTree state = RoseNode state (fmap makeTree (applyMoves state))

但我不知道你正在处理的具体应用程序，所以我可能是错的。

Haskell 将 RoseTree 限制为深度 n

Haskell restricting a RoseTree to depth n

haskell

recursion

tree

minimax