Divide and conquer - Revision history

Apm: added == External links ==

2024-12-27T18:17:54Z

added == External links ==

← Older revision		Revision as of 20:17, 27 December 2024
Line 43:		Line 43:
	* [[Lambda calculus encodings of algebraic data types]]		* [[Lambda calculus encodings of algebraic data types]]
	* [[Annotated lambda diagram]]		* [[Annotated lambda diagram]]

			== External links ==

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

	[[Category:Programming]]		[[Category:Programming]]

Apm: added Category:Programming

2024-12-27T18:14:04Z

added Category:Programming

← Older revision		Revision as of 20:14, 27 December 2024
Line 43:		Line 43:
	* [[Lambda calculus encodings of algebraic data types]]		* [[Lambda calculus encodings of algebraic data types]]
	* [[Annotated lambda diagram]]		* [[Annotated lambda diagram]]

			[[Category:Programming]]

Apm: /* Related */

2024-12-27T18:07:12Z

← Older revision		Revision as of 20:07, 27 December 2024
Line 42:		Line 42:

	* [[Lambda calculus encodings of algebraic data types]]		* [[Lambda calculus encodings of algebraic data types]]
			* [[Annotated lambda diagram]]

Apm at 18:06, 27 December 2024

2024-12-27T18:06:46Z

@@ Line 23: / Line 23: @@
 '''The HOF-Implementation:'''
   divideAndConquer ::
@@ Line 39: / Line 33: @@
           | indiv pb = solve pb
           | otherwise = combine pb (map dAC (divide pb))

Apm: added == Pitfall ==

2024-12-27T18:05:01Z

added == Pitfall ==

← Older revision		Revision as of 20:05, 27 December 2024
Line 23:		Line 23:

	'''The HOF-Implementation:'''		'''The HOF-Implementation:'''

			== Pitfall ==

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


	divideAndConquer ::		divideAndConquer ::

Apm: basic page

2024-12-27T17:58:58Z

basic page

New page

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