GP Course
Exercises

---++ Exercise Sets

<table style="margin:45px; width:90%; border-collapse:collapse; text-align:left;">

<tr style="border-bottom: 2px solid #6678b1; background-color: #f2f5ff;">
<th>Name</th>
<th>Submit (MM-DD hh:mm)</th>
<th>Correct</th>
<th>Notes</th>
</tr>

<tr style="border-bottom: 1px solid #ccc; vertical-align: top;">
<td>[[%ATTACHURL%/Set1.pdf][Exercise Set 1]]</td>
<td>09-18 13:15</td>
<td>09-25 13:15</td>
<td>
   * Since we haven't covered LIGD yet, don't do exercises 1(c) and 3.
   * The maximum grade is now 7.5.
</td>
</tr>

<tr style="border-bottom: 1px solid #ccc; vertical-align: top;">
<td>[[%ATTACHURL%/Set2.pdf][Exercise Set 2]]</td>
<td>09-25 13:15</td>
<td>10-02 13:15</td>
<td></td>
</tr>

<tr style="border-bottom: 1px solid #ccc; vertical-align: top;">
<td>[[%ATTACHURL%/Set3.pdf][Exercise Set 3]]</td>
<td>10-09 13:15</td>
<td>10-11 13:15</td>
<td></td>
</tr>

<tr style="border-bottom: 1px solid #ccc; vertical-align: top;">
<td>[[%ATTACHURL%/Set4.pdf][Exercise Set 4]]</td>
<td>11-11 23:59</td>
<td>--</td>
<td></td>
</tr>

<!--
<tr style="border-bottom: 1px solid #ccc; background-color: #f2f5ff;">
<td></td>
<td></td>
<td></td>
</tr>
-->

</table>

