Цель данной статьи - познакомить читателя с основными идеями ФП на примере программы для решения судоку. Для простоты наложим на входные данные два дополнительных условия: решение всегда есть и его можно найти без перебора. Входные данные задаются как список списков.

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<T>
{
	public ListTag Tag { get; }
	protected MyList(ListTag tag) => Tag = tag;
}

public class Empty<T> : MyList<T>
{
	public Empty() : base(ListTag.Empty) {}
}

public class Pair<T> : MyList<T>
{
	public T Head { get; }
	public MyList<T> Tail { get; }
	public Pair(T x, MyList<T> xs) : base(ListTag.Pair)
	{
		Head = x;
		Tail = xs;
	}
}

В качестве примера использования этих классов напишем функцию, возвращающую длину списка:

void Main()
{
	int Length<T>(MyList<T> list) 
	{
		switch(list.Tag)
		{
			case ListTag.Empty:
				return 0;
			case ListTag.Pair:
				var pair = (Pair<T>)list;
				return 1 + Length(pair.Tail);
			default:
				throw new ArgumentOutOfRangeException(nameof(list.Tag));
		}
	}
	
	var list1 = new Pair<int>(1, new Pair<int>(2, new Empty<int>()));
	Console.WriteLine(Length(list1));
}

В C# можно обойтись и без свойства Tag, используя оператор "is". А так как класс Empty не имеет свойств, то в данном конкретном случае можно обойтись одним классом Pair, договорившись, что значение null будет означать пустой список.

Это был классический ООП вариант. Ближе по смыслу к ФП было бы такое определение АТД:

public abstract class MyList<T>
{
	public abstract TResult Match<TResult>(Func<TResult> empty, Func<T, MyList<T>, TResult> pair);
}

public class Empty<T> : MyList<T>
{
	public override TResult Match<TResult>(Func<TResult> empty, Func<T, MyList<T>, TResult> pair)
	{
		return empty();
	}
}

public class Pair<T> : MyList<T>
{
	private readonly T Head;
	private readonly MyList<T> Tail;
	
	public Pair(T head, MyList<T> tail)
	{
		Head = head;
		Tail = tail;
	}
	
	public override TResult Match<TResult>(Func<TResult> empty, Func<T, MyList<T>, TResult> pair)
	{
		return pair(Head, Tail);
	}
}

Использование:

void Main()
{
	int Length<T>(MyList<T> list)
	{
		return list.Match(() => 0, (x, xs) => 1 + Length(xs));
	}
	
	var list1 = new Pair<int>(1, new Pair<int>(2, new Empty<int>()));
	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 = [ [getFigure i j | j <- [0..8]] | i <- [0..8] ]

Для вычисления цифры по паре индексов просто заменяем нули на новые значения:

getFigure 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 = [ [getFigure 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 
        getFigure 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 .