Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/Notes 3
Covered topics
editList anatomy:
- creation:
- prepending;
- appending;
- concatenation;
- pair sharing:
- advantages of functional programming;
- implications of side effects in non-functional programming;
- safety copies in non-functional programming;
- proper vs improper lists;
Immutable vs immutable data types:
Identity equality vs value equality:
- Section 6.3. Equality Predicates (from Common Lisp the Language, 2nd Edition);
- Section 3.1., Booleans and Equality (from Reference: PLT Scheme);
- Section 11.5., Equivalence predicates (from R6RS);
Modeling other data structures:
- functional data structures style, wikipedia:Purely functional;
- stacks;
- trees;
- graphs;
- queues;
- tables;
- maps (associative tables) (key / value pairs);
- circular lists;
Examples
editA queue functional data structure
edit...
Recursion over lists
edit...
A dictionary functional data structure
edit...
Plain binary tree
edit...
Exercises
editFrom the the book How to Design Programs:
- Section 9., Compound Data, Part 2: Lists:
- (m) exercises 9.1.1 (lists), 9.1.3 (
add-up-3
), 9.1.4 (contains-2-doll?
); - (m) exercises 9.3.2 (
contains-doll?
),contains?
); - (m) exercises 9.5.2 (
how-many-symbols
), 9.5.3 (dollar-store?
), 9.5.4 (9.5.4
), 9.5.5 (convert
), 9.5.6 (delta
), 9.5.7 (average-price
);
- (m) exercises 9.1.1 (lists), 9.1.3 (
- Section 6., Compound Data, Part 1: Structures:
- (m) implement all the functions described in section 6.1. Structures:
make-posn
,distance-to-0
,posn-x
,posn-y
; - exercises 6.3.3 (
within-range
,reduce-range
), 6.5.2 (time->seconds
);
- (m) implement all the functions described in section 6.1. Structures:
- Section 7., The Varieties of Data:
- exercise 7.1.3 (
area
);
- exercise 7.1.3 (
- Section 10., More on Processing Lists:
- (m) exercises 10.1.2 (excessive wages), 10.1.4 (
convert-euro
), 10.1.5 (eliminate-exp
), 10.1.6 (name-robot
), 10.1.7 (recall
); - exercise 10.1.9 (
controller
); - exercise 10.2.3 (
price-of
), 10.2.4 (phone directory);
- (m) exercises 10.1.2 (excessive wages), 10.1.4 (
- Section 11., Natural Numbers:
- (m) exercise 11.2.1 (
repeat
); - (m) exercise 11.3.1 (
random-n-m
), 11.3.2 (tie-dyed
); - exercises 11.3.3 (
create-temp
), 11.3.4 (create-prices
); - (m) exercises 11.4.2 (
product
), 11.4.4 (product-from-minus-11
); - exercise 11.4.4 (
tabulate-f20
), 11.4.7 (is-not-divisible-by<=i
);
- (m) exercise 11.2.1 (
References
editReading
editFor Scheme from the book An Introduction to Scheme and its Implementation (recommended):
- please note that it might seem many topics to read, but the pages are quite short in length;
- (m) The Empty List;
- (m) Pairs and Lists (and all sections hierarchically under this one);
- (m) Quoting and Literals (and all sections hierarchically under this one);
- Making Some Objects;
- (m) Lists;
- Strings;
- Symbols (and all sections hierarchically under this one);
- Lists Again;
- (m) Type and Equality Predicates (and all sections hierarchically under this one);
Also for Scheme from the book How to Design Programs:
- please note that in order to understand the following you'll have to start by looking at the reading section in the next laboratory related with this book (in summary: you need to know function definition and control structures);
- Section 6., Compound Data, Part 1: Structures (the entire section, except maybe the Extended exercise: ... sections);
- Section 7., The Varieties of Data (the entire section, except maybe the Extended exercise: ... sections);
- Section 9., Compound Data, Part 2: Lists (the entire section);
- Section 10., More on Processing Lists (the entire section);
- Section 11., Natural Numbers (the entire section);
- Section 13., Intermezzo 2: List Abbreviations (the entire section);
For Common Lisp from the book Practical Common Lisp:
- (m) Chapter 10., Numbers, Characters, and Strings (the entire chapter);
- (m) Chapter 12., They Called It LISP for a Reason: List Processing (the sections "There Is No List", Functional Programming and Lists, and List-Manipulation Functions; optionally the entire chapter, except maybe the Mapping section);
- Chapter 13., Beyond Lists: Other Uses for Cons Cells (the entire chapter, except maybe the DESTRUCTURING-BIND section);
- Chapter 11., Collections (be selective of what you read from this chapter, and leave out what seems too advanced);
API
edit- Numbers
For Scheme:
- Section 3.2., Numbers (from Guide: PLT Scheme);
- Section 3.2., Numbers (from Reference: PLT Scheme);
- Chapter 3, Numbers (overview), Section 11.7., Arithmetic (library) (from R6RS);
For Common Lisp:
- Section 2.1., Numbers (from Common Lisp the Language, 2nd Edition);
- Chapter 12, Numbers (from CLHS);
- Symbols
For Scheme:
- Section 3.6., Symbols (from Guide: PLT Scheme);
- Section 3.6., Symbols (from Reference: PLT Scheme);
- Section 11.10., Symbols (library) (from R6RS);
For Common Lisp:
- Section 2.3., Symbols (from Common Lisp the Language, 2nd Edition);
- Chapter 10, Symbols (from CLHS);
- Booleans
For Scheme:
- Section 3.1., Booleans (from Guide: PLT Scheme);
- Section 3.1., Booleans (from Reference: PLT Scheme);
For Common Lisp:
- ???;
- Strings and characters
For Scheme:
- Section 3.4., Strings (Unicode), Section 3.5., Bytes and Byte Strings, Section 3.3., Characters (from Guide: PLT Scheme);
- Section 3.3., Strings, Section 3.4., Byte Strings, Section 3.5., Characters (from Reference: PLT Scheme);
- Section 4.2.7., Strings (syntax), Section 11.12., Strings (library) (from R6RS);
For Common Lisp:
- Pairs (conses) and lists
For Scheme:
- Section 3.8., Pairs and Lists (from Guide: PLT Scheme);
- Section 3.9., Pairs and Lists (from Reference: PLT Scheme);
- Section 4.3.2., Pairs and lists (syntax), Section 11.9., Pairs and lists (library) (from R6RS);
For Common Lisp:
- Section 1.2.2., Nil, False, and the Empty List, Section 2.4., Lists and Conses, Chapter 15, Lists (from Common Lisp the Language, 2nd Edition);
- Structures
For Scheme:
- Section 5., Programmer-Defined Datatypes (from Guide: PLT Scheme);
- Section 4, Structures (from Reference: PLT Scheme);
For Common Lisp:
- Chapter 19, Structures (from Common Lisp the Language, 2nd Edition);
- Chapter 8, Structures (from CLHS);
- Arrays (vectors)
For Scheme:
- Section 3.9., Vectors (from Guide: PLT Scheme);
- Section 3.11., Vectors (from Reference: PLT Scheme);
For Common Lisp:
- Hash tables
For Scheme:
- Section 3.10., Hash Tables (from Guide: PLT Scheme);
- Section 3.13., Hash Tables (from Reference: PLT Scheme);
For Common Lisp:
- Chapter 16, Hash Tables (from Common Lisp the Language, 2nd Edition);
- Chapter 18, Hash Tables (from CLHS);
- Boxes
Only for Scheme: