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

From Wikiversity


Functional programming (Spring 2010):

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]

Important! 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:

API[edit]

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;