A Functional Introduction To Computer Science

    1 Introduction

      1.1 Required background

      1.2 Design philosophy

    2 Starting out with Racket

      2.1 Functions in mathematics

      2.2 Function application in Racket

      2.3 DrRacket’s Interactions window

      2.4 Function definitions in Racket

      2.5 DrRacket’s Definitions window

      2.6 More types of data

      2.7 Conditional expressions

      2.8 The design recipe

      2.9 An extended example

    3 Syntax and semantics

      3.1 Syntax and grammar

      3.2 A semantic model

    4 Structures

      4.1 Syntax and semantics

      4.2 Simulating natural numbers

      4.3 Correctness

    5 Lists

      5.1 Sequences

      5.2 Lists in Racket

      5.3 Sets

      5.4 Representing sets using ordered lists

      5.5 List abbreviations

    6 Functional Abstraction

      6.1 A first example

      6.2 More functional abstraction

      6.3 Functions are values

      6.4 Syntax and semantics of ISL+

      6.5 Local bindings and scope

      6.6 Still more functional abstraction

      6.7 Simplifying Racket

    7 Efficient Representations

      7.1 Unary representation reviewed

      7.2 Binary representation introduced

      7.3 Implementing addition

      7.4 Space and time analysis

      7.5 Representing integers

    8 Trees

      8.1 From lists to trees

      8.2 Braun trees

      8.3 Tree-structured data

      8.4 Binary search trees

    9 Generative Recursion

      9.1 Greatest common divisor

      9.2 Sorting

        9.2.1 Insertion and selection sort

        9.2.2 Treesort

        9.2.3 Quicksort

        9.2.4 Bottom-up mergesort

        9.2.5 Top-down mergesort

    10 Interpreters

      10.1 Evaluating arithmetic expressions

      10.2 Adding local names

      10.3 Adding second-class functions

      10.4 Adding first-class functions

      10.5 Interlude: programs that don’t terminate

      10.6 Deferring substitution

      10.7 What’s next?