A Functional Introduction To Computer Science (Part I)

8.1

← prev up next →

(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

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?

← prev up next →