Softwerkskammer

 

Real World Haskell - Chapter 4. Functional programming (Teil I)

Heute haben wir den ersten Teil des vierten Kapitels 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.