Haskell restricting a RoseTree to depth n

my code, takes a gameState and tries to return a list of GameStates.

I wish to limit the depth of the tree to depth n.

to do this i wrote this code

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)

this code compiles but does not return all of the nodes at a depth n. Instead it only returns some of the nodes at depth n. This has confused me for many days now as the code should return the tree up to a depth n not only some of the tree.

any help or guidance would be greatly appreciated !!

Solution

I'm assuming your definition is

data RoseTree a = RoseNode a [RoseTree a]

What you're trying to do is construct the game tree and then truncate the tree to depth n. But your code doesn't actually do that.

Suppose that applyMoves state = [move1, move2, move3] and depth = 2.

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

You're throwing away information regarding move2 and move3.

The best way to do this is by first constructing the tree and then limiting its depth.

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

This approach works because of laziness.

For the record, I think you're almost certainly doing the wrong thing with respect to Maybe. I strongly suspect that the correct approach is something like

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

But I don't know the specific application you're working on, so I might be wrong.