Q: In blok 1 ga ik het vak Functioneel Programmeren volgen, waar u college in geeft. Ik overweeg om een reader over te nemen van een student van vorig jaar. Is dit aan te raden, of zijn er grote veranderingen in vergelijking met de reader van dit jaar?

A: Er zijn wel veranderingen, maar nou ook weer niet zoveel; een extra hoofdstuk over het vinden van types, wat extra uitwerkingen van opgaven, etc. Volgorde is wat veranderd. De nieuwe pdf staat ook op de website.

2011-2012

Q: Ik ben aan het oefenen met Haskell en er is nog iets wat ik niet helemaal begrijp. Het vinden van types van 'map map' of 'map foldr' snap ik wel. Alleen als er een punt tussen staat (functiecompositie), weet ik niet hoe je de types kan vinden. Zoals map.map. Je hebt dan 2x het type (a->b) -> [a] -> [b] en de punt is van type (b->c) -> (a->b) -> (a->c). En door eerst (a->b) in te vullen en zo verder te werken, krijg je uiteindelijk (a->c) = (a->b) -> a? ->b? . Maar als ik die manier gebruik bij concat.concat, krijg ik type a? ->a, wat niet klopt. Maar deze komt wel uit als ik eerst (b->c) invul en zo verder werk.. Mijn vraag is dan, hoe moet je deze types vinden?

A: In het geval van een expressie waarin gebruik gemaakt wordt van functiecompositie (zoals .) kun je het probleem op verschillende manieren aanpakken. In de eerste plaats kun je map . map ook lezen als (.) map map. je krijgt op deze manier wel veel type variabelen die je allemaal apart moet oplossen. iets eenvoudiger is het om bijvoorbeeld concat.concat even om te schrijven naar \aaa -> concat (concat aaa). Je ziet dan gelijk dat het type dat uit de binnenste aanroep gelijk moet zijn aan het argument van de buitenste concat aanroep. Het type van concat is

forall a . [[a]] -> a

. Kies nu voor de a voor de buitenste aanroep eens x en voor die van de binnenste y; dan krijgen we de volgende vergelijkingen:

typeOf aaa = [[y]] -- want aaa staat op de argument plaats van de binnenste aanroep
[y] = [[x]]             -- want het resultaat van de binnenste concat is het argument van de buitenste

 [x]                      -- het resultaat van het geheel.

Het type van de hele expressie is dus iets van

[[y]] -> [x]

, waarbij [y] gelijk is aan

[[x]]

, en op deze manier krijgen we

[[[x]]]->[x]

, zonder dat we nog iets verder over x te weten kunnen komen, dus

forall x .[[[x]]] -> [x]

Q: Ik begrijp eigenlijk nog steeds niet zo goed wanneer je bij functiecompositie de operator $ nodig hebt en wanneer niet. Ook van de beschrijving in de Hoogle wordt ik niet veel wijzer. Kunt u mij dit via de mail uitleggen?

A: ipv

f ( g (h x)))

kunnen we schrijven

f.g.h $ x

Ga dit zelf na aan de hand van de prioriteiten en associativiteiten.:

*Exam> :info $
($) :: (a -> b) -> a -> b    -- Defined in GHC.Base
infixr 0 $
*Exam> :info .
(.) :: (b -> c) -> (a -> b) -> a -> c    -- Defined in GHC.Base
infixr 9 .
*Exam> > ((+1) $ (+1) $ 4)::Int
6
*Exam>

We hoeven zo minder haakjes te schijven en het argument is duidelijker zichtbaar.

Q: Ik ben al een tijdje bezig met een simpel Haskell programmatje dat een javascript bestandje comprimeerd. Oftewel alle onnogige spaties, enters, commetnaar e.d. weghaalt. Toen ik hieraan begon wist ik nog niet van het bestaan van parsers af, maar nu wel. Aangezien parsers hier uitermate geschikt voor zijn, wil ik die ook graag gebruiken. Dus ik ben wat gaan proberen te spelen met de uu-parsingslib, maar het lukt me niet om een hele simpele parser te maken.

Mijn vraag is dus, hoe kan ik een haskell programmatje maken die "(test)" als invoer krijgt, en "test" als uitvoer geeft. Oftewel, een programmatje die een string omzet naar een parser, daar pParens op toepast, en vervolgens die parser terug omzet naar een string ik heb dit (onder andere) geprobeerd, maar het doet nog niet precies wat ik wil, volgens mij ligt het aan de pReturn, die niet precies een string omzet naar een parser, maar een andere soort applicative (ofzoiets???) parse.pParens.pReturn

A: De module ParserCombinators? .UU.Demo.Examples en de Prolog interpretator bevatten beide voorbeelden van een draaiend programma. Heb je daar genoeg aan?

