Quali sono i modi di programmazione funzionale per implementare Conway's Game of Life [closed]

Question

Quali sono i modi di programmazione funzionale per implementare Conway's Game of Life [closed]

#1 da (11 voti)
#2 da (9 voti)
#3 da (3 voti)
#4 da (3 voti)
#5 da (1 voti)

12

Recentemente implementato per divertimento Conway's Game of Life in Javascript (in realtà coffeescript ma stessa cosa). Dal momento che javascript può essere usato come linguaggio funzionale stavo cercando di rimanere fino alla fine dello spettro. Non ero contento dei miei risultati. Sono un programmatore OO abbastanza buono e la mia soluzione ha lo stesso vecchio-vecchio-vecchio. Così lunga domanda in breve: qual è lo stile funzionale (pseudocodice) di farlo?

Ecco Pseudocode per il mio tentativo:

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)

functional-programming

posta George Mauer 20.11.2011 - 18:39

fonte

5 risposte

9

Se stai scrivendo una versione di programmazione funzionale della vita devi farlo tu stesso per conoscere l'algoritmo di Gosper. Usa idee dalla programmazione funzionale per ottenere trilioni di generazioni al secondo su tavole trilioni di quadrati su un lato. Sembra impossibile, lo so, ma è completamente possibile; Ho una piccola implementazione in C # che gestisce facilmente quadrati quadrati da 2 ^ 64 quadrati su un lato.

Il trucco consiste nel trarre vantaggio dalla massiccia auto-similarità delle tavole Life sia nel tempo che nello spazio. Memorizzando lo stato futuro di ampie sezioni del tabellone è possibile avanzare rapidamente enormi sezioni contemporaneamente.

Avevo intenzione di scrivere un'introduzione per principianti all'Algoritmo di Gosper per molti anni, ma non ne ho mai avuto il tempo. Se finisco, scriverò un link qui.

Nota che vuoi cercare Algoritmo di Gosper per calcoli sulla vita , non l'Algoritmo di Gosper per calcolare somme ipergeometriche.

risposta data 21.11.2011 - 18:30

fonte

3

Bella coincidenza, abbiamo coperto questo esatto problema nella nostra lezione di Haskell oggi. La prima volta l'ho visto, ma qui c'è un link al codice sorgente che ci è stato dato:

link

risposta data 22.11.2011 - 00:42

fonte

3

Potresti voler dare un'occhiata alle implementazioni su RosettaCode per l'ispirazione.

Ad esempio ci sono versioni Haskell e OCaml funzionali che creano una nuova scheda ogni turno applicando una funzione alla precedente, mentre la versione grafica di OCaml utilizza due array e li aggiorna alternativamente per la velocità.

Alcune delle implementazioni decompongono la funzione aggiornamento della scheda in funzioni per contare il quartiere, applicando la regola di vita e iterando sopra la lavagna. Quelli sembrano componenti utili su cui basare un design funzionale. Prova a modificare solo la scheda, mantenendo tutto il resto come pura funzione.

risposta data 21.11.2011 - 23:57

fonte

1

Ecco una breve versione puramente funzionale in Clojure. Tutto il merito va a Christophe Grand che ha pubblicato questo nel suo post sul blog: Conway's Game of La vita

(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)))

È quindi possibile riprodurre il gioco applicando ripetutamente la funzione "step" a un gruppo di celle, ad esempio:

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

L'intelligenza è la parte (delle celle vicine al mapcat) - ciò che fa è creare un elenco di otto vicini per ognuna delle celle attive e concatenarle tutte insieme. Quindi il numero di volte in cui ogni cella appare in questa lista può essere contato con (frequenze ...) e infine quelli che hanno i conteggi di frequenza giusti passano alla generazione successiva.

risposta data 22.11.2011 - 11:37

fonte

Leggi altre domande sui tag functional-programming

Chi ha inventato i puntatori? Tempo necessario per iniziare la codifica in una nuova azienda [chiuso]

score 11 · Accepted Answer

Bene, un paio di idee. Non sono un esperto di FP, ma ...

È abbastanza chiaro che dovremmo avere un tipo Board che rappresenta uno stato di gioco. La base dell'implementazione dovrebbe essere una funzione evolve di tipo evolve :: Board -> Board ; nel senso che produce un Board dall'applicazione delle regole del gioco a un Board .

Come dovremmo implementare evolve ? Un Board dovrebbe probabilmente essere una matrice n x m di Cell s. Potremmo implementare una funzione cellEvolve di tipo cellEvolve :: Cell -> [Cell] -> Cell che ha dato un Cell e il suo vicino Cell s calcola lo stato Cell nella successiva iterazione.

Dovremmo anche implementare una funzione getCellNeighbors che estrae i vicini di Cell s da un Board . Non sono completamente sicuro della firma di questo metodo; a seconda di come implementare Cell e Board potresti avere per esempio getCellNeighbors :: Board -> CoordElem -> CoordElem -> [Cell] , che ha dato una tavola e due coordinate ( CoordElem sarebbe il tipo utilizzato per indicizzare le posizioni in Board ), ti dà un elenco di lunghezza variabile dei vicini (non tutte le celle nella scheda hanno lo stesso numero di vicini di casa- gli angoli hanno 3 vicini, i bordi 5 e tutti gli altri, 8).

evolve può quindi essere implementato combinando cellEvolve e getCellNeighbors per tutte le celle nella scheda, ancora una volta l'implementazione esatta dipenderà da come si implementa Board e Cell , ma dovrebbe essere qualcosa di simile a "per tutte le celle nella scheda corrente, prendi i loro vicini e usale per calcolare la cella corrispondente della nuova scheda". Ciò dovrebbe essere possibile fare con un'applicazione generica di quelle funzioni su tutta la scheda usando una "funzione di cella della mappa su scheda" .

Altri pensieri:

Dovresti davvero implementare cellEvolve in modo che assuma come parametro un tipo GameRules che codifica le regole del gioco, ad esempio un elenco di tuple (State,[(State,NumberOfNeighbors)],State) che dice per un dato stato e il numero dei vicini in ogni stato, che dovrebbe essere lo stato nella prossima iterazione. La firma di cellEvolve potrebbe quindi essere cellEvolve :: GameRules -> Cell -> [Cell] -> Cell
Questo ti porta logicamente a fare di evolve :: Board -> Board di trasformarsi in evolve :: GameRules -> Board -> Board , in modo che tu possa usare evolve invariato con diverso GameRules , ma potresti fare un ulteriore passo avanti e rendere cellEvolve pluggable invece di GameRules .
Giocando con getCellNeighbors potresti anche rendere evolve generico rispetto alla topologia di Board - potresti avere getCellNeighbors che avvolge i bordi di ciascuna scheda, le schede 3d, ecc.