blob: 88e96eec039926aa341a1c9cd3737b810c7f2105 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
||Miranda programming example - topological sort
topsort :: [(*,*)] -> [*]
||topsort takes a list of pairs representing a partial order - where
||the presence of (u,v) in the list means that u precedes v in the
||ordering - and returns a total ordering consistent with the
||information given - that is if (u,v) is in the input data, then u will
||come before v in the output list.
topsort rel = tsort (carrier rel) rel
||the carrier of a relation is the set of all the elements related by it
tsort c r = [], if c=[]
= error "inconsistent data for tsort", if m=[]
= a : tsort (c--[a]) [(u,v)|(u,v)<-r; u~=a], otherwise
where
a = hd m
m = (c -- ran r)
||remarks on the above
|| - it is an invariant that c contains the carrier of relation r
|| - m is the set of elements of c with no predecessor in r
||the error case will arise if the input data contains a cycle - i.e.
||if there is an element that directly or indirectly precedes itself.
||a set is here represented as a list without duplicates
||the standard function mkset removes duplicates from a list
dom r = mkset [u|(u,v)<-r] ||domain of a relation
ran r = mkset [v|(u,v)<-r] ||range of a relation
carrier r = union (dom r) (ran r)
union x y = mkset (x++y)
|
