Quelles sont les méthodes de programmation fonctionnelle pour implémenter le jeu de la vie de Conway [fermé]

J'ai récemment implémenté pour le plaisir le jeu de la vie de Conway en Javascript (en fait coffeescript mais même chose). Étant donné que javascript peut être utilisé comme langage fonctionnel, j'essayais de rester à cette extrémité du spectre. Je n'étais pas satisfait de mes résultats. Je suis un assez bon programmeur OO et ma solution a semblé identique-vieille-même-vieille. Donc, longue question courte: quel est le style fonctionnel (pseudocode) de le faire?

Voici le pseudocode pour ma tentative:

class Node
  update: (board) ->
    get number_of_alive_neighbors from board
    get this_is_alive from board
    if this_is_alive and number_of_alive_neighbors < 2 then die
    if this_is_alive and number_of_alive_neighbors > 3 then die
    if not this_is_alive and number_of_alive_neighbors == 3 then alive

class NodeLocations
  at: (x, y) -> return node value at x,y
  of: (node) -> return x,y of node

class Board
  getNeighbors: (node) -> 
   use node_locations to check 8 neighbors 
   around node and return count

nodes = for 1..100 new Node
state = new NodeState(nodes)
locations = new NodeLocations(nodes)
board = new Board(locations, state)

executeRound:
  state = clone state
  accumulated_changes = for n in nodes n.update(board)
  apply accumulated_changes to state
  board = new Board(locations, state)

Eh bien, quelques idées. Je ne suis pas un expert en PF, mais ...

Il est assez clair que nous devrions avoir un type Boardqui représente un état de jeu. La base de la mise en œuvre doit être evolvefonction du type evolve :: Board -> Board; ce qui signifie qu'il produit un à Boardpartir de l'application des règles du jeu à un Board.

Comment devrions-nous mettre en œuvre evolve? A Boarddevrait probablement être une matrice nxm de Cells. Nous pourrions implémenter une fonction cellEvolvede type cellEvolve :: Cell -> [Cell] -> Cellqui, étant donné a Cellet ses voisins, Cellcalcule l' Cellétat dans l'itération suivante.

Nous devons également implémenter une getCellNeighborsfonction qui extrait a Cells voisins de a Board. Je ne suis pas entièrement sûr de la signature de cette méthode; selon la façon dont vous implémentez Cellet Boardvous pourriez avoir par exemple getCellNeighbors :: Board -> CoordElem -> CoordElem -> [Cell], qui, étant donné un tableau et deux coordonnées ( CoordElemserait le type utilisé pour indexer les positions dans a Board), vous donne une liste de longueur variable des voisins (toutes les cellules du tableau n'ont pas le le même nombre de voisins-coins ont 3 voisins, les frontières 5 et tout le monde, 8).

evolvepeut donc être implémenté en combinant cellEvolveet getCellNeighborspour toutes les cellules de la carte, l'implémentation exacte dépendra de nouveau de la façon dont vous implémentez Boardet Cell, mais cela devrait être quelque chose comme "pour toutes les cellules de la carte actuelle, obtenez leurs voisins et utilisez-les pour calculer la nouvelle cellule correspondante de la carte ". Cela devrait être possible grâce à une application générique de ces fonctions sur l'ensemble de la carte en utilisant une" fonction de cellule de carte sur carte ".

D'autres pensées:

• Vous devez vraiment implémenter cellEvolvepour qu'il prenne comme paramètre un type GameRulesqui code les règles du jeu - disons une liste de tuples (State,[(State,NumberOfNeighbors)],State)qui dit pour un état donné et le nombre de voisins dans chaque état, qui devrait être l'état dans la prochaine itération . cellEvolvela signature pourrait alors êtrecellEvolve :: GameRules -> Cell -> [Cell] -> Cell

• Cela vous amènerait logiquement à evolve :: Board -> Boardtransformer en evolve :: GameRules -> Board -> Board, afin que vous puissiez utiliser evolveinchangé avec différent GameRules, mais vous pourriez aller plus loin et rendre cellEvolvepluggable à la place de GameRules.

• Jouer avec getCellNeighborsvous pourrait également rendre evolvegénérique en ce qui concerne la Boardtopologie de la - vous pourriez avoir getCellNeighborsqui s'enroulent autour des bords de la carte, des cartes 3D, etc.

Si vous écrivez une version de programmation fonctionnelle de Life, vous vous devez d'apprendre l'algorithme de Gosper. Il utilise des idées de programmation fonctionnelle pour atteindre des milliards de générations par seconde sur des planches de milliards de carrés d'un côté. Cela semble impossible, je sais, mais c'est tout à fait possible; J'ai une jolie petite implémentation en C # qui gère facilement les planches carrées 2 ^ 64 carrés sur un côté.

L'astuce consiste à tirer parti de l'autosimilarité massive des planches Life à travers le temps et l'espace. En mémorisant l'état futur de grandes sections du tableau, vous pouvez rapidement avancer d'énormes sections à la fois.

J'ai l'intention de bloguer une introduction pour débutants à l'algorithme de Gosper depuis de nombreuses années, mais je n'ai jamais eu le temps. Si je finis par le faire, je posterai un lien ici.

Notez que vous voulez rechercher les calculs de l'algorithme de Gosper pour la vie , pas l'algorithme de Gosper pour calculer les sommes hypergéométriques.

Belle coïncidence, nous avons couvert ce problème exact dans notre conférence de Haskell aujourd'hui. La première fois que je l'ai vu, mais voici un lien vers le code source qui nous a été donné:

http://pastebin.com/K3DCyKj3

Vous voudrez peut-être vous inspirer des implémentations sur RosettaCode .

Par exemple, il existe des versions fonctionnelles Haskell et OCaml qui créent une nouvelle carte à chaque tour en appliquant une fonction à la précédente, tandis que la version graphique OCaml utilise deux tableaux et les met à jour alternativement pour la vitesse.

Certaines des implémentations décomposent la fonction de mise à jour de la carte en fonctions de comptage du voisinage, d'application de la règle de durée de vie et d' itération sur la carte. Ceux-ci semblent être des composants utiles pour fonder une conception fonctionnelle. Essayez de modifier uniquement la carte, en gardant tout le reste comme des fonctions pures.

Voici une courte version purement fonctionnelle de Clojure. Tout le mérite revient à Christophe Grand qui l'a publié dans son article de blog: Conway's Game of Life

(defn neighbours [[x y]]
  (for [dx [-1 0 1] 
        dy (if (zero? dx) [-1 1] [-1 0 1])]
    [(+ dx x) (+ dy y)]))

(defn step [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

Le jeu peut ensuite être joué en appliquant de manière répétée la fonction "step" à un ensemble de cellules, par exemple:

(step #{[1 0] [1 1] [1 2]})
=> #{[2 1] [1 1] [0 1]}

L'astuce est la partie (cellules voisines de mapcat) - ce que cela fait est de créer une liste de huit voisins pour chacune des cellules actives et de les concaténer toutes ensemble. Ensuite, le nombre de fois où chaque cellule apparaît dans cette liste peut être compté avec (fréquences ....) et enfin celles qui ont le bon nombre de fréquences atteignent la génération suivante.