pReturn is het zelfde als pure uit de class Functor en "lift" een functie naar een parser die de lege string herkent (in het college gebruiken we de meer sugegstieve naam pSucceed), maar wel een waarde als resultaat heeft.

{-# LANGUAGE  Rank2Types, FlexibleContexts #-}
module Test where
import Text.ParserCombinators.UU
import Text.ParserCombinators.UU.BasicInstances hiding (Parser)
import Text.ParserCombinators.UU.Utils

type Parser a = P (Str Char String LineColPos) a

run :: Show t =>  Parser t -> String -> IO ()
run p inp = do  let r@(a, errors) =  parse ( (,) <$> p <*> pEnd) (createStr (LineColPos 0 0 0) inp)
               putStrLn ("--  Result: " ++ show a)
               if null errors then  return ()
                              else  do putStr ("--  Correcting steps: \n")
                                       show_errors errors
               putStrLn "-- "
            where show_errors :: (Show a) => [a] -> IO ()
                  show_errors = sequence_ . (map (putStrLn . show))

p :: Parser String
p = pParens (pToken "test")

main = run p "(test)"

Q: Het kan zijn dat één van mijn klasgenoten u hierover al heeft gemaild, maar voor het geval dat dit niet zo is wil ik graag de volgende vraag aan u stellen. Ik volg het Functioneel programmeren dit jaar als onderdeel van mijn Twinfo-programma. Nu komt het zo uit dat in de tentamenweek een aantal andere twinfo-studenten en ik 3 tentamens op de dinsdag moeten maken, waarvan het laatste tentamen voor Functioneel Programmeren is. (De andere twee tentamens zijn voor Netwerken en Kansrekening.) Omdat dit voor ons inhoudt dat we die dinsdag dan 8 uur lang tentamens zouden moeten maken en de laatste toets van die dag Functioneel Programmeren is, kom ik naar u met de vraag of het mogelijk is dat wij het tentamen voor Functioneel Programmeren op een andere dag kunnen maken. Met mij zijn er vijf andere twinfo-studenten die in deze situatie verkeren. Ik begrijp dat dit misschien lastig te regelen is voor zes studenten, maar hoop toch dat u ons hierbij kunt helpen.

A: Ik heb contact gehad met de onderwijsdirecteur met de vraag over de te volgen strategie. Hij is van mening dat deze ongelukkige samenloop helaas onvoldoende reden is om het werk van het maken van een extra tentamen te rechtvaardigen. Ook lijkt het hem beter dat een kleiner vak, bijv numeriek?, een extra kans verzorgt. Wat ik kan aanbieden is dat jullie een uur later kunnen beginnen en een uur langer kunnen doorgaan, mits we niet uit de zaal gegooid worden. De zaal is van 8-10 nu nog net geboekt, maar dat kan nog veranderen al ziet het er daar niet naar uit. dat weten we dag ervoor redelijk zeker. Wat ik ook kan aanbieden is dat als TWIN studenten die die dag aantoonbaar 3 tentamens doen minder dan en 4 halen je toch met de herkansing mag meedoen.

Q: Ik kwam een goede vraag tegen op StackOverflow? , waarvan het antwoord mij verbaasde, of eigenlijk toch weer niet. In het college over typeclasses is ons uitgelegd dat typeclasses in ghc geïmplementeerd zijn dmv dictionaries. Dit leek mij toen gewoon een leuk weetje, met geen verdere relevantie voor het gebruik van de taal zelf.

Na het lezen van het onderstaand item, werd mij duidelijk dat het gebruik van typeclasses wel degelijk grote impact kan hebben op "statische waarden". Ik (als niet compiler-bouwer) zie hier 2 mogelijke oplossingen voor:

memoizen op de dictionary, zodat een "waarde" ook echt statisch wordt zodra het type bekend is.
automatische restrictie tijdens compilate als blijkt dat een polymorfe functie/waarde in een bepaalde toepassing maar met 1 type wordt gebruikt (dit lijkt me alleen lastig voor libraries). Helaas doen de optimalisaties van ghc geen van beiden, en moet je als programmeur hier dus zelf aan denken (zoals de beantwoorder laat zien, door bijvoorbeeld een lokale functie te definiëren, wat in ieder geval de recursieve aanroep helpt).

Ik weet niet of dit iets is om tijdens het college te behandelen, maar het is wellicht nuttig om een opmerking/waarschuwing hierover in het dictaat op te nemen.

http://stackoverflow.com/questions/7659845/will-a-value-that-has-a-type-with-class-constraints-actually-be-a-function-at-run

A: In het algmeeen is de GHC heel goed in het "specialiseren", d.w.z. het bouwen van een speciale versies van een functie, waarbij de dictionaires al "ingevuld" zijn. Eventueel kun je ook met zogenaamde pragma's aangeven voor welke functies en voor welke types in ieder geval gespecialiseerd moeten worden.

Zie verder: http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#specialize-pragma

Merk op dat de Haskell definitie juist om het probleem te voorkomen dat dit soort functies onbedoeld veel duurder zijn dan je zo op het eerste gezicht zou denken, de zogenaamde (dreaded) "monomorphims restriction" kent, d.w.z. je mag geen polymorfe waarden hebben op top niveau, anders dan functies. Geef je geen type op dat wordt een polymorfe waarde monomorf gemaakt door defaulting toe te passen. Je kunt dat zien in:

Prelude> :t repeat
repeat :: a -> [a]
Prelude> let ones = repeat 1
Prelude> :t ones
ones :: [Integer]

Er dus voor gekozen deze waarde niet te overloaden, maar hier Integer te kiezen, en ones heeft dus een monomorf type. Wil je dit niet dan kun je altijd een polymorf type expliciet specificeren:

Prelude> let {ones :: Num a => [a]; ones = repeat 1}
Prelude> :t ones
ones :: Num a => [a]
Prelude>

Op mailing lists wordt er vaak gesproken over de "dreaded" monomorphims restriction, waarbij het epitheton al aangeeft dat er op zijn minst bij velen mixed feelings zijn over deze hele gang van zaken.

*Q:*U had op maandag een voorbeeld gegeven van hoe je alle sublijsten ter lengte x kan genereren. Dat kon heel simpel door alle sublijsten te genereren en alleen die met lengte x te pakken, maar dat was niet zo efficient. Dus had u allcombs laten zien, die leek mij handig voor het practicum dus ik heb die (volgens mij) netjes overgetikt en hij doet niet wat je zou verwachten.

allcombs [1,2,3,4] !! 1 geeft [[1,2,3],[1,2],[1],[]] in plaats van [[1],[2],[3],[4]]

Ligt het probleem in de code of heb ik het verkeerd overgetypt? Hier is mijn (of eigenlijk uw) code


allCombs :: [a] -> [[[a]]]
allCombs [] = [[]] : repeat []
allCombs (x:xs) = let previous = allCombs xs
                  in [[]]:zipWith (\l r -> map (x:) l ++ r)
                     (tail previous)
                     previous

Ik heb de slides van het college aangepast.

A: Je hebt geljk, de lijst parameters voor de zipWith staan in de andere volgorde. Dus correct is bijv:

allCombs :: [a] -> [[[a]]]
allCombs [] = [[]] : repeat []
allCombs (x:xs) = let previous = allCombs xs
                 in [[]]:zipWith (\l r -> map (x:) r ++ l)
                    (tail previous)
                    (     previous)

Q: Ik heb een vraag over de berekening van het eindcijfer voor het vak Functioneel Programmeren. Er staat dat voor de tweede toets tenminste een 4 gehaald moet worden, of je kunt 'm beter niet inleveren. Nu is mijn vraag: geldt dit voor de eerste toets ook? Ik kan namelijk vanwege persoonlijke omstandigheden niet bij de toets aanwezig zijn vanmiddag.

A: Als je de cijferregeling goed bekijkt dan zie je dat het geen zin heeft de toets in te leveren als je zeker weet minder dan een 4 te halen.

Q: ik ben vergeten wat uw boodschap het eerste college precies was: je hebt recht op herkansing als je gemiddeld een 4 hebt over twee toetsen, of wanneer je je blaadje leeg inlevert/ziek bent? Geldt dit voor beide toetsen? Ofwel, als ik morgen mijn toets leeg inlever en de tweede toets gewoon maak kan ik de eerste tzt herkansen?

A: Er is geen herkansing voor de eerste toets. De herkansing geld voor het hele vak. Je hoeft echter niet in te leveren; in dat geval wordt het cijfer van t2 je voorlopige eindcijfer, en als dat >4 is kan je herkansen. Je kunt ook herkansen als je noch t1 noch t2 inlevert.

Q: Ik kan geen gebruik maken van de practicummachines; mijn login werkt niet.

A: De logins worden tegenwoordig centraal verstrekt. Wij hebben daar verder geen invloed op. Bij problemen kun je contact zoeken met de service desk die je verder help ICT service desk of Rob van den Broek.

Q: De Haskell omgeving werkt niet zoals ik had verwacht.

A: Overleg met een studentassistent om te kijken of dit aan jou ligt of aan de installatie. In het laatste geval graag een heldere melding aan de docent.

Q: Ik volg het vak functioneel programmeren voor de tweede keer. Helaas zakte ik vorig jaar op m'n tentamencijfers, maar ik had wel een voldoende voor alledrie de practica. Ik kan op de website niet vinden of ik de resultaten van vorig jaar mag laten meetellen, hoe is dat geregeld?

A: De universiteitsbrede regel is: nieuwe kansen, nieuwe inspanningen. Individuele resultaten blijven dus niet staan.

Q: Ik heb thuis het (proef)tentamen gemaakt. Als ik de code die ik heb geschreven vergelijk met de code op de uitwerkingen van het proeftentamen, dan zijn mijn uitwerkingen een stuk langer. Wat u in twee regels schrijft, daar heb ik er soms wel 4 of 5 keer meer regels voor nodig. De code werkt desondanks wel zoals het beschreven staat in de opdrachten. Natuurlijk is het zo dat wanneer ik uw antwoorden zie dat ik achteraf denk, ja logisch zo. Maar op zulke korte code komen lukt simpelweg vaak nog niet.

Mijn vraag is: Wanneer de code een stuk langer is dan noodzakelijk, maar het wel doet wat het moet doen of je er dan wel punten voor krijgt?

A: Ja, natuurlijk. Ik verwacht niet dat jullie in een paar weken volleerde Haskell programmeurs worden. Wat belangrijk is, is dat je geen blantante onzin opschrijft, en laat zien dat je goed op weg bent.

2010-2011

Q: ik heb een vraag betreffende het dictaat hoofdstuk 4. Hier staan functies die staandaar gedefineerd zijn in Helium en niet bestaan in Haskell. een paar voorbeelden: ordInt en eqList. (blz 65, 66 dictaat) Deze zijn niet / of nog niet behandeld in het hoorcollege. Is het de bedoeling dat er wel verondersteld wordt dat je dit moet weten hoe het werkt en hoe je dit moet schrijven in Haskell, of is komt dit niet aan de orde?

A: De manier waarop het hier staat is eigenlijk zoals het klasse systeem onder water werkt. Om twee lijsten te vergelijken heb je een vergelijkingsfunctie nodig voor de elementen; die wordt hier expliciet meegegeven. Nu zit eq voor lijsten toevallig in de Prelude, en is het dus niet nodig eqList (en alle andere varianten van dit soort functies) expliciet in de Prelude te stoppen. Het is echter wel goed te begrijpen wat het onderliggende mechanisme is, want soms kan je dit patroon toepassen.

Q: Ik ben de stof van de afgelopen weken aan het doorlopen en ik loop nu tegen een probleem aan; op p 35 van het dictaat staat de functie

sums (x : y : xs) = x : (x + y : xs)
sums xs = xs

hij is dus van het type [a]->[a]

zoals ik dergelijke definities begrijp zou ik zeggen dat deze twee declaraties tegenstrijdig zijn. In de tweede regel kan xs namelijk elke lijst zijn, en dus ook een lijst van de vorm (x:y:xs), waardoor er sums (x : y : xs) = (x : y : xs) zou komen te staan, wat tegenstrijdig zou zijn met sums (x : y : xs) = x : (x + y : xs).

De compiler ziet dit probleem echter niet, dus ik ga er vanuit dat ik een fout ergens maak. Weet u waar dat is?

A: De alternatieven worden van boven naar beneden geprobeerd; het laatste alternatief geld dus alleen voor lege lijsten en lijsten van 1 lang.

Q: Ik begrijp de eerste opdracht van het werkcollege 10, over de binaire boom niet. Er staat "define the corresponding data type which can be used as a map". Ik snap echter niet hoe een datatype een functie kan zijn (de map-functie). Moet ik misschien gewoon een boom definiëren en dan een aparte map-functie ervoor maken?

A: Op het college heb ik laten zien hoe de functie memo, met gebruik makend van tabulate en apply, een memoiserende versie van een functie kan maken. De boom waarin de functiewaarden worden opgeslagen speelt hierbij een cruciale rol. het gaat er hier om een soortgelijke boom te vinden, maar dan een die (de functiewarde voor de waarde) 1 in zijn wortel heeft. Het getal 0 moet nu dus apart behadeld worden. Als we dat toch doen kunnen we de zaak ook wel even uitbreiden zodat ook negatieve argumenten gememoïseerd kunnen worden.

Q: In college 10 van infofp wordt er gesproken over een Parselib.hs. Is deze ook ergens te downloaden?

A: Dit betreft een verwijzing op de allerlaatste slide. Vorig jaar heb ik deze Parsinglib.hs gebruikt in de Prolog interpretator. Dit jaar heb ik deze vervangen door de veel uitgebreidere, en gebruikersvriendelijk uu-parsinglib. De module met de afgeleide combinators is vrijwel onafhankelijk van de gebruikte implementatie van de basis-combinators. Voor het gebruik van de uu-parsinglib zie de Prolog interpretator en de source van de voorbeeld-module. De code van de core module hoort uitdrukkelijk niet tot de examenstof.