Teaching Introductory Functional Programming Using Haskelite

Learning functional programming requires learning a substitution-based computational model.While substitution should be a familiar concept from high-school algebra, students often have difficulty applying it to new settings, such as recursive definitions, algebraic data types and higher-order functions.Step-by-step interpreters have been shown to help beginners by clarifying misconceptions and improving understanding.This paper reports on the experience of using a step-by-step tracing interpreter for a subset of Haskell while teaching an introductory functional programming course at the University of Porto.We describe the use of the interpreter, present some feedback obtained from students, reflect on the lessons learned and point directions for further work. Context The courseProgramao Funcional (CC1005) is an undergraduate course offered by the Computer Science Department at the Faculty of Science of the University of Porto.The course is compulsory for first year Computer Science majors, who have already taken an introductory programming course in Python.These make up the majority of our students, but the course is also offered to students from other backgrounds, who may not have had previous programming experience.Teaching Introductory Functional Programming Using Haskelite Lecture Topics Expressions and values.Step-by-step evaluation.The Haskell interactive interpreter (GHCi).Some examples with arithmetic operations and functions from the Haskell Prelude.Types as collections of values.Type assignment.Basic types for numbers, booleans and characters.Structured types for lists, tuples and functions.Polymorphic functions.Overloading and type classes.Defining functions using equations.Conditional expressions and guards.Patternmatching with multiple equations.Patterns over tuples and lists.Case expressions and lambda expressions.More about lists.De-sugaring lists into constructors.Arithmetic sequences.List comprehensions.Strings as a special case of lists.Case study on list comprehensions: implementing the Caesar Cipher.Recursive definitions.Recursion over integers.Structural recursion over lists.Examples (sum, product, length).Higher-order functions as abstractions of common recursion patterns.Some examples: map, filter, takeWhile, dropWhile.Folding functions for lists: foldr and foldl.Folds as structural transformations of lists.Infinite lists.Producing infinite lists using numeric sequences.Lazy evaluation for processing infinite lists (e.g.mapping and filtering).Recursive definitions of infinite lists.Useful functions from the Prelude (repeat, cycle, iterate).Interactive programs.Actions versus values.The IO type constructor.Basic IO actions.Combining IO actions using do-notation.Complete programs and batch compilation.10 Case study on programming with IO: implementing John Conway's Game of Life.11 Live coding example: determining the N most common words in a text.12 Live coding example: solving the 8 Queens Puzzle.13 Defining new data types.Declaring enumeration types.Using constructors as expressions and in patterns.Constructors with arguments.Recursive data types.14 Case study on recursive data types: implementing a tautology checker.15 Binary search trees.16 AVL binary search trees.17Proving properties about programs using equational reasoning and induction.