Divide and conquer
Source: Course "Fortgeschrittene funktionale Programmierung"
("Advanced Functional Programming") by professor Jens Knoop at TU Vienna
Contents
[hide]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.
