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

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.