The principle of "Divide and Conquer", as well as the endless streams in Haskell

Greetings to all readers!
Below is my point of view on how I understood chapter 14 of the Haskell course slides in our university.
So today we will talk about the following two topics:

• The principle of "Divide and conquer"
• Work with endless streams

Experts in this area, please comment and correct, if there are inaccuracies. I will be glad to answer questions in the comments.

Divide and rule

Probably you have already met many times with the principle of “Divide and Conquer” in programming. If the problem is elementary , then we immediately solve it. If not, then we divide it into smaller “sub-problems” and perform it until all the problems are elementary. After solving all the elementary problems, they need to be "connected" back to get a solution to the original problem.
Let a problem (as well as all sub-problems) have type p , and all solutions have type s . It is required to find a higher order function divideAndConquer which accepts any problem of type p and, as a result, produces a solution of type s . To do this, we need auxiliary functions (= elements of the divideAndConquer), which implement the work of the divideAndConquer algorithm, namely:

 indiv :: p -> Bool 

This function answers the question: “is it possible to divide the problem into several sub-problems?”. If yes, then we return True. If not, then this problem is elementary, and it can be solved using the solve function.

 solve :: p -> s 

As the name implies, this function solves the elemental problem and produces a solution of type s .
')

 divide :: p -> [p] 

If the problem is not elementary, then we divide it into some set of sub-problems, i.e. from one problem p we make many problems [p] , which are much easier to solve.

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

After solving all the elementary problems, it is necessary to assemble them into a single solution. What are you asking for here? Sometimes, a part of the problem already contains a part of the solution that needs to be used for the final answer (we will see this in the example below).

So, what does this versatile divideAndConquer divideAndConquer ? The definition of the function is as follows:

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

Those. the function consists of the four basic elements described above and the problem with which division will begin. At the output, we have a solution of type s . And here is the function itself:

 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)) 

If the problem (pb) is not divided into smaller sub-problems, then solve it indiv pb = solve pb . If it is divided, then we divide this problem, solve it and combine the resulting results.

Let's quickSort look at quickSort as an example of how to use this feature. The quick sort function accepts an array of elements that can be compared and produces an array with the same elements, but in a sorted order:

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

Now we need to decide on our four elements of the divideAndConquer algorithm specifically for Quick Sort. The problem is then considered not divisible (= indiv), when the array length is less than or equal to 1. There is no solution (= solve) for quick sorting, since if the array length is 1, then this array is sorted. To divide (= divide) an array as follows: take the first element and form two arrays - one with all the elements <= the first element, the second with all the elements> the first element. Sorted arrays are combined (= combine) as follows: the first element is placed in the middle, to the left of it are all the numbers less than this element, and to the right all the numbers are more than this element.
Having defined the main four components of divideAndConquer, we can safely write a function:

 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 

This method can be applied not only to Quicksort, but also for other sorting algorithms, for example Mergesort (and not only for sorting). But do not be mistaken that if the problem can be solved with the help of divide and conquer, then this will be the most effective solution. This can be seen in the example of Fibonacci numbers. The function returns the n-th number from the Fibonacci series:

 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 

Unfortunately, this function has exponential complexity, and there are more efficient ways to solve this problem.

Conclusion

The divideAndConquer algorithm consists of 4 indiv, solve, divide, combine : indiv, solve, divide, combine . If you can identify all of them for some problem, you can safely use this method. But do not forget that "divide and conquer" is not always the best solution.

Infinite streams

One of the features of Haskell is that it can work with endless streams. The flow in this case is synonymous with "infinite array" (eng. Lazy list). For example, [1..] is an array of all natural numbers. Such threads allow you to perform "lazy evaluation" (eng. Lazy evaluation).
Let's try to write an algorithm that produces all prime numbers (= stream of prime numbers). We will calculate the prime number using the Sieve of Eratosthenes . The idea is that there is an array of all natural numbers from two to "infinity." The leftmost number is always a prime number. Every time we take a prime number, we delete from the list all those numbers that are divisible by that number, i.e. starting with:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11...
The number 2 is a simple one; we delete all numbers that are divisible by 2:
2, 3, 5, 7, 9, 11...
The number 3 is a simple one; we delete all numbers that are divisible by 3:
2, 3, 5, 7, 11...
etc.

The sieve (= sieve) takes an array and performs the above operations:

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

Now the stream of prime numbers (= primes) can be written as follows:

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

Now when primes called, primes will appear in the console. How does this work?
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, ...
->> ...

“Well, well, and then what?” - you ask. How to work with such streams, what operations can be performed with them?
There is the so-called “sampling” principle, which allows you to select only a few elements from the infinite stream, for example:

• take 5 primes ->> [2,3,5,7,11] first 5 prime numbers
• primes !! 42 ->> 191 primes !! 42 ->> 191 42nd prime number
• ((take 5) . (drop 5)) primes ->> [13,17,19,23,29] prime numbers from the 6th to the 10th

The principle of "filtering", which allows you to select a subset of the set of primes, for example:

• filter (>1000) primes ->> [1009,1013,1019,... all primes greater than 1000
• [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... all prime numbers where there are three ones (the implementation of the hasThreeOnes function hasThreeOnes left to the reader)

A small note to this type: filter (<10) primes ->> [2,3,5,7, will never complete its execution, because Filter does not know whether numbers will be less than 10 or not and continues to look for them. For increasing functions, this can be done like this: takeWhile (<10) primes ->> [2,3,5,7] .

The principle of "transformation", which for each thread number performs a specific action, for example:

• [n*n | n <- primes] ->> [4,9,25,49,... [n*n | n <- primes] ->> [4,9,25,49,... stream of squares of prime numbers
• [n-1 | n <- primes] ->> [1,2,4,6,... [n-1 | n <- primes] ->> [1,2,4,6,... stream of predecessors of prime numbers
• [sum [2..n] | n <- primes] ->> [2,5,14,27,65,90,... [sum [2..n] | n <- primes] ->> [2,5,14,27,65,90,... stream of sums of natural numbers from two to a simple

Conclusion

Streams are quite a useful thing in functional languages, but they should be used with caution. Three basic principles for threads:

• sample
• filtration
• transformation