Teaching Simple Constructive Proofs with Haskell Programs

Matthew Farrugia-Roberts, Bryn Jeffries, Harald Søndergaard

TL;DR

This paper explores how to teach mathematical proof-writing skills to computer science students by using Haskell programming exercises. The authors demonstrate a method of "digitizing" traditional constructive proof exercises by having students implement the core construction algorithm as a Haskell function, offering a novel approach to learning and assessment in a large university course.

What Problem Does This Paper Address?

Teaching students to write mathematical proofs, particularly constructive proofs, is a core learning outcome in many university courses, including "Models of Computation." However, traditional pen-and-paper proof exercises are difficult to digitize for large-scale assessment and feedback. This poses a challenge for educators aiming to leverage modern digital learning platforms and provide timely, automated feedback. The authors aim to bridge this gap by adapting proof-writing skills to a programming context, using Haskell as a lingua franca for both programming and mathematical concepts.

Methods

The core of the paper's method is the concept of "construction problems." These are Haskell exercises designed to mimic the constructive part of a mathematical proof. Instead of writing a formal proof, students implement a Haskell function that takes an object of one type (representing the input to a construction) and produces an object of another type (representing the output). This approach is applied across various topics in the course, including propositional logic, formal languages, and computability.

The authors leverage the Grok Academy platform for delivering these exercises. Each problem includes a description, skeleton Haskell code, and a suite of test cases. The platform provides automated feedback, allowing students to iterate on their solutions. The paper categorizes these exercises into:

  • Instance problems: Simpler exercises where students provide a specific instance of a representation.
  • Implementation problems: More complex exercises where students implement an algorithm or a general construction.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Haskell as a "lingua franca": The authors successfully use Haskell not just for programming tasks but also as a unified medium for expressing mathematical concepts and solutions across a broad syllabus.
  • "Construction problems" as a bridge: By framing Haskell exercises around implementing construction algorithms, the authors create a partial analogy to traditional constructive proofs, targeting similar skills like precision and understanding of formal objects.
  • Leveraging automated feedback: The Grok platform's ability to provide instant, automated feedback on Haskell code is a significant advantage over traditional proof exercises, enabling rapid iteration and learning.
  • Partial analogy is key: The authors acknowledge that their Haskell exercises don't fully replicate proof-writing, specifically the justification of the constructed object's properties. This highlights the need for a balanced approach.
  • Calibrating difficulty: The authors demonstrate how to vary the difficulty of exercises by shifting between instance problems and full implementation problems, allowing for scaffolding and progressive learning.

Key Results

The paper presents a catalogue of example Haskell exercises designed to target proof-writing skills. They analyze student performance on two specific exam questions (FC and LA), finding that while most students successfully complete the exercises, a small percentage (5-10%) struggle with combining Haskell features like recursive definitions and list comprehensions. This suggests that Haskell can be a barrier for some students, though the authors argue that the benefits of automated feedback and a unified learning platform outweigh this challenge.

Limitations and Future Work

  • Partial analogy: The Haskell exercises do not directly exercise the skills of analyzing and justifying one's construction, nor the skill of formalizing and explicating justifications. The authors suggest augmenting Haskell activities with opportunities for written justifications.
  • Haskell as a barrier: A small percentage of students struggle with Haskell syntax and features, potentially hindering their ability to express their understanding. Future work could investigate how to mitigate this barrier, perhaps by offering more choice in data types or focusing on clearer abstraction.
  • Open-endedness: While the exercises are "constructed response," they are not entirely open-ended in the way traditional proofs can be. The authors suggest exploring how to offer more choice in problem-solving approaches.
  • Student response to feedback: The authors note that rapid feedback might lead to "trial-and-error" without deep understanding and propose future work to investigate how students respond to feedback.
  • Higher-order constructions: The paper briefly touches on the possibility of creating Haskell exercises for higher-order proofs (e.g., related to pumping lemmas), which would be a significant extension.

Summary updated

BibTeX
@inproceedings{farrugiaroberts2022teaching,
  author = {Matthew Farrugia-Roberts and Bryn Jeffries and Harald Søndergaard},
  title = {{Teaching Simple Constructive Proofs with Haskell Programs}},
  booktitle = {TFPIE},
  year = {2022},
  url = {https://openreview.net/forum?id=U7MrdHIXDC},
}
Figure