On this page:
A Functional Introduction To Computer Science (Part I)
8.1

A Functional Introduction To Computer Science (Part I)

(a flânerie by Prabhakar Ragde)

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Please do not post exercise solutions to any public forum or publicly-accessible software repository.

This is a complete draft of Part I. For Part II, look here.

    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?