8
$\begingroup$

I am supposed to be holding a tutorial session in an Undergraduate Haskell Course, which is also supposed to be a first course in programming for a few of the students. Ideally, the tutorial should be interesting, interactive and inviting problem solving skills.

My audience is a group of Undergraduate students, a large number of which are mathematically oriented and a few graduate students, majoring in Computer Science. For the undergraduate students, it can be assumed that quite a few of them are new to programming or CS in general. And functional programming is new to almost everyone. This tutorial is part of a course they are all attending - the aim of which is to introduce programming.

I am wondering what sort of things I could cover in such a tutorial. Some ideas I had are these:

  • A sudoku solver
  • A Brain**** Interpretter
  • An Arithmetic Expression Parser and Interpretter
  • Discussing a data structure which the students have not seen before - like binomial heaps, or red black trees

What other things could I try? Functional Programming specific applications are especially welcome.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Go with the sudoku solver man. Easy to explain and easy to implement as well. and welcome to the site because, you know, you are here :P $\endgroup$
    – Jay
    Sep 13, 2017 at 4:25
  • 3
    $\begingroup$ Well, idk if I have a project idea for you, but based on your updated description, I think you can immediately reject your last three ideas. If most of your audience is new to programming, I don't think they'll either appreciate, care, or have the background to understand those three mini-projects. I would also recommend not approaching this from the perspective of "how can I introduce these students to Haskell/functional programming" -- I'd approach it from the perspective of "how can I introduce these students to programming" and ignore the people who are already familiar with CS. $\endgroup$
    – Michael0x2a
    Sep 13, 2017 at 5:44
  • $\begingroup$ wait, a f word is allowed in a question? $\endgroup$
    – Jay
    Sep 13, 2017 at 11:44
  • $\begingroup$ Welcome to Computer Science Educators! Not an answer, but all of those projects strike me as very ambitious for a novice programmer, though if they're not programming it (it's merely a demonstration), then have at it. $\endgroup$
    – Ben I. ♦
    Sep 13, 2017 at 11:53
  • 1
    $\begingroup$ If you can't tackle the problems in 10 minutes yourself, don't expect beginners to do so in 1 hour. $\endgroup$
    – Michel Billaud
    Sep 14, 2017 at 14:48

2 Answers 2

Reset to default
6
$\begingroup$

The ideas in your question are far too difficult, for a one hour introduction.

Yesterday I had a look at Haskell and learnt some. I have over 30 years programming experience (20 years professional). Have experience with functional programming. Yet it took me several hours, and did not get far enough to be able to do your suggestions.

Mathematics

You say that your students have a maths background.

Take advantage of this. Choose some math problems. That Haskell is ideally suited to solve. And explain why you are doing this.

Ensure that you have more than you think you will need, as some students will be much faster than you expect, but don't expect to use them all.

There are some good ideas here https://stackoverflow.com/a/15110828/537980 also some of the other answers, to the same question: sort, search, interpreter (this one may take too long), factorial.

Avoid bad examples

Don't do problems that are more difficult in a functional language than in a procedural one (Reversing a list, using procedural techniques, in $O(n)$, is easy. If by using functional they will probably get a $O(n^2)$ solution, and $O(n)$ is hard, then you are teaching a disadvantage on day one.)

Fibonacci is, I think $O(2^n)$, for simple recursive implementations.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

I did it in $O(n)$ once, that was the day I learnt a lot about caching. It was hard, it took me a whole day.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Any suggestions on what math problems I could talk about? $\endgroup$
    – Agnishom Chattopadhyay
    Sep 15, 2017 at 2:40
  • $\begingroup$ Added examples, counter example, and a link. $\endgroup$
    – ctrl-alt-delor
    Sep 15, 2017 at 8:04
  • $\begingroup$ On the other hand, if it's a demo rather than an exercise, a functional $O(n)$ Fibonacci can be just fibhelper 0 a _ = a; fibhelper n a b = fib (n-1) b (a+b); fib n = fibhelper n 0 1. (Although I suspect an idiomatic Haskell version would use a lazy infinite sequence and take the nth element). $\endgroup$
    – Peter Taylor
    Sep 15, 2017 at 10:31
  • $\begingroup$ @PeterTaylor very good. However you made an error: you call you called fib with 3 arguments. I changed it to fibhelper, tested it, thought it through and it worked. Fixed code fibhelper 0 a _ = a; fibhelper n a b = fibhelper (n-1) b (a+b); fib n = fibhelper n 0 1 $\endgroup$
    – ctrl-alt-delor
    Sep 15, 2017 at 12:01
  • $\begingroup$ They are not at all too difficult if you are being guided and can evaluate code during the tutorial to follow along. Parsers in Haskell are amazingly elegant, but also have an air of practicality that can help keep novices interested. A really simple arithmetic expression parser and evaluator is just one line: expr = "(" *> expr <**> ("+" $> (+) <|> "*" $> (*)) <*> expr <* ")" <|> decimal. This also gives the opportunities to talk about some very useful Haskell operators and the importance of the little details in formal grammar definitions. 1 hour should be enough to cover 1 line of code. $\endgroup$
    – Steven Armstrong
    Feb 20, 2019 at 16:47
1
$\begingroup$

You want an approach that aligns to the problems typed functional programming languages like Haskell lend themselves well to. That is to say, Category Theory + Tensor data. So the best problems to solve would likely be those involving linear algebra.

Example:

  • Start with implementing scalar arithmetic (custom types and functions and all. Intro to Monads / Maybe for NaNs and such)(1 hour)
  • next ask them to build on the last example but implement vectors (again, all custom types, higher order functions)(1 hour)
  • next ask them to do the same but with Matrix (Kernels, Images, custom types, higher order functions)(1 hour)
  • next ask them to do the same but a linear solver (so det, eigenvectors and values)(1 hour)
  • finally ask them implement Principal Components Analysis (so learn about files and loading data)(1 hour)
  • leave them with a question at the end to further build off the work:
    • What is the principal component of a tensor? (if they coded things right, they'll have a joy of exploration )
    • How would you implement formulas and derivative functions? (abstract a part of the linear solver from before)
    • How would you implement graphs and graphing algorithms? (matrix implementation vs association list)
    • How would you rewrite the library for Tensors of infinite size, or how would you implement dynamic programming problems? (intro to functional reactive streams)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.