Jakie są sposoby programowania funkcjonalnego wdrażania gry Conwaya w życie [zamknięte]

Niedawno zaimplementowałem dla zabawy Game of Life Conwaya w Javascript (właściwie coffeescript, ale to samo). Ponieważ javascript może być używany jako język funkcjonalny, starałem się pozostać na tym końcu spektrum. Nie byłem zadowolony z moich wyników. Jestem dość dobrym programistą OO, a moje rozwiązanie zostało spryskane tym samym-starym-tym samym-starym. Tak długie pytanie: jaki jest funkcjonalny (pseudokod) styl działania?

Oto Pseudokod dla mojej próby:

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)

Cóż, kilka pomysłów. Nie jestem ekspertem od FP, ale ...

Jest całkiem jasne, że powinniśmy mieć typ Boardreprezentujący stan gry. Podstawą wdrożenia powinna być evolvefunkcja typu evolve :: Board -> Board; co oznacza, że ​​powoduje to Boardzastosowanie reguł gry do Board.

Jak powinniśmy wdrożyć evolve? BoardPowinien prawdopodobnie matryca nXM od Cells. Możemy zaimplementować funkcję cellEvolvetypu, cellEvolve :: Cell -> [Cell] -> Cellktóra dla danego a Celli jego sąsiada Cells oblicza Cellstan w następnej iteracji.

Powinniśmy także zaimplementować getCellNeighborsfunkcję, która wyodrębnia Cellsąsiadów z Board. Nie jestem całkowicie pewien podpisu tej metody; w zależności od tego, jak się zaimplementujesz, Celli Boardna przykład możesz mieć getCellNeighbors :: Board -> CoordElem -> CoordElem -> [Cell], który z tablicą i dwiema współrzędnymi ( CoordElembyłby typem używanym do indeksowania pozycji w a Board), daje listę sąsiadów o zmiennej długości (nie wszystkie komórki na tablicy mają taka sama liczba sąsiadów - rogi mają 3 sąsiadów, granice 5 i wszystkich innych, 8).

evolvemożna więc zaimplementować łącząc cellEvolvei getCellNeighborsdla wszystkich komórek na planszy, ponownie dokładna implementacja będzie zależeć od sposobu implementacji Boardi Cell, ale powinno to być coś w rodzaju „dla wszystkich komórek na bieżącej planszy, zdobądź ich sąsiadów i użyj ich do obliczenia nowa komórka odpowiadająca komórce ”. Powinno to być możliwe w przypadku ogólnego zastosowania tych funkcji na całej płycie przy użyciu„ mapy funkcji komórki na tablicy ”.

Inne przemyślenia:

• Naprawdę powinieneś zaimplementować, cellEvolveaby jako parametr GameRulesprzyjmował typ kodujący reguły gry - powiedz listę krotek, (State,[(State,NumberOfNeighbors)],State)która mówi o danym stanie i liczbę sąsiadów w każdym stanie, który powinien być stanem w następnej iteracji . cellEvolvePodpis mógłby wtedy byćcellEvolve :: GameRules -> Cell -> [Cell] -> Cell

• To logicznie doprowadziłoby cię do zmiany evolve :: Board -> Boardw evolve :: GameRules -> Board -> Board, abyś mógł używać evolveniezmienionych z innymi GameRules, ale możesz pójść o krok dalej i uczynić cellEvolvewtykowym zamiast GameRules.

• Zabawa z getCellNeighborstobą może również być evolveogólna w odniesieniu do Boardtopologii - możesz mieć, getCellNeighborsktóre owijają się wokół krawędzi planszy, plansz 3d itp.

Jeśli piszesz funkcjonalną wersję programistyczną Life, musisz jej dowiedzieć się o algorytmie Gospera. Wykorzystuje pomysły z programowania funkcjonalnego, aby osiągnąć biliony pokoleń na sekundę na tablicach bilionów kwadratów na boku. Wiem, że to brzmi niemożliwe, ale jest całkowicie możliwe; Mam fajną małą implementację w języku C #, która z łatwością radzi sobie z kwadratowymi planszami 2 ^ 64 kwadratów z boku.

Sztuką jest wykorzystanie ogromnego samopodobieństwa plansz Życia zarówno w czasie, jak i przestrzeni. Zapamiętując przyszły stan dużych sekcji planszy, możesz szybko przejść do dużych sekcji jednocześnie.

Zamierzałem blogować wprowadzenie dla początkujących do Algorytmu Gospera od wielu lat, ale nigdy nie miałem czasu. Jeśli to zrobię, opublikuję link tutaj.

Zauważ, że chcesz sprawdzić obliczenia algorytmu Gospera dla życia , a nie algorytmu Gospera do obliczania sum hipergeometrycznych.

Niezły zbieg okoliczności, dokładnie omawialiśmy ten problem w naszym dzisiejszym wykładzie w Haskell. Pierwszy raz go widziałem, ale oto link do kodu źródłowego, który otrzymaliśmy:

http://pastebin.com/K3DCyKj3

Inspiracje możesz znaleźć w implementacjach RosettaCode .

Na przykład istnieją funkcjonalne wersje Haskell i OCaml, które tworzą nową tablicę w każdej turze poprzez zastosowanie funkcji do poprzedniej, podczas gdy wersja graficzna OCaml wykorzystuje dwie tablice i aktualizuje je naprzemiennie dla prędkości.

Niektóre implementacje rozkładają funkcję aktualizacji planszy na funkcje zliczania sąsiedztwa, stosowania reguły życia i iteracji po planszy. Wydają się być przydatnymi komponentami, na których można oprzeć funkcjonalny projekt. Spróbuj zmodyfikować tylko kartę, zachowując wszystko inne jako czyste funkcje.

Oto krótka, czysto funkcjonalna wersja Clojure. Wszystkie podziękowania należą się Christophe'owi Grandowi, który opublikował to na swoim blogu: 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)))

W grę można następnie grać, stosując wielokrotnie funkcję „krok” do zestawu komórek, np .:

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

Spryt to część (komórki sąsiadów mapcat) - tworzy to listę ośmiu sąsiadów dla każdej z aktywnych komórek i łączy je wszystkie razem. Następnie liczbę zliczeń każdej komórki na tej liście można policzyć (częstotliwości ....) i wreszcie te, które mają prawidłowe liczenie częstotliwości, przechodzą do następnej generacji.