Reputation: 720
we have the following function which builds up a tree. It's a tree which has a Node and as many subtrees as you want.
generateGameTree g p = Node (g,p) [ ((fst x),generateGameTree (snd x) (nextPlayer p)) | x <- (findPossibleMoves p g) ]
now the Problem is to find a recursive base case. We have a function called identifyWinner which does pretty much what it says.
The idea is, to use this function to determine if someone has won and to stop making subtrees whenever that happend. But that would look something like this:
generateGameTree g p =
| identifyWinner g p == Nothing = Node (g,p) [ ((fst x),generateGameTree (snd x) (nextPlayer p)) | x <- (findPossibleMoves p g) ]
| otherwise = "DO NOTHING"
We cant figure out how to actually do nothing. Is there a way to make this happen in Haskell?
Thanks in advance!
Upvotes: 0
Views: 2141
Reputation: 3370
If there is already a winner and this means the game has ended and there are no more moves, then that is what the result should be, the current state of the game together with a list of no children, so:
makeGameTree g p =
| identifyWinner g p == Nothing =
Node (g,p) [ (fst x, makeGameTree (snd x) (nextPlayer p))
| x <- (findPossibleMoves p g) ]
| otherwise = Node (g,p) []
Upvotes: 0
Reputation: 15605
If you have a function
nextPositions :: Game -> [Game]
which gives all the positions that can result from taking every possible move at the given position then a game tree is a Cofree [] Game
from Control.Comonad.Cofree
type GameTree = Cofree [] Game
and it can be generated with
generateGameTree :: Game -> GameTree
generateGameTree = coiter nextPositions
If positions which are won have no next positions then the generation will automatically stop at won positions. You can then convert this to a more usual Data.Tree
representation if you want.
Upvotes: 1
Reputation: 477210
First of all it is rather un-Haskell to say that Haskell does something, that's the whole point of declarative programming and lazy programming. You describe the output. How it is actually generated is up to the compiler.
To answer your question, you could change your function a bit, such that it allows Maybe
:
generateGameTree g p =
| identifyWinner g p == Nothing = Just $ Node (g,p) $ filter (isJust . snd) [ ((fst x),generateGameTree (snd x) (nextPlayer p)) | x <- (findPossibleMoves p g) ]
| otherwise = Nothing
the filter
will filter out Nothing
s in the tree.
Another (more or less equivalent) solution is generating a list of nodes, and the list is either empty, or a singleton:
generateGameTree g p =
| identifyWinner g p == Nothing = [Node (g,p) $ concat [ ((fst x),generateGameTree (snd x) (nextPlayer p)) | x <- (findPossibleMoves p g) ] ]
| otherwise = []
Upvotes: 3