Добрый вечер.

Продолжая (после долгого перерыва) серию статей про ФП, я решил написать о том, как ленивая модель вычислений позволяет просто и элегантно работать с бесконечными списками.

Зачем это нужно? Допустим, решение какой-то задачи требует обработки нескольких массивов/списков/наборов данных. Если мы описываем решение в терминах операций над конкретными элементами (”a[i]=b[j]+c[j-i+1,j]“), у нас всегда есть риск упустить какой-то частный случай или совершить простейшую (и от этого вдвойне досадную) ошибку. Все наверняка хоть раз да и встречались с классическими ошибками типа “на единичку больше/меньше” и “выход за границы массива”.

Если же мы сумеем сформулировать решение в терминах операций над “целыми” списками/массивами, мы не только уменьшаем описанный риск, но и, как правило, получаем более короткий и читаемый код. Впрочем, довольно вступлений, перейдем к сути.
Для иллюстрации будет использоваться язык Haskell, для полного понимания происходящего полезно экспериментировать с приводимым кодом в какой-нибудь интерактивной среде (GHC, Helium или Hugs).

Задача: реализовать оптимальную стратегию игры в Wythoff’s game. Описание игры “на пальцах” выглядит так: представим себе шахматную доску, бесконечную в направлении вправо-вниз. На какой-то ее клетке стоит ферзь. Играют двое. На своем ходу игрок может передвинуть ферзя (по обычным правилам) на любую клетку, но только в направлении влево или вверх (или влево-вверх). Выигрывает тот, кто поставит ферзя в левый верхний угол доски.

Другое описание этой же игры выглядит так: есть две кучки одинаковых предметов. На своем ходу игрок может взять произвольное кол-во предметов из любой кучки, или же из обоих кучек сразу. Выигрывает тот, кто возьмет последний предмет. Игра выглядит детской и простой, но на самом деле является важным инструментом в теории игр: к ней и ее ближайшему родственнику – классической игре в Ним – сводится целый класс т.н. комбинаторных игр и изучению ее свойств посвящено множество книг и статей.

Выигрышная стратегия заключается в том, чтобы ставить ферзя только на такие (оптимальные) позиции, из которых оппонент, во-первых, не сможет закончить игру, и, во-вторых, не сможет сделать ход в какую-то другую оптимальную позицию, обладающую такими же свойствами. Если пронумеровать строки и столбцы шахматной доски, начиная с нуля, то координаты оптимальных позиций будут таковы (за подробным объяснением см. сюда):

Если мы каким-то образом вычислили список координат оптимальных позиций (назовем его “winning_positions”, предполагая, что он выглядит вот так: [(1,2),(3,5),(4,7),...]), то поиск оптимального хода реализуется “в лоб” (да простят меня за английские комментарии):

module Main where

import Data.List (delete)

-- | Find optimal move (da,db) for game position (a,b).
-- Here, `da' and `db' are numbers that should be
-- substracted from `a' and `b', respectively.
move a b = move' a b winning_positions

-- | Find position in the list of winning positions that
-- could be reached from (a,b) by either:
-- 1)substracting solely from `a' or `b'
-- 2)substracting simultaneously from `a' and `b'
move' a b ((x,y):rest)
  | a == b = (a,b)
  | a == x = (0,b-y)
  | a == y = (0,b-x)
  | b == y = (a-x,0)
  | b == x = (a-y,0)
  | a-x == b-y = (a-x,a-x)
  | a-y == b-x = (a-y,a-y)
  | otherwise = move' a b rest

main = loop
loop =
  do putStrLn "Enter two number that describe game position and press Enter"
     l <- getLine
     let [a,b] = map read $ words l
     putStr "My move: "
     putStrLn $ show $ move a b
     loop

Дело за малым – получить список оптимальных позиций. Можно увидеть (или сходить по приведенной мною ссылке и почитать ), что “строка” является суммой “порядкового номера” позиции и “столбца”, а столбец, в свою очередь, является минимальным числом из ряда [1..], которое еще не было использовано в качестве “строки” или “столбца”.

Так и запишем (я постарался снабдить листинги гиперссылками на примеры использования задействованных функций, чтобы не перегружать текст примерами и объяснениям, так что если вы не знаете, что делают ($), map, zipWith и т.п. – кликайте на ссылки и читайте):

