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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
% lhs2TeX -verb MaxSegment.lhs > MaxSegment.tex
% lhs2TeX -math -align 33 MaxSegment.lhs > MaxSegment.tex
\documentclass{article}
\usepackage[german]{babel}
%-------------------------------= --------------------------------------------
%include ../lhs2TeX.sty
%include ../lhs2TeX.fmt
%-------------------------------= --------------------------------------------
%if style == math
%format alpha = "\alpha "
%format a1
%format an = a "_n"
%elif style == verb
%format a1 = "a$_1$"
%format an = "a$_n$"
%endif
\begin{document}
So ist |\x -> x + 1| die Nachfolgerfunktion.
Diese Aufgabe ist dem Artikel `Proofs as Programs' von Bates und
Constable entnommen. Gegeben ist eine Folge von ganzen Zahlen |[a1,
..., an]|. Finde die zusammenh"angende Teilfolge, deren Summe maximal
ist unter allen zusammenh"angenden Teilfolgen. F"ur die Folge
> seg :: [Integer]
> seg = [-3, 2, -5, 3, -1, 2]
ist die Teilfolge |[3, -1, 2]| mit der Summe |4| maximal.
Die Funktion |segments x| berechnet alle zusammenh"angenden
Segmente der Liste |x|.
> type Segment alpha = [alpha]
> segments :: [a] -> [Segment a]
> segments x = s ++ t
> where (s, t) = segments' x
Ist das Ergebnis der Hilfsfunktion |segments x| das Tupel |(s, t)|, so
enth"alt |s| alle echten Pr"afixe von |x| und |t| alle "ubrigen
Segmente von |x|.
> segments' :: [a] -> ([Segment a], [Segment a])
> segments' [] = ([], [])
> segments' (a : x) = ([a] : [ a : y | y <- s ], s ++ t)
> where (s, t) = segments' x
Die Funktion |maxSegment x| berechnet auf effiziente Weise die L"osung
f"ur das oben genannte Problem, d.h. sie realisiert die folgende
Spezifikation.
< maxSegment :: (Num a, Ord a) => [a] -> a
< maxSegment x = maximum [ sum s | s <- segments x ]
Die Vorgehensweise entspricht im wesentlichen dem oben geschilderten
Verfahren. Beachte, da"s |maxSegment []| undefiniert ist.
> maxSegment :: (Num a, Ord a) => [a] -> a
> maxSegment x = snd (maxSegment' x)
>
> maxSegment' :: (Num a, Ord a) => [a] -> (a, a)
> maxSegment' [a] = (a, a)
> maxSegment' (a : x) = (n, m `max` n)
> where (l, m) = maxSegment' x
> n = a `max` (a + l)
Zur "Ubung: erweitere |maxSegment|, so da"s nicht nur die Summe,
sondern zus"atzlich, das dazugeh"orige Segment zur"uckgegeben wird.
< min a b | a <= b = a -- vordefiniert
< | otherwise = b
\end{document}
|
