文档介绍：Structuring Depth
First Searc h Algorithms in Hask ell
Da vid J
King John Launc h bury
Departmen t puting Science Departmen t puter Science and Engineering
Univ ersit y of Glasgo w Oregon Graduate Institute of Science
T ec hnology
Glasgo w G
QQ
UK Bea v erton
Oregon
USA
gnik
dcs
gla
ac
uk jl
cse
ogi
edu
Abstract wide v ariet y of DFS algorithms binations of standard
comp onen ts
passing explicit in termediate v alues from one
to the other
The result is quite di
eren t from traditional
Depth
rst searc h is the k ey to a wide v ariet y of graph algo
presen tations of these algorithms
and w e obtain a greater
rithms
In this pap er w e express depth
rst searc h in a lazy
degree of mo dularit y than is usually seen
functional language
obtaining a linear
time implemen ta
tion
Unlik e traditional imp erativ e presen tations
w e use the
Of course
the idea of splitting algorithms in to man y sep
structuring metho ds of functional languages to construct al
arate phases connected b y in termediate data structures is
gorithms from individual p onen ts
This st yle
not new
T o some exten t it urs in all programmi ng
of algorithm construction turns out to b e quite amenable to
paradigms
and is esp mon in functional lan
formal pro of
whic h w e exemplify through a calculational
guages
What is new
ho w ev er
is applying the idea to graph
st yle pro of of a far from ob vious strongly
p o
algorithms
The di
cult y is alw a ys to
nd a su
cien tly
nen ts algorithm
exible in termediate v alue whic h allo ws a wide v ariet y of
algorithms to b e expressed in terms of it
Classi
cations
Computing P aradigms
functional program
There is another c hallenge here
ho w ev er
Graph algorithms
ming
En vironmen ts
Implemen tations
and Exp erience
ha v e long b een p o orly handled in functional languages
It
programming
graph algorithms
has not b een at all clear ho w to express suc h