Softwerkskammer

 

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

  • 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
1
2
3
4
5
6
7
8
9
10
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:

1
2
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:

1
2
3
4
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
    ```haskell
    ghci> head []

*** Exception: Prelude.head: empty list

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
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
 
```haskell
(++) :: [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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
8
9
10
11
12
13
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
1
2
3
4
5
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
1
2
3
4
5
6
7
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.

 

Wiki Links

Europaweite Veranstaltungen 2019
Jahreskalender von Konferenzen, Open Spaces, BarCamps und anderen Veranstaltungen