Статьи

Игра в жизнь в Хаскеле

Ката 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 на самом деле очень хорошо соответствует функциональному стилю. Его программы обычно работают правильно, в тот момент, когда вы можете заставить их скомпилировать.