Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/Notes 3


Discontinued due to lack of student interest.

Covered topics

edit

List 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:

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

edit

A queue functional data structure

edit

...

Recursion over lists

edit

...

A dictionary functional data structure

edit

...

Plain binary tree

edit

...

Exercises

edit

From 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);
  • 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);
  • Section 7., The Varieties of Data:
    • exercise 7.1.3 (area);
  • 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);
  • 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);

References

edit

  The next topics are already covered by the course notes and are put here only for reference, or they are useful later when working on projects.

Reading

edit

For Scheme from the book An Introduction to Scheme and its Implementation (recommended):

Also for Scheme from the book How to Design Programs:

For Common Lisp from the book Practical Common Lisp:

Numbers

For Scheme:

For Common Lisp:

Symbols

For Scheme:

For Common Lisp:

Booleans

For Scheme:

For Common Lisp:

  • ???;
Strings and characters

For Scheme:

For Common Lisp:

Pairs (conses) and lists

For Scheme:

For Common Lisp:

Structures

For Scheme:

For Common Lisp:

Arrays (vectors)

For Scheme:

For Common Lisp:

Hash tables

For Scheme:

For Common Lisp:

Boxes

Only for Scheme:

  To be finalized... ToDo list:

  • add functional data structures examples of the basic ones (stacks and queues);
  • add tree and graph modeling examples;
  • add examples of pair sharing in the case of append and cons;
  • show the cons implementation in other programming languages;