Принцип «Разделяй и властвуй», а также бесконечные потоки в Haskell

Приветствую всех читателей!
Ниже идет моя точка зрения того, как я понял главу 14 из сладов курса по Haskell у нас в университете.
Итак, сегодня мы поговорим о следующих двух темах:

• Принцип «Разделяй и властвуй»
• Работа с бесконеными потоками

Экспертов в этой области прошу комментировать и поправлять, если будут неточности. Буду рад ответить на вопросы в комментариях.

Разделяй и властвуй

Наверное вы уже много раз встречались с принципом «Разделяй и властвуй» в программировании. Если проблема элементарна, то сразу решаем её. Если нет, то делим её на более мелкие «под-проблемы» и выполняем это до тех пор, пока все проблемы не будут элементарными. После решения всех элементарных проблем, их надо обратно «соединить», чтобы получить решение к исходной проблеме.
Пусть проблема (а также все под-проблемы) имеет тип p, а все решения имеют тип s. Требуется найти функцию высшего порядка divideAndConquer которая принимает какую-либо проблему типа p и как результат выдаёт решение типа s. Для этого нам понадобятся вспомогательные функции (= элементы divideAndConquer), которые реализуют работу алгоритма divideAndConquer, а именно:

indiv :: p -> Bool

Эта функция отвечает на вопрос: «можно ли поделить проблему на несколько под-проблем?». Если да, то возвращаем True. Если нет, то данная проблема элементарна, и её можно решить с помощю функции solve.

solve :: p -> s

Как видно из названия, эта функция решает элементарую проблему и выдаёт решение типа s.

divide :: p -> [p]

Если проблема не элементарна, то делим её на некоторое множество под-проблем, т.е. из одной проблемы p делаем много проблем [p], которые решить намного проще.

combine :: p -> [s] -> s

После решения всех элементарных проблем, надо их собрать в единое решение. Для чего здесь p спросите вы? Иногда, часть проблемы уже содержит часть решения, которое необходимо использовать для окончательного ответа (это мы увидим в примере ниже).

Итак, как же выглядит эта универсальная фукнция divideAndConquer? Определение функции выглядит следующим образом:

divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s

Т.е. функция состоит из четырех основных элементов, описанных выше, и той проблемы, с которой начнется деление. На выходе имеем решение типа s. А вот и сама функция:

divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideAndConquer indiv solve divide combine initPb = dAC initPb 	where 			dAC pb 				| indiv pb = solve pb 				| otherwise = combine pb (map dAC (divide pb))

Если проблема (pb) не делится на более мелкие под-проблемы, то решаем её indiv pb = solve pb. Если делится, то делим эту проблему, решаем её и комбинирует получившиеся результаты.

Давайте на примере quickSort посмотрим как применить такую функцию. Функция быстрой сортировки принимает массив элементов, которые можно сравнивать и выдаёт массив с теми же элементами, но в отсортированном порядке:

quickSort :: Ord a => [a] -> [a]

Теперь надо бы определиться с нашими четыремя элементами алгоритма divideAndConquer конкретно для Быстрой сортировки. Проблема считается тогда не делимой (=indiv), когда длина массива меньше или равна 1. В быстрой сортировке нет как такового решения (=solve) под проблемы, т.к. если длина массива равна 1, то этот массив отсортирован. Делить (=divide) массив можно следующим образом: берем первый элемент и формируем два массива — один со всеми элементами <= первого элемента, второй со всеми элементами > первого элемента. Отсортированные массивы комбинируем (=combine) следующим образом: первый элемент помещается в середину, слева от него идут все числа меньше данного элемента, а справа все числа больше данного элемента.
Определив основные четыре состовляющие divideAndConquer, можно смело писать функцию:

quickSort :: Ord a => [a] -> [a] quickSort lst = divideAndConquer indiv solve divide combine lst 	where 		indiv ls 		= length ls <= 1 		solve			= id 		divide (l:ls)		= [[x | x <- ls, x <= l], [x | x <- ls, x > l]] 		combine	(l:_) [l1,l2]	= l1 ++ [l] ++ l2 

Этот способ можно применять не только к Quicksort, но и для других алгоритмов сортировки, например Mergesort (и не только для сортировки). Но не надо заблуждаться, что если проблему можно решить с помощью divide and conquer, то это будет самым эффективным решением. Это можно увидеть на примере чисел Фибоначчи. Функция возвращает n-ое число из ряда Фибоначчи:

