Tilman Zuckmantel
Tilman Zuckmantel

Reputation: 720

A "do nothing" guard for a recursive function?

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

Answers (3)

hkBst
hkBst

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

Rein Henrichs
Rein Henrichs

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

willeM_ Van Onsem
willeM_ Van Onsem

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

Related Questions