Divide and conquer

Source: Course "Fortgeschrittene funktionale Programmierung"
("Advanced Functional Programming") by professor Jens Knoop at TU Vienna

Implementing Divide-and-Conquer as a higher order function

The ingredients of divideAndConquer:

▸ indiv :: p -> Bool: The function indiv yields True,
if the problem instance can/need not be divided further
(e.g., it can directly be solved by some basic algorithm).

▸ solve :: p -> s: The function solve yields the
solution instance of a problem instance that cannot be
divided further.

▸ divide :: p -> [p]: The function divide divides a
problem instance into a list of subproblem instances.

▸ combine :: p -> [s] -> s: Given the original
problem instance and the list of the solutions of the
subproblem instances derived from, the function combine
yields the solution of the original problem instance.

The HOF-Implementation:

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

Pitfall

Not every problem that can be modeled as a “divide and conquer” problem is also (directly) suitable for it.
E.g. the Fibonacci function due to overlapping sub-problems.

Related

• Lambda calculus encodings of algebraic data types
• Annotated lambda diagram

External links

• https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm
• https://www.complang.tuwien.ac.at/knoop/ffp185A05_ss2022.html