1/opdr1.txt

   1    Functional Query Language (FQL)
   2
   3 In dit practicum gaan jullie een aantal operaties op tabellen implementeren.
   4 Met deze operaties kun je vragen (queries) opschrijven zoals dat ook kan met SQL.
   5 Het gaat in dit practicum voornamelijk om het manipuleren van lijsten.
   6
   7 Algemene hints
   8
   9     * Lijstcomprehensies komen goed van pas bij het schrijven van de functies.
  10     * Test na iedere functie. Pas functies die je net geschreven hebt toe op
  11       geschikte waarden om te controleren of ze doen wat je verwacht.
  12     * Schrijf veel kleine functies. Het werk van de functies is goed op te
  13       splitsen in subfuncties. Soms kan je zo'n subfunctie dan ook weer gebruiken
  14       op een andere plek.
  15     * Gebruik standaardfuncties. Zie de Haskell prelude.hs. Standaardfuncties
  16       kunnen veel werk uit handen nemen en voor veel taken zijn functies beschikbaar.
  17       Kijk ook eens in de module List (/usr/lib/hugs/libraries/List.hs).
  18     * Ga uit van correcte invoer. Je mag er vanuit gaan dat de parameters aan
  19       de functies correct zijn. Bijvoorbeeld bij join (zie verderop) mag je
  20       aannemen dat de tabellen precies één veld gemeenschappelijk hebben.
  21     * Kijk eens wat transpose doet met een lijst van lijsten. Om transpose
  22       te kunnen gebruiken moet je de volgende regels bovenaan (!) je programma
  23       opnemen. Vervang hierin FQL door de naam van je bestand (zonder .hs natuurlijk):
  24
  25       module FQL where
  26
  27       import List
  28
  29       ... <en hier de rest van je programma>
  30
  31 Het type van een tabel
  32
  33 Een database-tabel wordt gerepresenteerd door een lijst van lijsten van strings.
  34 Het eerste element is de lijst met veldnamen van de kolommen. De rest van de
  35 lijst bevat alle records van de tabel in een lijst. Ieder element van de lijst
  36 stelt een record voor en is op zijn beurt weer een lijst met waarden voor iedere
  37 kolom. Voor het gemak worden alle gegevens voorgesteld door strings.
  38
  39 type Table = [[String]]
  40
  41 Voorbeelden van tabellen
  42 Twee voorbeeldtabellen laten zien hoe waarden van het type Table er uitzien. De
  43 eerste tabel bevat verschillende Haskell compilers en voor ieder de naam van de
  44 universiteit of het bedrijf waar de compiler ontwikkeld wordt. De tweede tabel
  45 relateert de universiteiten en bedrijven met landen en steden.
  46
  47 compilers :: Table
  48 compilers =
  49   [ ["Compiler", "Universiteit/bedrijf"]
  50   , ["Helium", "Universiteit Utrecht"]
  51   , ["NHC", "University of York"]
  52   , ["GHC", "Microsoft Research"]
  53   , ["Hugs", "Galois Connections"]
  54   , ["Hugs.NET", "Galois Connections"]
  55   , ["O'Haskell", "Oregon Graduate Institute"]
  56   , ["O'Haskell", "Chalmers University of Technology"]
  57   , ["HBC", "Chalmers University of Technology"]
  58   ]
  59
  60 locaties :: Table
  61 locaties =
  62   [ ["Universiteit/bedrijf", "Land", "Stad"]
  63   , ["Universiteit Utrecht", "Nederland", "Utrecht"]
  64   , ["University of York", "Engeland", "York"]
  65   , ["Microsoft Research", "Engeland", "Cambridge"]
  66   , ["Galois Connections", "Verenigde Staten", "Beaverton"]
  67   , ["Oregon Graduate Institute", "Verenigde Staten", "Beaverton"]
  68   , ["Chalmers University of Technology", "Zweden", "Goteborg"]
  69   ]
  70
  71 Het tonen van een tabel
  72
  73 Standaard kijkt Hugs niet naar newlines in een string. Om dat voor elkaar te
  74 krijgen moet je de functie putStr er op toepassen:
  75
  76 Prelude> "regel 1\nregel 2"
  77 "regel 1\nregel 2"
  78 Prelude> putStr "regel 1\nregel 2"
  79 regel 1
  80 regel 2
  81
  82 Als we in Hugs de tabel tonen dan krijgen we:
  83
  84 Database> putStr ( show compilers )
  85 [["Compiler","Universiteit/bedrijf"],["Helium","Universiteit Utrecht"],
  86 ["NHC","University of York"],["GHC","Microsoft Research"],["Hugs","Galois C
  87 onnections"],["Hugs.NET","Galois Connections"],["O\'Haskell","Oregon Gradua
  88 te Institute"],["O\'Haskell","Chalmers University of Technology"],["HBC","C
  89 halmers University of Technology"]]
  90
  91 Dat ziet er niet overzichtelijk uit. De eerste functie die jullie schrijven
  92 laat de tabel mooier zien. Daarbij zijn de veldnamen visueel gescheiden van
  93 de records en zijn de kolommen uitgelijnd. Dit is het type van de te schrijven
  94 functie:
  95
  96 writeTable :: Table -> String
  97
  98 En dit is een voorbeeld van het gebruik:
  99
 100 Database> putStr (writeTable compilers)
 101 +---------+---------------------------------+
 102 |Compiler |Universiteit/bedrijf             |
 103 +---------+---------------------------------+
 104 |Helium   |Universiteit Utrecht             |
 105 |NHC      |University of York               |
 106 |GHC      |Microsoft Research               |
 107 |Hugs     |Galois Connections               |
 108 |Hugs.NET |Galois Connections               |
 109 |O'Haskell|Oregon Graduate Institute        |
 110 |O'Haskell|Chalmers University of Technology|
 111 |HBC      |Chalmers University of Technology|
 112 +---------+---------------------------------+
 113
 114 Zorg ervoor dat de uitvoer er precies zo uit ziet als hier.
 115
 116 Hint
 117
 118 Schrijf een functie die de breedte van een kolom kan bepalen. Houd daarbij
 119 niet alleen rekening met de waarden (zoals Helium en Hugs.NET) maar ook met
 120 de veldnaam (Compiler). De veldnaam zou immers langer kunnen zijn dan elk
 121 van de waarden.
 122
 123 Selecteren van kolommen
 124
 125 De volgende stap is het selecteren van bepaalde kolommen uit een tabel, ook
 126 wel projectie genoemd. De functietoepassing project velden tabel levert een
 127 nieuwe tabel op waarbij alleen die kolommen uit tabel overblijven die genoemd
 128 worden in velden. Hier is het type:
 129
 130 project :: [String] -> Table -> Table
 131
 132 En zo zou je de functie kunnen gebruiken:
 133
 134 Database> putStr (writeTable (project ["Stad", "Land"] locaties))
 135 +---------+----------------+
 136 |Stad     |Land            |
 137 +---------+----------------+
 138 |Utrecht  |Nederland       |
 139 |York     |Engeland        |
 140 |Cambridge|Engeland        |
 141 |Beaverton|Verenigde Staten|
 142 |Beaverton|Verenigde Staten|
 143 |Goteborg |Zweden          |
 144 +---------+----------------+
 145
 146 Merk op dat Stad en Land nu in omgekeerde volgorde staan vergeleken met de
 147 oorspronkelijke tabel.
 148
 149 Selecteren van records
 150
 151 Net hebben we kolommen geselecteerd, nu gaan we rijen (records) selecteren.
 152 De expressie select veld conditie tabel levert een nieuwe tabel op waarin
 153 alleen die rijen overblijven waarvan de waarde voor het gegeven veld aan de
 154 conditie voldoet. De conditie is een functie die een boolean resultaat
 155 oplevert. De functie die jullie moeten schrijven heeft het type:
 156
 157 select :: String -> (String -> Bool) -> Table -> Table
 158
 159 En hier is een voorbeeld van het gebruik (selecteer de compilers waarvan
 160 de naam 3 lang is):
 161
 162 Database> putStr (writeTable (select "Compiler" ((==3) . length) compilers))
 163 +--------+---------------------------------+
 164 |Compiler|Universiteit/bedrijf             |
 165 +--------+---------------------------------+
 166 |NHC     |University of York               |
 167 |GHC     |Microsoft Research               |
 168 |HBC     |Chalmers University of Technology|
 169 +--------+---------------------------------+
 170
 171 Combineren van tabellen
 172
 173 De laatste bewerking die jullie maken is het combineren van twee tabellen.
 174 Voorwaarde is dat de twee tabellen precies een veld gemeen hebben. Voor de
 175 bovenstaande voorbeeldtabellen geldt dat; het gemeenschappelijke veld is
 176 Universiteit/bedrijf. De combinatie van de tabellen heeft als veldnamen de
 177 veldnamen van de eerste en daarbij die van de tweede behalve het
 178 gemeenschappelijk veld. Dus als de eerste tabel n velden heeft en de tweede
 179 tabel m dan heeft de gecombineerde tabel n+m-1 velden. De records in de
 180 nieuwe tabel zijn alle combinaties van de records uit beide tabellen waarbij
 181 het gemeenschappelijke veld dezelfde waarde heeft. De naam van de tabel is
 182 een combinatie van de namen van de twee tabellen. In het voorbeeld kun je
 183 zien wat de bedoeling is.
 184
 185 join :: Table -> Table -> Table
 186
 187 Dit voorbeeld laat de werking van join zien. Merk op dat Stad en Land van
 188 Chalmers nu twee keer voorkomen omdat daar nu eenmaal twee compilers vandaan komen.
 189
 190 Database> putStr (writeTable (join compilers locaties))
 191 +---------+---------------------------------+----------------+---------+
 192 |Compiler |Universiteit/bedrijf             |Land            |Stad     |
 193 +---------+---------------------------------+----------------+---------+
 194 |Helium   |Universiteit Utrecht             |Nederland       |Utrecht  |
 195 |NHC      |University of York               |Engeland        |York     |
 196 |GHC      |Microsoft Research               |Engeland        |Cambridge|
 197 |Hugs     |Galois Connections               |Verenigde Staten|Beaverton|
 198 |Hugs.NET |Galois Connections               |Verenigde Staten|Beaverton|
 199 |O'Haskell|Oregon Graduate Institute        |Verenigde Staten|Beaverton|
 200 |O'Haskell|Chalmers University of Technology|Zweden          |Goteborg |
 201 |HBC      |Chalmers University of Technology|Zweden          |Goteborg |
 202 +---------+---------------------------------+----------------+---------+
 203
 204 Hints
 205
 206     * Schrijf een functie die bepaalt welke veldnaam twee tabellen
 207       gemeenschappelijk hebben.
 208     * Lijstcomprehensies!
 209
 210 Tot slot
 211
 212 Samenvattend moeten de volgende functies geschreven worden:
 213
 214 writeTable :: Table -> String
 215 project    :: [String] -> Table -> Table
 216 select     :: String -> (String -> Bool) -> Table -> Table
 217 join       :: Table -> Table -> Table
 218
 219 Bovenstaande functies vormen nu samen een kleine "functional query language".
 220 Bij het gebruik van die query language heb je de beschikking over de volledige
 221 kracht van Haskell waardoor bijvoorbeeld geneste queries geen probleem zijn.
 222 Als uitsmijter een query die alle functies combineert om de Haskell
 223 compilers te bepalen die aan universiteiten worden gemaakt. Een extra
 224 tabel wordt gebruikt om aan te geven of iets een universiteit of een bedrijf is:
 225
 226 query :: Table
 227 query =
 228     project ["Compiler"]
 229       (select "Soort" ((==) "Universiteit")
 230         (join compilers (join locaties soort)))
 231
 232 soort :: Table
 233 soort =
 234   [ ["Universiteit/bedrijf", "Soort"]
 235   , ["Universiteit Utrecht", "Universiteit"]
 236   , ["University of York", "Universiteit"]
 237   , ["Microsoft Research", "Bedrijf"]
 238   , ["Galois Connections", "Bedrijf"]
 239   , ["Oregon Graduate Institute", "Universiteit"]
 240   , ["Chalmers University of Technology", "Universiteit"]
 241   ]
 242
 243 Database> putStr (writeTable query)
 244 +---------+
 245 |Compiler |
 246 +---------+
 247 |Helium   |
 248 |NHC      |
 249 |O'Haskell|
 250 |O'Haskell|
 251 |HBC      |
 252 +---------+
 253