Resource Files

• exercise165.zip
• Life.lhs
  Solution Template

lhs2TeX Life.lhs > Life.tex
pdflatex Life.tex

\documentclass[a4paper]{article} \usepackage[ngerman]{babel} \usepackage[utf8x]{inputenc} \usepackage[german=guillemets]{csquotes} %include polycode.fmt \setlength\parindent{0pt} \setlength{\parskip}{5pt plus 2pt minus 1pt} \usepackage{enumitem} \begin{document} \author{} \title{Übungsblatt 3} \maketitle \section*{Aufgabe 3: Game of Life (Spiel des Lebens)} Ziel dieser Aufgabe ist es eine einfache Version von ``Conways Spiel des Lebens''\footnote{\verb+https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens+} in Haskell zu implementieren. > module Life where Das Spielfeld wird dargestellt durch quadratische Matrizen, deren Einträge entweder belegt (bevölkert), oder nicht belegt sind. Ein Eintrag an Position (i, j) in einer Matrix wird durch seine Zeile i und sein Spalte j bezeichnet, wobei die Zählung der Zeilen und Spalten bei 0 beginnt. Diese Aufgabe ist dem Modul ``Funktionale Programmierung'' von Manfred Schmidt-Schauß an der Johann Wolfgang Goethe-Universität entnommen. Solche Matrizen lassen sich in Haskell durch die folgende Datenstruktur darstelle Gegeben sei eine Datenstruktur, die bool'sche Werte in einem 2-dimensionalen Raum darstellt. > data Matrix = Matrix [[Bool]] > deriving (Eq) Die Struktur ist eine Instanz der Klasse Show, so dass eine Matrix als String gut angezeigt werden kann. > instance Show Matrix where > show (Matrix m) = unlines $ map showRow m > where showRow = map (\x -> if x then '#' else ' ') Es sollen nur quadradrische Matrix-Objekte erzeugt werden. Daher die folgende Konstruktorfunktion. > newMatrix n = Matrix $ replicate n (replicate n False ) Die Anzahl der Zeilen und Spalten lässt sich demnach direkt über die Länge der äußeren Liste erfragen. > groesseMatrix (Matrix m) = length m \begin{enumerate}[label=\alph*)] \item Implementieren Sie eine Funktion, die eine Matrix und eine Matrix-Position als Eingabe erwartet und die Belegung des durch die Koordinate gegebenen Matrix-Eintrags berechnet. > get :: Matrix -> (Int, Int) -> Bool > get _ _ = False \item Implementieren Sie mit Hilfe einer List-Comprehension eine Funktion, die eine Matrix-Position und die Dimension einer Matrix erwartet und die Positionen aller benachbarten Felder berechnet. Beispielsweise liefert nachbarn (1,1) 3 als Resultat die Liste:\\ \verb+[(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1),(2,2)]+ > nachbarn :: (Int, Int) -> Int -> [(Int, Int)] > nachbarn _ _ = [] \item Implementieren Sie eine Funktion, die in einer gegebenen Matrix zu einem durch seine Position gegebenen Feld die Anzahl seiner belegten Nachbarn berechnet. > anzahlBelegterNachbarn :: (Int, Int) -> Matrix -> Int > anzahlBelegterNachbarn _ _ = 0 \item Implementieren Sie eine Funktion, die den Nachfolger einer Matrix gemäß der Spielregeln des Spiel des Lebens berechnet: \begin{itemize} \item Für eine Matrix-Zelle, die belegt ist: \begin{itemize} \item Jede Zelle mit einem oder keinem Nachbarn stirbt. \item Jede Zelle mit vier oder mehr Nachbarn stirbt. \item Jede Zelle mit zwei oder drei Nachbarn überlebt. \end{itemize} \item Für eine Matrix-Zelle, die leer ist: \begin{itemize} \item Jede Zelle mit drei Nachbarn wird belegt. \end{itemize} \end{itemize} Hier bedeutet „stirbt“: nicht belegt in der Matrix (False) und „überlebt“: belegt in der Matrix (True). > zugGOL :: Matrix -> Matrix > zugGOL m = m \item Implementieren Sie eine Funktion, die zu einer Anfangsmatrix eine Liste der Folgematrizen berechnet, die durch aufeinanderfolgende Spielzüge im Spiel des Lebens aus entstehen. > zuege :: Matrix -> Int -> [Matrix] > zuege m n = [] \item Implementieren Sie eine Funktion, die zu einer gegebenen Matrix testet, ob der durch sie beschriebene Spielzustand oszilliert. Ein Spielzustand M oszilliert, wenn nach i-Spielzügen (mit i ≥ 1) wieder der Zustand M erreicht ist. > oszilliert :: Matrix -> Bool > oszilliert m = False \end{enumerate} \end{document}