content: % 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}
  