Ката Game of Life — это справочная задача, которая может быть решена различными способами, с использованием нового языка, методологии, среды тестирования, IDE или других. Устранение проблемы при замене одного фактора в уравнении позволяет избежать многих (но не всех) смешанных переменных.
У меня было подозрение, что функциональные реализации Игры Жизни были бы очень краткими, имея проблему математической формулировкой. После некоторого функционального кода PHP , на этот раз я попробовал Haskell, известный статически типизированный функциональный язык.
Основные типы
В Haskell мы можем определить перечислительные типы данных. Состояние ячейки в Game of Life может быть смоделировано с помощью логического значения, или, точнее, с любым типом, содержащим только два значения. Поэтому имеет смысл давать имена возможным состояниям вместо использования True и False.
data CellState = Dead | Alive
Более сложные типы данных могут быть построены путем составления списка существующих типов. Справа от = Position находится конструктор, который определяет этот «объект значения», составленный из 2 целых чисел, представляющих фактически положение ячейки в бесконечной 2D-плоскости.
data Position = Position Integer Integer
Функции также имеют типы: Я определяю Поколение как снимок плоскости в один момент времени. Способ полностью описать поколение состоит в предоставлении функции, которая отображает каждый возможный экземпляр Position в CellState, Dead или Alive.
type Generation = Position -> CellState
Листовые функции
Я не знаю, есть ли технический термин, но даже при разработке извне мы должны прийти к некоторым функциям, которые не вызывают другие.
is_alive — простая карта от CellState до логического значения; нам это нужно, потому что примитивам, подобным filter, нужен вход Bool (точнее, тип возврата функции, взятой в качестве входа):
is_alive :: CellState -> Bool is_alive Alive = True is_alive Dead = False
Соседи могут генерировать список значений позиции из одного, на самом деле список из 8 значений. Я не нашел более простого решения, чем генерация его вручную, но это определение, основанное на конкретных случаях, вероятно, можно сократить:
neighbors :: Position -> [Position] neighbors (Position x y) = [(Position (x-1) (y-1)), (Position x (y-1)), (Position (x+1) (y-1)), (Position (x+1) y), (Position (x+1) (y+1)), (Position x (y+1)), (Position (x-1) (y+1)), (Position (x-1) y)]
составление
Функция alive_neighbors берет Generation и Position и сообщает вам, сколько из 8 ячеек, расположенных рядом с выбранной позицией, являются живыми в этом поколении.
alive_neighbors :: Generation -> Position -> Int alive_neighbors generation position = length (filter is_alive (map generation (neighbors position)))
Чтение функции изнутри: первые соседи применяются к позиции, и генерация отображается на результат: в этот момент у нас есть список значений CellState. Фильтр создает новый список, содержащий только Живые значения, и длина считает их.
В сигнатуре типа вы можете заметить, как указывается функция с несколькими аргументами, разделяя аргументы и возвращаемый тип с помощью ->:
alive_neighbors :: Generation -> Position -> Int
Причина заключается в каррировании, поскольку каждая функция в Haskell имеет только один аргумент, и мы пишем функцию, которая принимает Generation и возвращает функцию, которая принимает Position. Но это сейчас не важно: эта запись означает, что у нас есть два аргумента, и возвращаемое значение будет Int.
Прямо сейчас мы готовы решить полную проблему: наша функция эволюции берет Поколение и производит другое Поколение. Это функция высшего порядка, такая как map и filter, потому что она использует функцию более низкого уровня в качестве аргумента, а не просто использует ее.
evolution :: Generation -> Generation evolution generation position = case (alive_neighbors generation position) of 2 -> if (is_alive (generation position)) then Alive else Dead 3 -> Alive _ -> Dead
Здесь происходит волшебство карри. Сигнатура типа для эволюции может быть прочитана как:
evolution :: Generation -> Position -> CellState
Таким образом, чтобы «вернуть» новое Поколение из старого Поколения, мы можем определить функцию, которая принимает старое Поколение и Позицию в качестве входных данных и возвращает CellState. Кажется волшебством, но это действительно соответствует.
Остальная часть функции — это просто оператор switch, возвращающий новое состояние как Alive или Dead в зависимости от текущего CellState и количества alive_neighbors.
Отображение
Поскольку я еще не знаю, как писать модульные тесты (или тесты на основе свойств) в Haskell, единственный способ поэкспериментировать с моей реализацией во время кодирования состоял в том, чтобы визуализировать результаты.
Эти функции принимают Поколение и визуализируют его в сетке 10х10, начиная с (1, 1) координат.
visualize_generation generation = map (visualize_line generation) [1..10] visualize_line :: Generation -> Integer -> String visualize_line generation y = concat (map (visualize_cell generation y) [1..10]) visualize_cell generation y x = case (generation (Position x y)) of Alive -> ['X'] Dead -> [' ']
Вот классическая барная структура, последовательность из трех живых клеток, которые вращаются на 90 ° в каждом новом поколении:
bar (Position 1 2) = Alive bar (Position 2 2) = Alive bar (Position 3 2) = Alive bar (Position x y) = Dead
Вот вращающаяся планка:
*Main> mapM_ print (visualize_generation bar) " " "XXX " " " " " " " " " " " " " " " " " *Main> mapM_ print (visualize_generation (evolution bar)) " X " " X " " X " " " " " " " " " " " " " " " *Main> mapM_ print (visualize_generation (evolution (evolution bar))) " " "XXX " " " " " " " " " " " " " " " " "
Выводы
Функциональные подходы иногда намного быстрее. Я хотел бы, чтобы карринг без синтаксических издержек был доступен на императивных языках, чтобы легко преобразовывать вызовы методов в замыкания.
Синтаксис Haskell на самом деле очень хорошо соответствует функциональному стилю. Его программы обычно работают правильно, в тот момент, когда вы можете заставить их скомпилировать.