column = <a href="http://www.zvon.org/other/haskell/Outputprelude/zipWith_f.html">zipWith</a> (+) [1..] row
row    = not_yet_used

winning_positions = <a href="http://www.zvon.org/other/haskell/Outputprelude/zip_f.html">zip</a> row column

Осталось определить “not_yet_used” – список, в котором на позиции N стоит минимальное число, не использованное в N-1 предыдущих оптимальных позициях. Очевидно, что можно взять список [1..] и, двигаясь последовательно по списку выигрышных позиций, вычеркивать из [1..] использованные строки и столбцы. После каждого вычеркивания “выписывать отдельно” минимальное неиспользованное число (оно будет первым в оставшемся списке) и двигаться дальше. Код практически дословно повторяет сказанное:

not_yet_used = <a href="http://www.zvon.org/other/haskell/Outputprelude/map_f.html">map</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/head_f.html">head</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/D_o.html">$</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/scanl_f.html">scanl</a> remove [1..] winning_positions
  where remove lst (a,b) = <a href="http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Adelete">delete</a> b $ delete a lst

Вот и все, алгоритм реализован, и вы можете проверить, что, например, “move 12 6″ выдает правильный ход “(2,0)”, переводящий игрока в оптимальную позицию (10,6).

Теперь приглядимся повнимательнее к тому, как функции используют друг друга. Для вычисления “column” используется “[1..]” и “row”. Для вычисления “row” используется “not_yet_used”. Для нее, в свою очередь, нужны “winning_positions”. Для вычисления которой нужны … все те же “row” и “column”. Всё, круг замкнулся (см. рисунок).

Получилась эдакая змея, кусающая себя за хвост. Простите, спросите вы, но как все это может работать?

Разгадка в том, что хоть все функции и используют для вычислений бесконечные списки и возвращают бесконечные же списки результатов, но делают они это лениво – т.е. не потребляя из бесконечного списка больше элементов, чем реально необходимо для вычисления следующего элемента результата.

А запускается вся эта карусель тогда, когда “scanl” из функции “not_yet_used” выдает на-гора начало своего результата – список [1..]. Первый элемент этого списка тут же попадает в значение “row”, после чего можно вычислить первый элемент результата “column”, после чего можно вычислить первую пару из “winning_positions”, которую можно использовать для вычисления следующего значения “not_yet_used” и т.д. и т.п (см. схему после этого абзаца). При этом вам вовсе не обязательно самому рисовать подобные картинки и прослеживать зависимости – за вас это сделает компилятор

Получившийся в результате список оптимальных позиций является бесконечным во всех практических смыслах этого слова. Например, если попытаться его напечатать (”print winning_positions”), то среда исполнения будет выводить оптимальные позиции до тех пор, пока вы ее не прервете.

Причем, для операций с бесконечными списками вовсе не требуется бесконечно много памяти Если скомпилировать программу, печатающую список всех оптимальных позиций и запустить ее, то можно заметить, что она занимает в памяти около 10 мб, и это значение со временем увеличивается очень плавно. А все дело в том, что значения “winnig_positions”, выведенные на экран, уже не требуются для дальнейших вычислений и тут же собираются сборщиком мусора, равно как и значения списоков “row” и “column”. Таким образом, в любой момент времени в памяти хранится по одному значению из списков “row”, “column” и “winning_position” + в памяти находится диапазон натуральных чисел от следующего минимально-неиспользованного до максимально-использованного (его использует в своих вычислениях функция “not_yet_used”). “Удлинение” этого диапазона и вызывает увеличение объема потребляемой памяти.

А неиспользованные элементы (или непрерывные диапазоны элементов) бесконечных списков представляются в Haskell в виде так называемых thunk-ов – “ссылок” на код, который их вычислит. Когда элемент “потребляется” для какого-то вычисления, thunk заменяется на вычисленное значение. Таким образом (упрощая), для хранения списка всех натуральных чисел [1..] достаточно хранить число “1″ + thunk с описанием, как вычислить последующие числа.

Надеюсь, что это краткий экскурс в ленивые вычисления с использованием бесконечных списков оказался для вас не только забавным, но и полезным. Удачи, до новых встреч!

PS
Disclaimer: данный код не является самым умным, самым быстрым или самым оптимальным способом решения поставленной задачи.