Haskell Opdrachten Taal, Wiskunde, Logica

Derde week

  1. Schrijf een functie takeTwo die de lijst bestaande uit de eerste 2 elementen van een lijst teruggeeft, of de hele lijst als die minder dan 2 elementen heeft. De aanroep takeTwo 'Piet' moet dus 'Pi' opleveren. De type-specificatie is:
    takeTwo :: [a] -> [a]
    
  2. Schrijf een functie splitUp die als eerste element een eigenschap neemt, als tweede element een lijst, en die als resultaat een paar van lijsten (ys,zs) geeft waarbij ys precies de elementen uit xs zijn die aan de eigenschap voldoen, en zs precies de elementen uit xs die niet aan de eigenschap voldoen. De type-specificatie is:
     
    splitUp :: (a -> Bool) -> [a] -> ([a],[a])
    
    De aanroep splitUp even [1..10] moet het paar van lijsten ([2,4,6,8,10],[1,3,5,7,9]) opleveren.
  3. Haskell heeft een voorgedefinieerde functie sum die de som geeft van een lijst van getallen. De type-specificatie is:
     
    sum :: Num a => [a] -> a
    
    Schrijf hiervan je eigen versie mySum.
  4. We nemen nu even aan dat we binaire relaties representeren als lijsten van paren, type [(a,a)]. Een relatie R is symmetrisch als voor elke x en y geldt dat als (x,y) in R zit, dan ook (y,x). Implementeer een functie symmetricR die nagaat of een relatie symmetrisch is. De type-specificatie is:
    symmetricR :: [(a,a)] -> Bool
    
  5. Een relatie R is reflexief op een domein A als voor elke x in A geldt dat (x,x) in R zit. Implementeer een functie reflexiveR die nagaat of een relatie reflexief is op een bepaald domein (gegeven door een lijst). De type-specificatie is:
    reflexiveR :: [a] -> [(a,a)] -> Bool
    
  6. Een relatie R is transitief als voor elke x, y en z geldt dat als (x,y) en (y,z) in R zitten, dan ook (x,z). Dit is het geval precies wanneer R.R (dat wil zeggen, de compositie van R met zichzelf) bevat is in R. Compositie van relaties wordt gedefinieerd in de slides van het college van deze week. Implementeer een functie transitiveR die nagaat of een relatie transitief is. De type-specificatie is:
    transitiveR :: [(a,a)] -> Bool
    
  7. Een relatie R is een equivalentie op een domein A als de volgende drie eigenschappen gelden: Combineer de functies uit de vorige opdrachten tot een functie equivalenceR die nagaat of een relatie een equivalentie is op een bepaald domein. De type-specificatie is:
    equivalenceR :: [a] -> [(a,a)] -> Bool
    

    NB: vanaf hier zijn de vragen bonusvragen.

  8. Binaire relaties op een domein A kunnen worden gerepresenteerd op allerlei manieren, bij voorbeeld: Schrijf conversiefuncties om de ene representatie in de andere om te zetten. De type-specificaties zijn:
    list2charfct :: Eq a => [a] -> [(a,a)] -> a -> a -> Bool
    
    charfct2list :: [a] -> (a -> a -> Bool) -> [(a,a)]
    
    Het eerste lijst-argument van charfct2list geeft het domein aan. Hier zijn een paar voorbeelden van aanroepen:
    Main> list2charfct [(1,2),(3,4)] 1 3 
    False
    Main> list2charfct [(1,2),(3,4)] 3 4 
    True
    Main> charfct2list [1..5] (<)
    [(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]
    
  9. Een andere representatie van relaties is: als karakteristieke functies van paren, dat wil zeggen, als type (a,a) -> Bool. Schrijf conversiefuncties voor converteren van type a -> a -> Bool naar type (a,a) -> Bool, en vice versa. De type-specificaties zijn:
    charfct2pairfct :: (a -> a -> Bool) -> (a,a) -> Bool
    
    pairfct2charfct :: ((a,a) -> Bool) -> a -> a -> Bool
    
  10. In het hoofdstuk over oneindige verzamelingen in het cursusboek van Partee, ter Meulen en Wall wordt beweerd dat de verzameling van alle paren van natuurlijke getallen aftelbaar is. Leg uit waarom de volgende functie een bewijs is van deze bewering (of liever, een illustratie van het bewijs):
    natPairs :: [(Integer,Integer)]
    natPairs = [ (x,z-x) | z <- [0..], x <- [0..z] ]
    

Huiswerk

Tekstbestand met alle antwoorden. Let op: de laatste drie vragen zijn bonusvragen. Deadline: maandag 19 mei, 12 uur 's middags. Per email inleveren bij Arno Bastenhof, met een cc naar Jan van Eijck.


Jan van Eijck
Last modified: Thu Apr 24 16:30:27 CEST 2008