---++ Notes on Submitting

   * File format: *[[http://www.haskell.org/onlinereport/literate.html][literate Haskell]]*
   * File name: =&lt;First&gt; &lt;Last&gt; &lt;Exercise Num&gt; .lhs=
      * e.g. =AlonzoChurch1.lhs=, =EdsgerDijkstra2.lhs=, or =GuidoVanRossum3.lhs=
   * *Email* the file as an attachment to leather@cs.uu.nl *before* the specified due time


<!--

2011

   * *[[%ATTACHURL%/Set4.pdf][Exercise Set 4]]. Due before Friday, 17:00, 11 November, 2011.*
      * I have updated the written exercise in the PDF. (2011-11-09 14:00)
      * In Sec. 2.2, Ex. 1(a), when defining a so-called =Plate= datatype, think of the possible types that can be constructed for =ZigZag=.
   * [[%ATTACHURL%/Set3.pdf][Exercise Set 3]]. Due before Friday, 15:00, 7 October, 2011.
      * The functions in 1 should support all representation types as given in the "base" of each library.
      * In 2(e)(iv), define one algebra for counting =Cons= in a list containing an unknown type of value. Use that algebra to define the two functions. You can even define one function with the other.
   * [[%ATTACHURL%/Set2.pdf][Exercise Set 2]]. Due before Friday, 15:00, 30 September, 2011.
      * In 2, use the =spine= package to start from. Note that where there are differences from the slides, the =spine= package takes precedence.
      * In 4(a), give the minimum number of instances necessary for Zig and Zag to be used with all functions in =Generics.EMGM.Functions.*=. You don't need to give overloaded instances if the function uses the default.
      * In 4(b)(ii) and (iii), you should not need to do any overloading. Indeed, you can answer this without defining your own generic functions at all. Think of the types as functors and the functions as collapsing functors into a list of the elements. So =Zig a= is a functor, and in =Zig a Char=, that functor has a parameter of type =Char=. For =Zig Char b=, think of how you can convince EMGM that you really have a container of =Char= even though the parameters are in the reverse order.
   * [[%ATTACHURL%/Set1.pdf][Exercise Set 1]]. Due before Friday, 09:00, 23 September, 2011.
      * When using extensions to the standard Haskell language definition (i.e. type families, GADTs, kind signatures, etc.), be sure to list the necessary [[http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#language-pragma][language extension pragmas]] at the top of your file. See [[http://hackage.haskell.org/packages/archive/ligd/0.2/doc/html/src/Generics-LIGD-Base.html][Generics.LIGD.Base]] for how =LANGUAGE= pragmas are used by the LIGD library.
      * "LIGD representation" in Exercise 1(c) refers to everything you need to use a generic function with a given datatype. See the various versions of =rList= for the list representation in the lecture slides. You only need to give the representation for =Rep=, not =Rep1= or =Rep2=.
      * For 2(d), you might try first defining a version of =Exp= with only type indexes. Then, abstract over the recursive references (as you did in 2(b)) to produce =ExpTF=.
      * For 3, you can consider =typeInfo= to be a generic consumer function that returns a triple (perhaps =(Int, Char, [String])=). Depending on each type, you do something specific to each of the values returned. Those values will depend (1) on the type and (2) how you decide to handle each of the three results as described in the exercise. For example, if I ask you what the maximum character of the =Int= =37= is (an ill-typed question), do you tell me that (a) there is no maximum or (b) the maximum character by default is the minimum?
      * Exercise 4 calls for an "associated type" synonym. That means a type like [[http://www.haskell.org/haskellwiki/GHC/Type_families#An_associated_type_synonym_example][this example]].

-->

<!--

2010

---++ Papers for presentations

You can browse for papers to present during the course at several places. Obvious candidates are:

   * [[http://osl.iu.edu/wgp2010/][Workshop on generic programming 2010]]
   * [[http://portal.acm.org/toc.cfm?id=1596614&type=proceeding&coll=GUIDE&dl=GUIDE&CFID=102568971&CFTOKEN=47884041][Workshop on generic programming 2009]]
   * [[http://portal.acm.org/toc.cfm?id=1411318&type=proceeding&coll=GUIDE&dl=GUIDE&CFID=102568971&CFTOKEN=47884041][Workshop on generic programming 2008]]
   * [[http://portal.acm.org/toc.cfm?id=1159861&type=proceeding&coll=GUIDE&dl=GUIDE&CFID=102568971&CFTOKEN=47884041][Workshop on generic programming 2006]]

But also the ICFP proceedings sometimes contain papers about generic programming, see for example

   * [[http://portal.acm.org/toc.cfm?id=1086365&coll=GUIDE&dl=ACM&type=proceeding&idx=SERIES824&part=series&WantType=Proceedings&title=ICFP&CFID=://www.google.nl/search?client=safari&CFTOKEN=www.google.nl/search?client=safari][ICFP 2005]]

Ask the lecturers if you are interested in a special topic and need help in searching. 

Searching for generic programming in Google also gives many hits.

What do you have to think about when presenting a paper? What will we be looking at?

   * Present the problem which is dealt with in the paper. (The <b>research question</b>.)
   * Present the solution proposed by the authors. (The <b>research contribution</b>.)
   * Present how the authors arrived at the solution. (The <b>research method</b>.)
   * After we have read the paper, we should have learned something. What can we do after reading/understanding/working on the paper? You can see this as a learning goal of the paper. (The <b>intended learning outcome</b>. This is probably a slight reformulation of the research question.)
   * To assess whether or not a student has reached the learning goal, develop two questions which assess the learning goals. Use one of these in your presentation, and give us the other. If it is a good question we might reuse it in the take-home exam. (The <b>assessment</b>.)

Grading criteria:

   * You will fail the presentation assignment if at the presentation it is clear that you 
      * don't understand the paper, 
      * started reading it last night (or the night before), 
      * have no clue how it is related to the other material discussed in the course,
      * wouldn't know how to assess an intended learning outcome of the paper,
      * prepared unintelligible slides, and when presenting them managed to further confuse the audience
   * You will pass with a 6 if you manage to prepare the components mentioned above, but basically by literally copying the paper, and by going no further than the paper. Any question that is not directly answered by the paper is considered difficult.
   * You will pass with a 7 if you show deep understanding of the paper, by preparing appropriate assessments, and by answering questions about the paper confidently.
   * You will pass with an 8 if you can relate the paper to the rest of the content of the course and some of the related literature, explain the differences and similarities, etc.
   * You will pass with a 9 if you know the related literature and can critically assess the paper in the context of the literature.
   * You will pass with a 10 if your presentation can easily be turned into a follow-up research paper.

From a practical point of view:
   * make sure you don't use more than 45 minutes for your presentation. 
   * if you use slides (which we expect most or all of you will do), structure them well, and prepare them carefully.
   * remember that the audience didn't spend as much time on the paper as you did, and adapt your speed accordingly.

We will use these practical aspects to adjust your grade with plus or minus 0.5.

---++ Project

During the course you will work on a small research project related to generic programming. 

In the project you will look at compressing structured documents. 

We will introduce the projects in one of the lectures. Some possibilities are:

   * improve the generic selections library by annotating an abstract syntax tree node with the program code to which it corresponds (and release the improved lib on hackage)
   * generic programming and dependent types
   * generic bidirectionalization: bidirectionalizing EMGM; investigate the possibilities of GP in bidirectionalization techniques
   * several aspects of generics in UHC (optimisation, expressivity)
   * refactoring code such that it is more generic
   * turning (aspects of) exercise assistants into generic programs. For example, use `Scrap your nameplate' to implement strategies in the exercise assistant.
   * implementing zippers in instant generics

You will be divided into small groups. You will have regular project meetings with the teacher or other assistants.

At the end of the course we will organise a workshop at which each group will present their work on the research project. You have to hand a document describing your solution, your solution, and the slides of your presentation via submit on or before ???.

What do you have to think about when working on your project? What will we be looking at?

   * Present the problem you deal with in the project. (The <b>research question</b>.)
   * Present the solution you have arrived at. (The <b>research contribution</b>.)
   * Present how you arrived at the solution, and discuss why this is a good way to approach the research problem. (The <b>research method</b>.)

Grading criteria:

   * You will fail if you 
      * don't manage to formulate a research question
      * don't manage to find any solution at all (not even a negative result)
      * do nothing more than is suggested to you by your project supervisor, with no or hardly any result
      * show no initiative
   * You will pass with a 6 if you get some research results for your research question, but mainly by lots of pushing from the project supervisor.
   * You will pass with a 7 if you answer your research question satisfactorily
   * You will pass with an 8 if you formulate your own research question, answer it relatively independent, and can relate it to the course literature
   * You will pass with a 9 if the report you produced independently only needs little work to be turned into a research paper.
   * You will pass with a 10 if you surprise the teachers with a deep research result.

It is not uncommon that the results of your project (which is sometimes followed by a Master's thesis project) will end up in a research publication. For examples, see:

   * [From the course in 2007, followed by a Master's thesis:] Martijn van Steenbergen, José Pedro Magalhães, and Johan Jeuring. Generic selections of subexpressions. To appear in Proceedings Workshop on Generic Programming, WGP 2010, ACM, 2010.
   * [From the course in 2006, followed by a Master's thesis:] Thomas van Noort, Alexey Rodriguez, Stefan Holdermans, Johan Jeuring, and Bastiaan Heeren. A Lightweight Approach to Datatype-Generic Rewriting. In Ralf Hinze, editor, Proceedings of the ACM SIGPLAN Workshop on Generic Programming, WGP'08.
   * [From the course in 2006:] Patrik Jansson, Johan Jeuring, and students of the Utrecht University Generic Programming class. Testing properties of generic functions. In Zoltán Horváth, Viktória Zsók, and Andrew Butterfield, editors, Implementation and Application of Functional Languages, 18th International Symposium, IFL 2006, Revised Selected Papers, LNCS 4449, pages 217 - 234, 2007, © Springer-Verlag.
   * [From the course in 2006:] Johan Jeuring, Alexey Rodriguez, and Gideon Smeding. Generating generic functions. In Ralf Hinze, editor, Proceedings of the ACM Sigplan Workshop on Generic Programming, Portland, September 16, pages 23 - 32, 2006.

This years' projects:
 
   * Robert Kreuzer, Jurri&euml;n Stutterheim, Henk Erik van der Hoek: Generics in UHC/GHC; Supervisor: Pedro
   * Alessandro Vermeulen, Thijs Alkemade: Source code annotation; Supervisor: Johan
   * Bram Schuur, Ruud Koot: Zippers for instant generics; Supervisor Pedro
   * Ruben de Gooijer, Tom Hastjarjanto: Zipper in SYB in Scala; Supervisor Sean
   * Dragos Ionita: Generic bidirectionalization; Supervisor Sean
   * Calin Juravle, Andreas Resios, Steven Keuchel: Implement a regular-like library for higher-order functors (for nested datatypes); Supervisor Johan

-->
Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
pdf	Set3.pdf	manage	94.7 K	02 Oct 2012 - 10:07	JohanJeuring