14 декабря 2012 в 23:06

Принцип «Разделяй и властвуй», а также бесконечные потоки в 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,... поток сумм натуральных чисел от двойки до простого


Заключение

Потоки довольно полезная вещь в функциональных языках, но использовать их надо с осторожностью. Три основных принципа для потоков:
  • выборка
  • фильтрация
  • трансформация
+22
6004
40
IvanP 8,0

Комментарии (14)

0
leventov, #
Маленькое примечание к этому типу: filter (<10) primes ->> [2,3,5,7, никогда не завершит своего выполнения, т.к. filter не знает, будут ли числа меньше 10 или нет и продолжает их искать.

Да вроде нет, filter ничем не отличается от других ленивых функций.

На тему «разделяй и властвуй» советую очень крутую книжку Ричарда Бёрда «Жемчужины проектирования алгоритмов: функциональный подход», почитать первые главы можно тут: oz.by/books/more10282958.html
+2
barmaley_exe, #
Вижу, Вас минусуют (это не я :-) ), но никто не отписался, за что.

Да вроде нет, filter ничем не отличается от других ленивых функций.
Автор имеет в виду, что простых чисел, меньших 10 конечное число, но filter никогда об этом не узнает.
0
nsinreal, #
Кстати, можно вопрос, а нет там какого-нибудь filterInSorted, takeWhile?
0
barmaley_exe, #
takeWhile упоминался в посте, а какого поведения ожидать от filterInSorted, и чем это поможет? Предикат-то не обязан зависеть от упорядоченности.
0
IvanP, #
функциа filter обязана проверить каждый элемент листа который ей передаётся, в то время как takeWhile берет элемент за элементом пока условие выполняется. Функция filter в любом случае никогда не завершит своего выполнения при работе с бесконечными потоками (ведь даже filter (>100) primes никогда не завершается, и понятно почему). Можно рассматривать primes как строго возрастающую функцию, и только благодаря этому свойству takeWhile (<10) primes «фильтрует» список правильно.
+1
edem, #
Принцип «Разделяй и властвуй», а также бесконечные потоки в Haskell

Поэтичное название статьи)
0
Qrilka, #
А можно поинтересоваться, в каком это универе курс по Haskell?
Может слайды доступны публике?
0
yupic, #
Вот здесь в первых лекциях рассказывается о Haskell. В том числе и о бесконечных потоках, тоже строится бесконечная последовательность простых чисел.
0
Qrilka, #
вопрос-то был не где в принципе рассказывается, а какой именно университет
+1
IvanP, #
Технический Университет Вены. Курс «Функциональное программирование». Слайды на немецком языке, поэтому публиковать не стал (ну и чтобы хабраэффект не создавать). Если кому интересно, все слайды тут: http://www.complang.tuwien.ac.at/knoop/lehre/ws1213/fp185A03/fp185A03_ws1213_121204.pdf
0
barmaley_exe, #
На матмехе СПбГУ есть аж 2 полугодовых курса по нему. Они не обязательны и не для всех, но желающих не выгоняют.
Слайдов, видимо, нет.
+1
Gokjer, #
[sum [2..n] | n < — primes] ->> [2,5,14,27,65,90,… поток сум простых чисел

Стоит отметить, что это не поток сумм простых чисел, а поток сумм натуральных от двойки до простого.
0
IvanP, #
Спасибо, поправил!
0
grigorym, #
Для того, чтобы решить задачу методом «разделяй и властвуй», нужно еще доказать, что агрегация решений подзадач даст решение всей задачи.

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.