Haskell restricting a RoseTree to depth n

Question

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

You apply `f x i` so with the *same* depth, whereas you use recursion with `myMap' f xs (i-1)` (so with another depth). Why is there a difference in applying `x` and working with `xs` (rest of the nodes)? This means that the second node works with `i-1`, the third with `i-2`, etc. You thus have a certain "skew" in the way how you handle the `RoseTree`. — Willem Van Onsem, May 30 '21 at 16:57
Would you please explain why `applyMoves :: Maybe GameState -> [Maybe GameState]` when you are requiring that `g :: Maybe GameState` be a `Just`? It seems like you'd be better off defining `applyMoves :: GameState -> [Maybe GameState]`. But if you're going to use your method, you should use `Data.Maybe.fromJust` instead of `f`. — Mark Saving, May 30 '21 at 18:42
Also, could you give the types for `applyMove` and `legalMoves`? — Mark Saving, May 30 '21 at 18:52
A [very idiomatic way to do this](https://stackoverflow.com/questions/7868507/non-trivial-lazy-evaluation/7868790#7868790) is to simply produce an infinite tree (or the whole tree, if that's finite), and have a post-processing pass that limits the tree to depth n. — Daniel Wagner, May 30 '21 at 20:12

Mark Saving · Accepted Answer · 2021-05-30T20:40:55.763

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.

Haskell restricting a RoseTree to depth n

1 Answers1