fib :: Integer -> Integer fib n = divideAndConquer indiv solve divide combine n 	where 		indiv n 		= (n==0) || (n==1) 		solve n 			| n == 0		= 0 			| n == 1		= 1 			| otherwise		= error "Input argument must be >= 0" 		divide n 		= [n-2, n-1] 		combine _ [l1,l2] 	= l1 + l2

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

Заключение

Алгоритм divideAndConquer состоит из 4 состовляющих: indiv, solve, divide, combine. Если для какой-то проблемы вы можете их все определить, то можете спокойно использовать этот метод. Однако не стоит забывать, что «разделяй и властвуй» не всегда является оптимальным решением проблемы.

Бесконечные потоки

Одной из особенностей Haskell является то, что он может работать с бесконечными потоками. Поток в данном случае является синонимом «бесконечного массива» (англ. lazy list). Например, [1..] представляет собой массив всех натуральные числа. Такие потоки позволяют выполнять «отложенные вычисления» (англ. lazy evaluation).
Попробуем написать алгоритм который выдаёт все простые числа (=поток простых чисел). Простое число будем вычислять с помощью Решета Эратосфена. Идея в том, что есть массив всех натуральных числе от двух до «бесконечности». Самое левое число — всегда простое число. Каждый раз, когда мы берем простое число то вычёркиваем из списка все те числа, которые делятся на это число без остатка, т.е. начинаем с:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11...
Число 2 — простое, вычеркиваем все числа, которые деляться на 2:
2, 3, 5, 7, 9, 11...
Число 3 — простое, вычеркиваем все числа, которые делятся на 3:
2, 3, 5, 7, 11...
и т.д.

Решето (=sieve) принимает массив и выполняет вышеописанные операции:

sieve :: [Integer] -> [Integer] sieve (x:xs) = x : sieve [y | y <- xs, mod y x > 0]

Теперь поток простых чисел (=primes) можно записать следующим образом:

primes :: [Integer] primes = sieve [2..] 

Теперь при вызове primes в консоль будут выходить простые числа. Как же это работает?
primes
->> sieve [2..]
->> 2 : sieve [y | y <- [3..], mod y 2 > 0]
->> 2 : 3 : sieve [z | z <- [y | y <- [4..], mod y 2 >0], mod z 3 > 0]
->> ...
->> 2 : 3 : sieve [ z | z <- [5, 7, 9..], mod z 3 > 0]
->> ...
->> 2 : 3 : sieve [5, 7, 11, ...
->> ...

«Ну, хорошо, а дальше что?» — спросите вы. Как работать с такими потоками, какие операции можно с ними выполнять?
Есть так называемый принцип «выборки», который позволяет выбрать из бесконенчого потока лишь несколько элементов, например:

• take 5 primes ->> [2,3,5,7,11] первые 5 простых чисел
• primes !! 42 ->> 191 42ое простое число
• ((take 5) . (drop 5)) primes ->> [13,17,19,23,29] простые числа с 6го по 10ое

Принцип «фильтрации», который позволяет выбрать подмножество множества простых чисел, например:

• filter (>1000) primes ->> [1009,1013,1019,... все простые числа больше 1000
• [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... все простые числа, где встречаются три единички (реализация функции hasThreeOnes оставляется на вооброжение читателя)

Маленькое примечание к этому типу: filter (<10) primes ->> [2,3,5,7, никогда не завершит своего выполнения, т.к. filter не знает, будут ли числа меньше 10 или нет и продолжает их искать. Для возрастающих функций это можно сделать так: takeWhile (<10) primes ->> [2,3,5,7].

Принцип «трансформации», который для каждого числа потока выполняет определённое действие, например:

• [n*n | n <- primes] ->> [4,9,25,49,... поток квадратов простых чисел
• [n-1 | n <- primes] ->> [1,2,4,6,... поток предшественников простых чисел
• [sum [2..n] | n <- primes] ->> [2,5,14,27,65,90,... поток сум простых чисел

Заключение

Потоки довольно полезная вещь в функциональных языках, но использовать их надо с осторожностью. Три основных принципа для потоков:

• выборка
• фильтрация
• трансформация