Elementares

• Listen sind linear angeordnete Kollektionen von Werten desselben Typs.

  Unterschied zum Mengenbegriff:

  [1] /= [1,1],  [1,2] /= [2,1]
   
  

• Listen können über jeden Typ gebildet werden:

   [] :: [a]   - leere Liste, gehört zu jedem Listentyp (polymorph)
  
  
  
  
  
  
  [1,2,3] :: Num a => [a]              - Liste von Zahlen
  
  
  
  
  
  
  [[1], [2,3]] :: Num a => [[a]]       - Liste von Listen von Zahlen
  
  
  
  
  
  
  [[], [2,3]] :: Num a => [[a]]        - [] als leere Zahlenliste
  
  
  
  
  
  
  [sin, cos] :: Floating a => [a->a]   - Liste von reelen Funktionen
  
  
  
  
  
  
  [coarse_diff, fine_diff] :: [(Float->Float)->Float->Float]
  
                                       - Liste von higher order functions
  
  
  

  1 /= [1]
   
  

  Element ungleich einelementige Liste (singleton list)!

• Listen sind wichtige Datenstruktur in gesamter Informatik, aber in funktionaler Programmierung noch größere Bedeutung als in imperativer Programmierung;

  insbesondere: lazy evaluation erlaubt Arbeit mit unendlichen Listen!

• Listen sind gut verstandener mathematischer Gegenstand mit vielen nützlichen Gesetzen für einschlägige Operationen und Funktionen.

  zB:

  R. Bird:"`An introduction to the theory of lists"',Oxford Programming Research Group report PRG-56, 1986

• Listen können aufgebaut und in eindeutiger Weise zerlegt werden durch:

   [] :: [a]  - leere Liste, Basis aller Konstruktionen
  
  
  
  
  
  
  (:) :: a->[a]->[a]  - Anfügen eines Elements am Kopf der Liste
  
                      - ("cons" = "construct"-Operation)
  
  
  

  zB:

   3:[]
  
  2:(3:[])
  
  1:(2:(3:[]))
  
  
  

  (:) assoziiert rechts, also:

  1:2:3:[]  ==  1:(2:(3:[]))
   
  

  Konstruktion / Zerlegung mit (:) ist Grundlage aller Definitionen einschlägiger Operationen / Funktionen.

