Kapitel 4 - Zusammenfassung Teil 1

Heute haben wir den ersten Teil des vierten Kapitels ("Functional programming") besprochen. Es geht vor allem um Funktionen die auf Listen operieren.

Chapter 4. Functional programming (Teil I)

• Thinking in Haskell
• A simple command line framework
• Warming up: portably splitting lines of text
  • A line ending conversion program
• Infix functions
  • Working with lists
  • Basic list manipulation
  • Safely and sanely working with crashy functions
  • Partial and total functions
  • More simple list manipulations
  • Working with sublists
  • Searching lists
  • Working with several lists at once
  • Special string-handling functions
  • Exercises

Thinking in Haskell

Zwei Aspekte:

• Funktionale statt imperative Denkweise
• Haskells Standardbibliotheken kennenlernen
  • Heute vor allem Operationen auf Listen

A simple command line framework

import System.Environment (getArgs)

interactWith function inputFile outputFile = do
  input <- readFile inputFile
  writeFile outputFile (function input)

main = mainWith myFunction
  where mainWith function = do
          args <- getArgs
          case args of
            [input,output] -> interactWith function input output
            _ -> putStrLn "error: exactly two arguments needed"

        -- replace "id" with the name of our function below
        myFunction = id

Neu:

• do Notation
• Kommandozeilenargumente via getArgs

Warming up: portably splitting lines of text

Problem:

• Unterschiedliche Zeilenumbrüche: LF, CR, CRLF
• lines arbeitet nicht zuverlässig, z.B. Windows-Datei auf Unix

splitLines [] = []
splitLines cs =
    let (pre, suf) = break isLineTerminator cs
    in  pre : case suf of 
                ('\r':'\n':rest) -> splitLines rest
                ('\r':rest)      -> splitLines rest
                ('\n':rest)      -> splitLines rest
                _                -> []

isLineTerminator c = c == '\r' || c == '\n'

Neu:

• lines: Teilt einen String in eine Liste von Zeilen
• break: Teilt eine Liste an der ersten Stelle, die das Prädikat erfüllt

A line ending conversion program

Lösung:

fixLines :: String -> String
fixLines input = unlines (splitLines input)

Diese Funktion ins Framework einsetzen => Konvertierungswerkzeug

Neu:

• unlines: Gegenstück zu lines, setzt ein Liste von Zeilen zusammen

Infix functions

• In Backticks eingefasste Funktionsnamen werden zwischen dem 1. und 2. Argument verwendet
• Nur syntaktischer Zucker
• Backticks erfüllen auch nur diesen einen Zweck
• Geht anscheinend nur mit Funktionen mit genau zwei Parametern

Neu / Beispiele für Infix-Funktionen auf Listen:

3 `elem` [1,3,4,8]
"foo" `isPrefixOf` "foobar"
"needle" `isInfixOf` "haystack full of needle thingies"
"end" `isSuffixOf` "the end"

Working with lists

• Listen sind die vielleicht wichtigste Datenstruktur
• Sammlung der elementaren Operationen auf Listen
• Modul: Data.List (teilweise im Prelude reexportiert)

Basic list manipulation

• Elementare Operationen:
  • length
  • null
  • head
  • tail
  • last
  • init
• Verkettete Listen
• Unendliche Listen möglich

Safely and sanely working with crashy functions

Problem:

• head tail last init werfen Fehler bei leerer Liste

ghci> head []
*** Exception: Prelude.head: empty list

Lösung:

• Vorher auf leere Liste prüfen
• null benutzen, nicht etwa length xs == 0

Partial and total functions

• total function: liefert für jedweden Input ein gültiges Ergebnis
• partial function: Ergebnis nicht definiert für bestimmte Inputs

More simple list manipulations

(++) :: [a] -> [a] -> [a]  -- "append"
"foo" ++ "bar" == "foobar"

concat :: <a class="internal" href="/wiki/lernfp/a">a</a> -> [a]
concat <a class="internal" href="/wiki/lernfp/123">1,2],[3</a> <a class="internal" href="/wiki/lernfp/456">4],[5],[6</a> == <a class="internal" href="/wiki/lernfp/123456">1,2],[3],[4],[5],[6</a>

reverse :: [a] -> [a]
reverse "foo" == "oof"

and :: [Bool] -> Bool
and [True,False,True] == False
and [] == True

or :: [Bool] -> Bool
or [False,False,False,True,False] == True
or [] == False

all :: (a -> Bool) -> [a] -> Bool
all odd [1,3,5] == True
all odd [] == True

any :: (a -> Bool) -> [a] -> Bool
any even [3,1,4,1,5,9,2,6,5] == True
any even [] == False

Working with sublists

take :: Int -> [a] -> [a]
take 3 "foobar" == "foo"

drop :: Int -> [a] -> [a]
drop 3 "xyzzy" == "zy"

splitAt :: Int -> [a] -> ([a], [a])
splitAt 3 "foobar" == ("foo","bar")

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile odd [1,3,5,6,8,9,11] == [1,3,5]

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile even [2,4,6,7,9,10,12] == [7,9,10,12]

span :: (a -> Bool) -> [a] -> ([a], [a])
span even [2,4,6,7,9,10,11] == ([2,4,6],[7,9,10,11])

break :: (a -> Bool) -> [a] -> ([a], [a])
break even [1,3,5,6,8,9,10] == ([1,3,5],[6,8,9,10])

Searching lists

elem :: (Eq a) => a -> [a] -> Bool
2 `elem` [5,3,2,1,1] == True
2 `notElem` [5,3,2,1,1] == False

filter :: (a -> Bool) -> [a] -> [a]
filter odd [2,4,1,3,6,8,5,7] == [1,3,5,7]

isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
"foo" `isPrefixOf` "foobar" == True

[2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9] == True

".c" `isSuffixOf` "crashme.c" == True

Working with several lists at once

zip :: [a] -> [b] -> [(a, b)]
zip [12,72,93] "zippity" == [(12,'z'),(72,'i'),(93,'p')]

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (+) [1,2,3] [4,5,6] == [5,7,9]

• Varianten zip3 bis zip7 für mehr als zwei Listen
• Variadische Funktionen in Haskell
  • Zumindest in Haskell 98 nicht möglich
  • Haskell 2010 bietet die Möglichkeit

Special string-handling functions

lines "foo\nbar" == ["foo","bar"]

unlines ["foo", "bar"] == "foo\nbar\n"

words "the  \r  quick \t  brown\n\n\nfox" == ["the","quick","brown","fox"]

unwords ["jumps", "over", "the", "lazy", "dog"] == "jumps over the lazy dog"

Organisatorisches

Wir haben uns wieder für kommenden Dienstag verabredet. Markus wird den nächsten Abschnitt "How to think about loops" vorbereiten, inklusive der Aufgaben. Sprich: bei "Anonymous (lambda) functions" aufhören.