CODEWITHSUNDEEP
haskelltree
Daniel
Daniel

Reputation: 71

Map or fold tree

If a tree has the data constructor and type of:

data Tree m v = Tree v [(m, Tree m v)]
type GTree g = Tree (Move g) (Player, GameState g)

where

moves :: g -> Player -> GameState g -> [Move g]
move :: g -> Player -> GameState g -> Move g -> GameState g

tree :: Game g => g -> (Player, GameState g) -> GTree g

Where tree needs to generate an infinite game tree.

Is map to fold preferred here? And how would one achieve doing so?

Upvotes: 0

Views: 314

Answers (2)

amalloy
amalloy

Reputation: 92117

You can't really fold here, because you don't have a recursive structure to consume; rather you want to produce one from a base value. In principle this is an unfold, as Carl says in another answer, but I don't think Carl suggests to actually use Data.List.unfoldr: unfoldr is for generating specifically lists. You could use it to generate, say, an infinite list of gradually-deeper game trees, implementing a sort of iterative deepening, but it is simpler to just write this recursive function by hand, perhaps using Data.List.unfoldr as a template to see how unfolding works in general.

Here is one implementation that seems reasonable to me, together with dummy definitions of the other data types you mention but do not define, so that the file is compilable on its own.

data Move g
data Player
data GameState g
class Game g

data Tree m v = Tree v [(m, Tree m v)]
type GTree g = Tree (Move g) (Player, GameState g)

moves :: g -> Player -> GameState g -> [Move g]
moves = undefined
move :: g -> Player -> GameState g -> Move g -> GameState g
move = undefined

tree :: Game g => g -> (Player, GameState g) -> GTree g
tree game (player, root) = expand root
  where expand node = Tree (player, node) $ explore node
        explore state = do
          edge <- moves game player state
          let node = move game player state edge
          return (edge, expand node)

Upvotes: 1

Carl
Carl

Reputation: 27023

Both map and fold for the Tree type would consume a Tree. You don't have a Tree to consume. Neither one will work. You're looking for an unfold. See Data.List.unfoldr for an example of what one looks like.

Upvotes: 0

Related Questions