• Es gibt mehrere notationelle Kurzformen:
  • Aufzählung:

     [1,2,3] == 1:2:3:[]
    
    
    

    Sonderfall für Strings:

     "abc" == ['a', 'b', 'c']
    
          == 'a':'b':'c':[]
    
    
    

  • Intervalle:

     [2..5]   == [2,3,4,5]  - Schritte von +1
    
    [5..2]   == []         - Schritte von +1
    
    [5,4..2] == [5,4,3,2]  - Schritte von -1
    
    
    

    ähnlich:

     ['a','c'..'f'] == "ace"
    
    
    

    Beachte:

    [0.0,0.2..1.4] == [0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2]
           - Feierabend, wenn Obergrenze nicht exakt getroffen wird
           - (Float-Arithmetik!)
    
    [0.2,0.2..1.4] == [0.2,0.2,0.2,0.2......
           - Schrittweite von 0!
     
    

  • Listen-Komprehension: (analog: Mengenkomprehension)

    Sei l = [1,2,3]
    dann [ 2*x | x<-l ] == [2,4,6]

    genauere Betrachtung später...

• viele Standardfunktionen / -operationen

  Definition abgestützt auf [] und (:) und pattern matching.

  zB kennen wir schon:

   length :: [a] -> Int   - Länge der Liste
  
  head   :: [a] -> a     - Kopfelement
  
  tail   :: [a] -> [a]   - Rest
  
                         - head und tail sind partielle Funktionen,
  
                         - Fehler falls Liste leer!
  
  
  

  andere Beispiele:

  • Konkatenation (join, append, Vereinigung)

    zB:

     [1,2] ++ [1,3] == [1,2,1,3]
    [] ++ [1,2] == [1,2]
    [1,2] ++ [] == [1,2]
    

    also:

     (++) :: [a]->[a]->[a]
    [] ++ ys     = ys
    (x:xs) ++ ys = x : (xs++ys)

    Beispiel:

    Listenumkehr:

     reverse :: [a]->[a]
    
    reverse []     = []
    
    reverse (x:xs) = reverse xs ++ [x]
    
    
    

    (++) ist assoziative Operation mit neutralem Element [], also:

     ([1]++[2])++[3] == [1,2,3] == [1]++([2]++[3])
    
    
    

    In Haskell konventionell Assoziirung nach rechts:

     [1]++[2]++[3] == [1]++([2]++[3])
    
    
    

    (:) und (++) nicht verwechseln; Typfehler bei:

    [1]:[2,3]
    1++[2,3]
     
    

  • Konkation, Form 2 ("`flatten"')

    wirkt auf Listen von Listen:

     concat [[1,2,3],[4,5],[],[6]] == [1,2,3,4,5,6]
    
    
    

    also:

     concat :: [[a]]->[a]
    
    concat []     = []
    
    concat (x:xs) = x ++ concat xs
    
    
    

    Beachte Typen in dieser Definition:

    [] :: [[a]]
    [] :: [a]
    x  :: [a]
    xs :: [[a]]
     
    

  • Teil-Listen:

     take, drop :: Int->[a]->[a]
    
    take 0 _  = []
    
    take _ [] = []
    
    take (n+1) (x:xs) = x:take n xs
    
    
    
    
    
    
    drop 0 xs = xs
    
    drop _ [] = []
    
    drop (n+1) (x:xs) = drop n xs
    
    
    
    
    
    
    - Anwendung zum Beispiel:
    
    > take 2 "abc"
    
    "ab"
    
    > take 5 "abc"
    
    "abc"
    
    
    
    
    
    
    > drop 2 "abc"
    
    "c"
    
    > drop 5 "abc"
    
    ""
    
    
    

  • Enthalten sein:

     elem :: a->[a]->Bool
    
    elem _ [] = False
    
    elem e (x:xs) = x==e || elem e xs
    
    
    
    
    
    
    - Anwendung zum Beispiel:
    
    > elem 'a' "abc"
    
    True
    
    > elem 'x' "abc''
    
    False
    
    
    

Standard Prelude A1, Report Seite 96 ff. enthält viele weitere Definitionen, einiges daraus später!

• Dieser Teil ist auch ohne "`höhere"' Haskell-Kenntnisse fast 100% verständlich lesen!
• allgemeiner Aufbau als Haskell-Modul:

   module PreludeList     - Modulkopf
  
     (head, tail, ...)   - Verzeichnis der nach aussen angebotenen Dienste
  
                         - (Exportliste vgl. Spezifikationsteil von Ada Paketen)
  
  where                - hier geht's los
  
  
  
  
  
  
  import ...             - Verzeichnis der von anderswo importierten Dienste
  
                         - (vgl. Ada "with clause")
  
  
  
  
  
  
  infix ...              - "fixity declarations" d.h. Deklaration von
                         - Präzedenz und Assoz. der im Modul definierten
  
                         - Operatoren
  
  
  
  
  
  
  ...                    - jetzt die Definitionen ("Implementierung")
  
  
  

Beispiel PreludeList aus dem Standard-Prelude:

 -  A.1  Prelude PreludeList






- Standard list functions

module PreludeList (

head, last, tail, init, null, length, (!!),

foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,

iterate, repeat, replicate, cycle,

take, drop, splitAt, takeWhile, dropWhile, span, break,

lines, words, unlines, unwords, reverse, and, or,

any, all, elem, notElem, lookup,

sum, product, maximum, minimum, concatMap,

zip, zip3, zipWith, zipWith3, unzip, unzip3)

where






import qualified Char(isSpace)






infixl 9  !!

infix  4  `elem`, `notElem`






- head and tail extract the first element and remaining elements,

   - respectively, of a list, which must be non-empty.  last and init

   - are the dual functions working from the end of a finite list,

   - rather than the beginning.

head             :: [a] -> a

head (x:_)       =  x

head []          =  error "PreludeList.head: empty list"






last             :: [a] -> a

last [x]         =  x

last (_:xs)      =  last xs

last []          =  error "PreludeList.last: empty list"






tail             :: [a] -> [a]

tail (_:xs)      =  xs

tail []          =  error "PreludeList.tail: empty list"






init             :: [a] -> [a]

init [x]         =  []

init (x:xs)      =  x : init xs

init []          =  error "PreludeList.init: empty list"






null             :: [a] -> Bool

null []          =  True

null (_:_)       =  False






- length returns the length of a finite list as an Int.

length           :: [a] -> Int

length []        =  0

length (_:l)     =  1 + length l

   ...