О функциональном программировании на примере решения судоку
Цель данной статьи — познакомить читателя с основными идеями ФП на примере программы для решения судоку. Для простоты наложим на входные данные два дополнительных условия: решение всегда есть и его можно найти без перебора. Входные данные задаются как список списков.
puzzle = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]Прежде чем решать задачу, расскажем, что такое список.
Список
В Haskell список можно определить так:
data List = Empty
| Pair Int ListЗдесь List — имя типа, а Empty и Pair — имена конструкторов. Такие типы называются «алгебраический тип данных» (АТД). Данное определение означает, что список — это пустой список или пара, состоящая из целого числа и списка. Конструктор — это функция, создающая значение заданного типа. Имена типов и конструкторов пишутся с большой буквы (требование синтаксиса Haskell).
Нецелесообразно отдельно определять список для каждого типа элементов. Поэтому определим обобщённый тип — список элементов произвольного типа.
data List a = Empty
| Pair a (List a)Здесь a — это параметр типа. В C# аналогом будет Generic.
В C# в общем случае аналогичный тип можно определить так:
public enum ListTag
{
Empty,
Pair
}
public abstract class MyList
{
public ListTag Tag { get; }
protected MyList(ListTag tag) => Tag = tag;
}
public class Empty : MyList
{
public Empty() : base(ListTag.Empty) {}
}
public class Pair : MyList
{
public T Head { get; }
public MyList Tail { get; }
public Pair(T x, MyList xs) : base(ListTag.Pair)
{
Head = x;
Tail = xs;
}
} В качестве примера использования этих классов напишем функцию, возвращающую длину списка:
void Main()
{
int Length(MyList list)
{
switch(list.Tag)
{
case ListTag.Empty:
return 0;
case ListTag.Pair:
var pair = (Pair)list;
return 1 + Length(pair.Tail);
default:
throw new ArgumentOutOfRangeException(nameof(list.Tag));
}
}
var list1 = new Pair(1, new Pair(2, new Empty()));
Console.WriteLine(Length(list1));
} В C# можно обойтись и без свойства Tag, используя оператор «is». А так как класс Empty не имеет свойств, то в данном конкретном случае можно обойтись одним классом Pair, договорившись, что значение null будет означать пустой список.
Это был классический ООП вариант. Ближе по смыслу к ФП было бы такое определение АТД:
public abstract class MyList
{
public abstract TResult Match(Func empty, Func, TResult> pair);
}
public class Empty : MyList
{
public override TResult Match(Func empty, Func, TResult> pair)
{
return empty();
}
}
public class Pair : MyList
{
private readonly T Head;
private readonly MyList Tail;
public Pair(T head, MyList tail)
{
Head = head;
Tail = tail;
}
public override TResult Match(Func empty, Func, TResult> pair)
{
return pair(Head, Tail);
}
} Использование:
void Main()
{
int Length(MyList list)
{
return list.Match(() => 0, (x, xs) => 1 + Length(xs));
}
var list1 = new Pair(1, new Pair(2, new Empty()));
Console.WriteLine(Length(list1));
} Фактически, всё, что мы можем сделать со значением АТД — это выяснить, как оно было создано (какой из конструкторов использовался и с какими значениями аргументов). Такая деконструкция значения называется сопоставлением с образцом (pattern matching).
Функция length на Haskell будет выглядеть так:
myLength :: List a -> Int
myLength list =
case list of
Empty -> 0
Pair x xs -> 1 + myLength xsВ первой строке — необязательное объявление типа, в котором стрелка »→» означает отображение (функцию). В большинстве случаев объявление типа можно опустить, и тип будет выведен компилятором. Применение функции в Haskell имеет максимальный приоритет 10, а сложение — приоритет 6. Поэтому в последней строке не обязательно использовать скобки.
Сопоставление с образцом аргумента функции удобнее записывать по-другому:
myLength Empty = 0
myLength (Pair _ xs) = 1 + myLength xsЭто одна функция, состоящая из нескольких частей («тел») для разных вариантов входных аргументов. Так как во втором случае мы не используем первый аргумент конструктора, то его можно (и нужно в соответствии с правилами красивого кода) заменить на подстановочный знак (wildcard) »_».
Создадим экземпляр списка целых чисел:
list1 :: List Int
list1 = Pair 1 (Pair 2 (Pair 3 Empty))Здесь первая строка содержит необязательное описание типа переменной list1. В отличии от C#, в Haskell переменная — это не имя ячейки памяти, в которой хранится значение, а синоним (обозначение) для выражения справа. Вспомните, как на уроках математики мы писали «пусть z = x + y» или «обозначим z = x + y».
Создание списка выглядит слишком громоздко. Чтобы упростить, добавим оператор:
infixr 5 +:
x +: xs = Pair x xsПервая строка означает «правоассоативный инфиксный оператор с приоритетом 5». Вторая строка содержит код оператора. Её можно переписать так:
(+:) x xs = Pair x xsИли даже так:
(+:) = PairЧтобы использовать произвольный инфиксный оператор * как функцию двух аргументов, достаточно взять его в скобки: (*).
Чтобы использовать произвольную функцию двух аргументов f как инфиксный оператор, достаточно взять её в обратные кавычки (backtick): `f`.
Теперь мы можем записать создание списка более наглядно:
list1 = 1 +: 2 +: 3 +: EmptyДля вывода в консоль используется функция print:
print (myLength list1)Чтобы избавиться от скобок, введём оператор применения функции:
infixr 0 <|
f <| x = f xМы задали оператору применения функции минимальный приоритет, и сделали его правоассоативным.
С использованием этого оператора можем записать без скобок:
print <| myLength list1В данном случае разница невелика, но часто такой оператор помогает сделать код более удобным для чтения.
Вот полный код примера:
data List a = Empty
| Pair a (List a)
infixr 0 <|
f <| x = f x
infixr 5 +:
(+:) x xs = Pair x xs
myLength :: List a -> Int
myLength Empty = 0
myLength (Pair _ xs) = 1 + myLength xs
list1 :: List Int
list1 = 1 +: 2 +: 3 +: Empty
main :: IO ()
main = do
print <| myLength list1 -- 3В комментариях (--) я указываю результат вызова print. Этот и другие примеры кода можно запустить на https://play.haskell.org/
Если мы попробуем напечатать list1 в консоль с помощью функции print, то получим ошибку »No instance for (Show (List Int)) arising from a use of «print». Смысл ошибки в том, что функции print нужно преобразовать значение типа List в строку, но наш тип List не относится к классу типов (Show), которые можно преобразовать в строку.
Приблизительным аналогом классов типов в C# являются интерфейсы. Правда, в C# нет необходимости в интерфейсе IShowable, так как в базовом классе object есть метод ToString ().
Класс типов Show a определяется так:
class Show a where
showsPrec :: Int -> a -> ShowS
show :: a -> String
showList :: [a] -> ShowSЗдесь a — это параметр типа, а ShowS — синоним для типа String → String (функция, отображающая строку на строку). Специализированная функция showsPrec может использоваться для написания более эффективного кода, но мы не будем отвлекаться на её обсуждение.
Все три функции уже имеют определение по-умолчанию. При этом showsPrec определяется через show, и наоборот. Поэтому для полного определения нашего типа, как принадлежащего классу типов Show, достаточно определить showsPrec или show. Или мы можем попросить компилятор Haskell самостоятельно вывести для нас определение экземпляра класса (instance declaration), добавив к определению типа «deriving Show».
data List a = Empty
| Pair a (List a)
deriving Show
list1 :: List Int
list1 = Pair 1 (Pair 2 (Pair 3 Empty))
main :: IO ()
main = do
print list1 -- Pair 1 (Pair 2 (Pair 3 Empty))Получается не очень красиво, поэтому определим объявление экземпляра явно. Для того чтобы преобразовывать в строку значение типа List a, необходимо уметь преобразовывать в строку элемент списка. Поэтому в определении экземпляра есть предварительное условие »(Show a) =>», означающее, что тип a является экземпляром класса Show.
instance (Show a) => Show (List a) where
show Empty = "[]"
show (Pair x xs) = "[" ++ show x ++ showl xs
where
showl Empty = "]"
showl (Pair y ys) = "," ++ show y ++ showl ysЗдесь »++» — оператор конкатенации строк. Из-за сложения строк в цикле данная реализация неэффективна, но мы уже договорились не обсуждать здесь функцию showsPrec.
Итоговый код выглядит так:
data List a = Empty
| Pair a (List a)
infixr 0 <|
f <| x = f x
infixr 5 +:
(+:) = Pair
instance (Show a) => Show (List a) where
show Empty = "[]"
show (Pair x xs) = "[" ++ show x ++ showl xs
where
showl Empty = "]"
showl (Pair y ys) = "," ++ show y ++ showl ys
main :: IO ()
main = do
print <| 1 +: 2 +: 3 +: Empty -- [1,2,3]А вот так выглядит то же самое с использованием типов и операторов из базовой библиотеки:
main :: IO ()
main = do
print $ 1 : 2 : 3 : [] -- [1,2,3]Для создания списков также можно использовать генераторы списков (list comprehension):
main :: IO ()
main = do
print [1,2,3] -- [1,2,3]
print [1..5] -- [1,2,3,4,5]
print [5,4..1] -- [5,4,3,2,1]
print [(i,j) | i <- [1..3], j <- [1..3], even (i+j)] -- [(1,1),(1,3),(2,2),(3,1),(3,3)]Список — это рекурсивный тип, поэтому для работы с ним обычно используется рекурсия. Но в ФП принято вместо явного использования рекурсии использовать абстракции более высокого порядка, чем цикл или рекурсия. Основной такой абстракцией является свёртка (fold).
-- left fold
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z [] = z
myFoldl f z (x:xs) = myFoldl f (f z x) xs
-- right fold
myFoldr :: (a -> b -> b) -> b -> [a] -> b
myFoldr f z [] = z
myFoldr f z (x:xs) = f x (myFoldr f z xs)
main :: IO ()
main = do
print $ myFoldl (+) 0 [1..5] -- 15
print $ myFoldr (*) 1 [1..5] -- 120Левая свёртка использует хвостовую рекурсию, что позволяет избежать переполнения стека. В «ленивом» Haskell для этого нужно использовать строгую версию: foldl'.
Правая свёртка может применяться к бесконечным спискам. Вычисления завершатся, если в какой-то момент функции f не нужно будет вычислять значение второго аргумента.
Другие часто используемые абстракции — отображение (mapping) и фильтрация (filtering) — можно считать частным случаем свёртки.
myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x xs -> f x : xs) []
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter f = foldr (\x xs -> if f x then x:xs else xs) []
main :: IO ()
main = do
print $ myMap (*3) [1..5] -- [3,6,9,12,15]
print $ myFilter even [1..10] -- [2,4,6,8,10]Решение судоку
Забегая вперёд, скажу, что нам понадобятся 1 функция из библиотеки Data.List и 4 функции из библиотеки Data.Set. Назначение этих функций понятно из названия.
import Data.List (transpose)
import Data.Set (fromList, toList, difference, union) Для решения судоку будем использовать тот же алгоритм, который мы бы использовали, решая без помощи компьютера.
До тех пор пока не решено (судоку), вычисляем цифры:
sudoku = until solved resolveFigures Судоку решено, когда в матрице все элементы не равны нулю:
solved = all (/=0) . concatВ Haskell оператор «не равно» выглядит так »/=». Функция concat склеивает все списки в заданном списке списков (превращает список списков в плоский список).
Вычислять цифры будем по индексам строки и столбца:
resolveFigures m = [ [getFugure i j | j <- [0..8]] | i <- [0..8] ]Для вычисления цифры по паре индексов просто заменяем нули на новые значения:
getFugure i j = case m !! i !! j of
0 -> newFigure i j
x -> xЗдесь »!» — оператор получения значения по индексу. Таким образом, «m! i! j» — это j-тый элемент в i-том списке (строке) матрицы m.
Если у нас есть ровно один кандидат на позицию (список кандидатов состоит из одного элемента), то используем это значение, иначе, оставляем ноль:
newFigure i j = case candidates i j of
[x] -> x
_ -> 0 Кандидаты — это те цифры, которые не встречаются в текущей строке, столбце или квадрате:
candidates i j = toList $ difference figures $ (rows !! i) `union` (columns !! j) `union` (squares !! squareIndex)
where squareIndex = i `div` 3 * 3 + j `div` 3Здесь мы используем множества figures, rows, columns и squares.
Множество всех цифр от 1 до 9:
figures = fromList [1..9]Список множеств всех цифр в каждой строке:
rows = map fromList $ mСписок множеств всех цифр в каждом столбце:
columns = map fromList . transpose $ mНемного сложнее получить множество всех цифр в каждом квадрате.
Нам потребуется вспомогательная функция, разбивающая список на трёхэлементные списки:
chunksOf3 = take 3 . map (take 3) . iterate (drop 3)Функция iterate создаёт бесконечный список, применяя заданную функцию (первый аргумент) сначала к исходному значению (второй аргумент), затем к результату первого применения и так далее. В данном случае мы применяем функцию drop 3, которая отбрасывает первые 3 элемента списка. Например:
main = print $ take 5 $ iterate (drop 3) [1..9] -- [[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9],[7,8,9],[],[]]От каждого внутреннего списка мы берём только первые 3 элемента с помощью «map (take 3)». Всего нам нужно 3 элемента внешнего списка.
main = print $ take 3 $ map (take 3) $ iterate (drop 3) [1..9] -- [[1,2,3],[4,5,6],[7,8,9]]Для выделения квадратов 3 на 3, мы сначала делим все строки на группы по 3. Получаем список из трёх элементов вида
[[11,12,13,14,15,16,17,18,19],
[21,22,23,24,25,26,27,28,29],
[31,32,33,34,35,36,37,38,39]]
Каждый из таких элементов мы сначала делим на группы по 3 (map chunksOf3):
[[[11,12,13],[14,15,16],[17,18,19]],
[[21,22,23],[24,25,26],[27,28,29]],
[[31,32,33],[34,35,36],[37,38,39]]]
Затем транспонируем (transpose):
[[[11,12,13],[21,22,23],[31,32,33]],
[[14,15,16],[24,25,26],[34,35,36]],
[[17,18,19],[27,28,29],[37,38,39]]]
И склеиваем внутренние списки (map concat):
[[11,12,13,21,22,23,31,32,33],
[14,15,16,24,25,26,34,35,36],
[17,18,19,27,28,29,37,38,39]]
В результате каждый элемент списка содержит список из трёх «квадратов», которые мы склеиваем и превращаем в список множеств:
squares = map fromList . concat . map (map concat . transpose . map chunksOf3) . chunksOf3 $ mПроследить все преобразования в squares по шагам можно с помощью следующего кода:
import Data.List (transpose)
chunksOf3 = take 3 . map (take 3) . iterate (drop 3)
puzzle = [ [i*10 + j | j <- [1..9]] | i <- [1..9] ]
main = do
pp1 $ puzzle
pp2 $ chunksOf3 $ puzzle
pp2 $ map (map chunksOf3) . chunksOf3 $ puzzle
pp2 $ map (transpose . map chunksOf3) . chunksOf3 $ puzzle
pp2 $ map (map concat . transpose . map chunksOf3) . chunksOf3 $ puzzle
pp1 $ concat . map (map concat . transpose . map chunksOf3) . chunksOf3 $ puzzle
-- функции для печати с отступами (вместо print)
pp1 :: (Show a) => [[a]] -> IO ()
pp1 = pp show
pp2 :: (Show a) => [[[a]]] -> IO ()
pp2 = pp (showp show " ")
showp :: (a -> String) -> String -> [a] -> String
showp showf ident (x:xs) = "[" ++ showf x ++ showl xs
where
showl [] = "]"
showl (y:ys) = ",\n " ++ ident ++ showf y ++ showl ys
pp :: (a -> String) -> [a] -> IO ()
pp showf m = do
putStrLn $ showp showf "" m
putStrLn ""Осталось только собрать всё вместе, чтобы получить итоговый код нашего решения:
import Data.List (transpose)
import Data.Set (fromList, toList, difference, union)
sudoku :: [[Int]] -> [[Int]]
sudoku = until solved resolveFigures
where
solved = all (/=0) . concat
resolveFigures m = [ [getFugure i j | j <- [0..8]] | i <- [0..8] ]
where
figures = fromList [1..9]
rows = map fromList $ m
columns = map fromList . transpose $ m
squares = map fromList . concat . map (map concat . transpose . map chunksOf3) . chunksOf3 $ m
where chunksOf3 = take 3 . map (take 3) . iterate (drop 3)
candidates i j = toList $ difference figures $ (rows !! i) `union` (columns !! j) `union` (squares !! squareIndex)
where squareIndex = i `div` 3 * 3 + j `div` 3
newFigure i j = case candidates i j of
[x] -> x
_ -> 0
getFugure i j = case m !! i !! j of
0 -> newFigure i j
x -> x
puzzle = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
main :: IO ()
main = do
print $ sudoku puzzleВ итоге мы получили простой и понятный код (возможно, за исключением squares), который почти дословно повторяет словесное описание алгоритма. При этом мы нигде не использовали рекурсию явно. Конечно, для более сложных программ могут потребоваться более сложные абстракции (монады, линзы и так далее), изучение которых займёт немало времени. Главное, не использовать абстракции ради использования абстракций, а то может получиться что-то типа этого кода:
-- nubBy устраняет из списка дубли, используя заданную функцию сравнения
import Data.List (nubBy)
-- бесконечный список простых чисел
primes = nubBy (((>1).).gcd) [2..]
main :: IO ()
main = do
print $ take 30 primes Если у кого-то появилось желание больше узнать про Haskell, то можно начать с учебника на wikibooks https://en.wikibooks.org/wiki/Haskell (английский, но есть возможность переключить язык на русский). Учебник содержит упражнения, решения которых можно найти там же https://en.wikibooks.org/wiki/Category: Book: Haskell/Solutions .
