Exercise index of this lecture   Alphabetic index   Course home   

Exercises and solutions
Introduction to Functional Programming in Scheme


1.1   Installing a Scheme System  

There are many different implementations of Scheme - Scheme Systems - around. It is important for you to install one of them, and to be able to use the installed Scheme system throughout the functional programming part of this course. It is your own choice which Scheme system you wish to use. This exercise is intended to help you, inform you about possibilities, and to locate possible software on the internet.

Racket comes both with a modern and pedagogically supportive IDE - DrRacket - and a more naked Scheme engine (with a REPL - a read-eval-print loop). Racket is probably the Scheme system in most widespread use today. Earlier, Racket was known as PLT Scheme.

Chez Scheme is another nice alternative. It comes as a commercial system, and as a free variant. As of now (August 2018) the commercial system has been turned in to an open-source project at github. The free variant is called Petite Chez Scheme. Direct download link for Petite Chez Scheme: for windows (version 8.4, reviewed August 2018), and for other platforms. Chez Scheme is made by the author of the book The Scheme Programming Language, Kent Dybvig.

Independent of the Scheme system you use, it is recommended to develop programs in a two-pane setup. In one pane you write your Scheme source programs. In the other, you run the REPL (Read-Eval-Print-Loop) - the Scheme interpreter. There must be (will be) flexible ways to load the Scheme program (incrementally or totally) from the source pane to the REPL pane. DrRacket supports this setup.

I always use Scheme from my favorite text editor, which happens to be GNU Emacs. There is a simple addition to your .emacs file which may be helpful, in case you want to program in Scheme using Emacs.

When you have installed a Scheme system, be sure to give it a try. Start with some existing examples (from a possible example dir, from the text book, or from these notes). Load the Scheme forms into your REPL and evaluate them.


1.2   Testing functional programs  

Tesing is important in every programming paradigm.

Discuss testability of a program written in the functional paradigm, in contrast to a program written in the imperative programming paradigm.

A few years ago I wrote a paper Systematic Unit Testing in a Read-eval-print Loop. You may consult this paper for your inspiration.


1.3   A Proper List Predicate * 

The Scheme function (predicate) pair? tells if its parameter is a pair (constructed by cons). The function null? tells if its parameter is the empty list. The function list? tells if its parameter is a proper list. In this exercise, write your own version of list? Let us call our function proper-list?

Intuitively, a proper list is empty, or it is 'ended by' an empty list (by following the cdr chain).

You may want to read about pairs and lists in the Scheme Report.

Can you write your predicate without thinking (and programming) in terms of a while loop?

Can you write your predicate without using if or cond?

Is your function efficient? What is the time complexity?

Please - consider these questions carefully.

Solution

Here is a solution programmed with or and and:

(define (proper-list? x) (or (null? x) (and (pair? x) (proper-list? (cdr x)))))

It is, of course, also possible to write the function using if.

(define (proper-list-1? x) (if (null? x) #t (if (pair? x) (proper-list-1? (cdr x)) #f)))

This version is more verbose, and less elegant. Both versions are memory efficient (tail recursive). Notice, however, that it is rather costly to use the proper list predicate, because it will have to iterate to the end of the cdr chain to find out if the list is proper or not. There are no possible shortcuts as long as we rely on (single) linked lists.


1.4   Construction of symbolic expressions * 

Construct the symbolic expressions illustrated on this page via the cons primitive in Scheme. The entities named a through h should be symbols. As a help, the rightmost part of the structure is made by (cons 'g 'h) . 'g is equivalent to (quote g) , meaning that g is not evaluated, but taken for face value.

Experiment with h being the empty list, which is denoted '().

Try to use a proper list function, such as length, on your structures. Can you make sense of the result?

Solution

The following is a name binding form with the left and right branch of the structure:

(let ((left (cons (cons 'a 'b) (cons 'c 'd))) (right (cons (cons 'e 'f) (cons 'g 'h)))) (cons left right))

It is, of course, also possible to make one nasty expression with cons'es:

(cons (cons (cons 'a 'b) (cons 'c 'd)) (cons (cons 'e 'f) (cons 'g 'h)))

Please notice the way the Scheme interpreter prints the value of the expression. Try find the rule it applies for printing.


1.5   Every second element of a list ** 

Write a function, every-second-element, that returns every second element of a list. As examples

  (every-second-element '(a b c)) => (a c)
  (every-second-element '(a b c d)) => (a c)

Do you see any use of this function when we work with property lists?

It is often worthwhile to go for a more general solution than actually needed. Therefore, program (every-nth-element n lst) where n >= 1 and lst is a proper list.

Can you define every-second-element in terms of every-nth-element?

Solution

;; Return every second element of list, starting with the first element.
(define (every-second-element lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) (list (car lst)))
        (else (cons (car lst) (every-second-element (cddr lst))))))

; Return every n-th element of lst. Assume as a pre-condition that n >= 1.
(define (every-nth-element n lst)
  (if (shorter-than? n lst)
      (list (car lst))
      (cons (car lst) (every-nth-element n (list-tail lst n)))))

; Expensive variant.
(define (shorter-than? n lst)
  (< (length lst) n))

; Does lst have n elements, or fewer?
(define (shorter-than? n lst)
  (or (and (null? lst) (>= n 0))
      (and (not (null? lst)) (shorter-than? (- n 1) (cdr lst)))))

; An alternative with cond
(define (shorter-than? n lst)
  (cond ((null? lst) (>= n 0))
        ((not (null? lst)) (shorter-than? (- n 1) (cdr lst)))))

; Return every n-th element of lst. Assume as a pre-condition that n >= 1.
(define (every-nth-element n lst)
  (cond ((null? lst) '())
        ((shorter-than? n lst) (list (car lst)))
        (else (cons (car lst) (every-nth-element n (list-tail lst n))))))

(define (every-second-element lst)
  (every-nth-element 2 lst))

; Does not work - calls for currying.
; (define every-second-element (every-nth-element 2))

The function every-second-element is useful to extract the keys or values of a property list.


1.6   Creation of association lists * 

Program a function pair-up that constructs an association list from a list of keys and a list of values. As an example

  (pair-up '(a b c) (list 1 2 3))

should return

  ((a . 1) (b . 2) (c . 3))

Think of a reasonable solution in case the length of the key list is different from the length of the value list.

Solution

; Return the association list formed by keys from key-list and values from value-list.
; Terminate when the shortest of the lists is exhausted.
(define (pair-up key-list value-list)
  (if (or (null? key-list) (null? value-list))
      '()
      (cons
       (cons (car key-list) (car value-list))
       (pair-up (cdr key-list) (cdr value-list)))))


1.7   Association lists and property lists * 

Association lists have been introduced at this slide. An association list is a list of keyword-value pairs (a list of cons cells).

Property lists are closely related to association lists. See the slide about property lists. A property list is a 'flat list' of even length with alternating keys and values.

The property list corresponding to the following association list

  ((a . 1) (b . 2) (c . 3))

is

  (a 1 b 2 c 3)

Program a function that converts an association list to a property list. Next, program the function that converts a property list to an association list.

Solution

;; Make and return an association list from a property list plist.
(define (propertylist-to-alist plist)
  (let ((lgt (length plist)))
   (cond ((null? plist) '())
         ((= 1 lgt) (error "propertylist-to-a-list called with list of odd length. A property list is always of even length"))
         ((>= lgt 2) (cons (cons (car plist) (cadr plist)) (propertylist-to-alist (cddr plist)))))))

;; Make and return a property list from an association list.
(define (alist-to-propertylist alist)
  (cond ((null? alist) '())
        (else (cons (car (car alist)) (cons (cdr (car alist)) (alist-to-propertylist (cdr alist)))))))


1.8   The get-prop function for property lists * 

The R5RS Scheme functions assoc, assq, and assv access pairs in association lists. In this exercise we will write a similar function for property lists. More specifically, write a function get-prop with the following signature:

(get-prop key property-list)

The function should return the value of key in property-list. Like assoc, get-prop should return #f if key is not found in property-list. Here is an example REPL session with get-prop:

> (define weekday-plist (list 'monday 1 'tuesday 2 'wednesday 3 'thursday 4 'friday 5 'saturday 6 'sunday 7))
> (get-prop 'wednesday weekday-plist)
3
> (get-prop 'sunday weekday-plist)
7
> (get-prop 'january weekday-plist)
#f

How will you handle the case where the property list is malformed - a property list with an odd number of elements?

Discuss pros and cons of property lists and get-prop, compared to association lists and assoc.

Does the #f value, returned in cases where we do not find the key, bother you?

Solution

Here is a possible solution:

(define (get-prop key property-list)
  (cond ((null? property-list) #f)
        ((null? (cdr property-list))
           (error "Malformed property list"))
        ((equal? key (car property-list))
           (cadr property-list))
        (else (get-prop key (cdr (cdr property-list))))))

I see a number of problems and issues with property lists and get-prop:

The last observation could give rise to an alternative solution, which returns a list of (key value) in case key is found, and #f if the key is not found:

(define (get-prop key property-list)
  (cond ((null? property-list) #f)
        ((null? (cdr property-list))
           (error "Malformed property list"))
        ((equal? key (car property-list))
           (list key (car (cdr property-list))))
        (else (get-prop key (cdr (cdr property-list))))))

However, this requires allocation of two new cons cells (in contrast to association lists, where no new cons cell allocation is necessary). Please understand this.


1.9   Parameter passing in Scheme * 

Familiarize yourself with the parameter passing rules of Scheme by trying out the following calls:

  ((lambda (x y z) (list x y z)) 1 2 3)
  ((lambda (x y z) (list x y z)) 1 2)
  ((lambda (x y z) (list x y z)) 1 2 3 4)
  ((lambda (x y z . r) (list x y z r)) 1 2 3)
  ((lambda (x y z . r) (list x y z r)) 1 2)
  ((lambda (x y z . r) (list x y z r)) 1 2 3 4)
  ((lambda r r) 1 2 3)
  ((lambda r r) 1 2)
  ((lambda r r) 1 2 3 4)

Be sure that you can explain all the results


1.10   A calendar language - Some calendar functions **** 

Design a small Lisp language (in Scheme) for calendars and appointments. A calendar can contain a number of appointments. An appointment is characterized by an appointment text, a starting time and an ending time. Times have the usual constituents: Year, month, day, hour, and minute.

A calendar can also contain other calendars recursively (as in a Composite design pattern).

In addition to the design of the Lisp Calendar language, you are requested to write a number of processing functions, including a function that presents a calendar in HTML.

In this assignment we distinguish between:

You are asked to program the following functionality on calendars and appointments:

In case of inaccuracies in the formulations of this exercise, please state the conditions under which you have created you solution.


1.11   A counterpart to list-tail ** 

The Scheme function list-tail returns the n'th tail of a list:

  > (list-tail '(a b c d e)  2)
 (c d e)
  > (list-tail '(a b c d e)  0)
 (a b c d e)
 > (list-tail '(a b c d e)  4)
 (e)

Program your own version of list-tail. Call it my-list-tail.

Next, program a function list-prefix which is a prefix counterpart to list-tail. (list-prefix lst n) returns a prefix of the list of length n:

 > (list-prefix '(a b c d e)  2)
 (a b)
 > (list-prefix '(a b c d e)  4)
 (a b c d)
 > (list-prefix '(a b c d e)  0)
 () 

Do not just use reverse and/or length in clever ways. Make 'a real implementation' of list-prefix.

Reflect on the difference between these two functions. Which one is most expensive in terms of memory allocation?

Solution

Here are my functions:

(define (my-list-tail lst n)
  (if (= n 0)
      lst
      (my-list-tail (cdr lst) (- n 1))))

(define (list-prefix lst n)
  (if (= n 0)
      '()
      (cons (car lst) (list-prefix (cdr lst) (- n 1)))))

Notice that we must allocate memory to the result in list-prefix, whereas my-list-tail returns part of the original list (without allocating additional space).


1.12   The function butlast ** 

R5RS has functions such that list-ref and list-tail. (list-ref lst n) returns element number n in a list, (list-tail lst k) returns a suffix of list (omitting k elements). In this exercise we will program a function butlast. (butlast lst) returns all elements of lst apart from the last element. Thus, butlast computes the prefix of the list consisting of all elements but the last one. Needless to say, butlast assumes as a precondition that the input list is non-empty.

Let us notice that it is harder to compute the prefix of a list than a suffix of a list. Why?

The following implementation of butlast is tempting, but inefficient (quick and dirty):

  (define (butlast lst)
    (reverse (cdr (reverse lst)))))

Now, program butlast with a single traversal of the list.

Can you generalize butlast to compute the prefix of a list appart from the last n elements:

  (define (but-n-last lst n)
     ...))

Please consider the similarity between but-n-last and list-prefix from one of the other exercises.

Solution

Here is an implementation of butlast and but-n-last:

(define (butlast lst)
  (cond ((null? lst)
           (error "Cannot apply butlast on an empty list"))
        ((null? (cdr lst))  ; a list of a single element
           '())
        (else (cons (car lst) (butlast (cdr lst))))))

(define (but-n-last lst n)
  (cond ((< (length lst) n)
           (error "The list is too short for but-n-last"))
        ((= (length lst) n)
           '())
        (else (cons (car lst) (but-n-last (cdr lst) n)))))
  


1.13   Lexicographic photo file naming *** 

Imagine that we have a collection of photo files, named arbitrarily. We also have a list of photo file names (or photo path names) which represents a desired order of the photos. In this exercise we wish to copy the collection of photos to a new destination. At the new destination, the photo files must be renamed lexicographically, relative to the given list of photo names. By that we mean that the name of the first photo file should be "AAA", the next "AAB", the twenty sixth "AAZ", the twenty senventh "ABA", and the last "ZZZ". With this kind of naming, most photo playing devices will show the photos in the desired order (because it will sort the photos alphabetically before showing them).

In the scenario above we have used names of three characters. The number of digits can/should be adopted to the number of photo files. In addition we have used the alphabet of capital letters from 'A' to 'Z'. Other alphabets may, of course, be possible.

Write a function

   (next_photo_name current-photo-name)

which returns the name after current-photo-name, in lexicographic order. Thus, for example

  (next_photo_name "A") => "B"
  (next_photo_name "AA") => "AB"
  (next_photo_name "AAAZ") => "AABA"
  (next_photo_name "HIJK") => "HIJL" 

Make a wise decision about the value of (next_photo_name "ZZZ").

Your function next_photo_name should be recursive. The function is simple in case the last letter in the string is lower than the last letter in the alphabet. A recursive solution is used if the last letter in the string is equal to the last letter of the alphabet.

For test purposes, write a function

  (list-of-photo-names first-name n) 

that generates a list of n photo names, each with the same number of letters as in first-name. As an example

  (list-of-photo-names "AAA" (* 26 26 26))

should generate the full list of all 17576 three letter photo file names from "AAA" to "ZZZ".

Given the functions next-photo-name and list-of-photo-names it is relatively simple to plug it into a useful file copy function, such as this function:

  (define (copy-photos! source-photo-name-list target-photo-name-list source-path destination-path)
    (for-each
      (lambda (source-photo-name target-photo-name)
        (let* ((source (string-append source-path source-photo-name))
               (destination (string-append destination-path target-photo-name)) 
              )
         (if (not (file-exists? destination))
             (copy-file source destination)
             (display-message "Destination file exists" destination "- NO copy made."))
        )
      )
      source-photo-name-list target-photo-name-list))
  
  (copy-photos! 
    some-photo-list
    (list-of-photo-names "AAA" (length some-photo-list))
    ...)

Notice that this function is imperative, a named accordingly (with an exclamation suffix in the function name). Notice also the use of file-exists?, copy-file and display-message (all of which are non R5RS procedures). In the sketch above we assume that a three-letter file length will be appropriate.

Solution

Here is my solution. I assume that I know the number of letters in the alphabetic photo names. Alternatively, I could compute the necessary number of letters (by calculating log26(photo-list-lengt) and rounding up), where log26 is the logorithm function with base 26.

; RETURN the lexigraphically next string name (of the same string length as alpha-name-str) relative to alpha-name-str
(define (next-photo-name alpha-name-str)
  (next-photo-name-given-length alpha-name-str (string-length alpha-name-str)))

; The function doing the real work. str-lgt is the string length of the string this-alpha-name-str
(define (next-photo-name-given-length this-alpha-name-str str-lgt)
  (if (or (empty-string? this-alpha-name-str) (<= str-lgt 0))
      ""
      (let* ((this-alpha-name-list (string->list this-alpha-name-str))
             (last-ciffer (list-ref this-alpha-name-list (- str-lgt 1)))
             (first-ciffers (butlast this-alpha-name-list)))
        (if (char<? last-ciffer #\Z)
            (string-append (list->string first-ciffers) (string (integer->char (+ (char->integer last-ciffer) 1))))
            (string-append (next-photo-name-given-length (list->string first-ciffers) (- str-lgt 1)) "A")))))

; Generate a list of n photo names, starting with alpha-name (and all of the same string length as alpha-name)
(define (list-of-photo-names alpha-name n)
  (if (> n 0)
      (cons alpha-name 
            (list-of-photo-names (next-photo-name alpha-name) (- n 1)))
      '()))

; A couple of simple helping functions:

(define (empty-string? str)
  (string=? str ""))

(define (butlast lst)
  (cond ((null? lst)
           (error "Cannot apply butlast on an empty list"))
        ((null? (cdr lst))  ; a list of a single element
           '())
        (else (cons (car lst) (butlast (cdr lst))))))


(define (copy-photos! source-photo-path-list target-photo-path-list source-path destination-path)
  (for-each
    (lambda (source-photo-name target-photo-name)
      (let* ((source (string-append source-path source-photo-name))
             (destination (string-append destination-path target-photo-name)) 
            )
       (if (not (file-exists? destination))
           (copy-file source destination)
           (display-message "Destination file exists" destination "- NO copy made."))
      )
    )
    source-photo-path-list target-photo-path-list))

(copy-photos! 
    some-photo-list
    (list-of-photo-names \"AAA\" (length some-photo-list))
    ...)


1.14   A music language in Scheme **** 

Design a simple and small Lisp (Scheme) language for music. In this assignment, music is basically modelled in terms of notes and pauses. A note is characterized by a pitch value, a duration, and an instrument. A pause is characterized by a duration. A pitch value is an integer between 0 and 127 (where 60 is middle C). Durations are integers; 960 time units correspond roughly to a second. Instruments are represented as symbols, where the following are supported: Piano, Organ, Guitar, Violin, Flute, Trumpet, Helicopter eller Telephone.

Notes and pauses can be composed sequentially and in parallel. Conceptually, a MusicElement is either a Note, a Pause, a SequentialMusicElement or a ParallelMusicElement. A SequentialMusicElement represents a collection of MusicElements which are played in a strict sequence (one after the other). A ParallelMusicElement represents a collection of MusicElements which are played together (all starting at the same time). Please notice the recursive nature of this modelling: A SequentialMusicElement or a ParallelMusicElement consist of parts, which themselves may be of type SequentialMusicElement and/or ParallelMusicElement. Notes and pauses terminate the recursion. This model of music is a composite (design pattern), and it can be illustrated as in the following class hierarchy:

You are asked to program the following functionality:

Finally, your program must include an example of a simple canon song, and you must include the generated MIDI file in your submission.

The constructor function note-abs-time-with-duration takes the following parameters:

   (note-abs-time-with-duration abs-time channel note-number velocity duration)

where

The procedure transform-to-midi-file! transforms a list of note-abs-time-with-duration forms to a playable MIDI file. The procedure has the following signature:

   (transform-to-midi-file-and-write-to-file! low-level-event-list filename)

where

The low-level transformation functionality, which supports this exercise, can be downloaded from the course website in a number of different variants (depending on your Scheme platform).

Alternatively, a playable MIDI file can be generated by a web service from a list of note-abs-time-with-duration forms, provided that you use this simple implementation of the constructor function:

  ; Construct the low-level internal representation of a note (with note-number)
  ; bound to a particular absolute time (in time ticks), and with a given duration
  ; (in time ticks). The channel parameter encodes the instrument used.
  ; The velocity represents the strengths of the node.
  (define (note-abs-time-with-duration abs-time channel note-number velocity duration)
    (cons 'note-abs-time-with-duration (list abs-time channel note-number velocity duration)))

In case of inaccuracies in the formulation of this exercise, please state the conditions under which you have created you solution.


1.15   AAU group formation **** 

In this exercise we will work with the concepts student, group and grouping. The overall purpose is to program various ways to make project groups, in the context of PBL group work at AAU.

A student has the following properties: Student-id, name, sex, ethnicity (country born), and age. The student-id is unique, and it corresponds directly to the AAU student number (represented as a string). The sex is either "male" or "female" (both strings). The nationality is a string (such as "Danish"). The age is a non-negative integer. As such, a student can be represented by various list formats, as a struct, or as a simulated OOP object.

A group is a set of students, which, for some purpose, belongs together (such as in a semester group at AAU). The group also has a group-id, which in this exercise is an integer group number (starting from 1). A group can be represented as the group-id together with a list of students, or (shorter) a group-id together with a list of student-ids.

A grouping attaches a group to each student in our population of interest. Thus, in a grouping each student should belong to exactly one group. A grouping can be represented as a list of groups. Alternatively, a grouping can be represented as an association list which maps student-ids to group-ids. In this exercise, we recommend that a grouping is represented as an association list, which associcates a group number to a student. As an example, the association list (ordered arbitrarly):

    ((1 . a) (1 . e) (2 . b) (1 . c) (2 . d))

defines a grouping consting of two group. Group 1 consists of the students a, e and c. Group 2 consists of the students b and d.

The starting point of this exercise is a population of n students. There exists a sample population of 200 students, which can be used as the starting point in a solution to this exercise. You are supposed to input/read these student in the beginning of your program.

Write a function that returns a given group from a grouping. In addition, write a function that returns the number of groups in the grouping, a function that return the maximum group size in a grouping, and a function that returns the minimum group size in a grouping.

Write constructor, predidate, selection functions for a single student. As part of this you must decide how to represent a student in your program.

Write a constructor function for a single group, and write a group predicate function. In addition, write a selector function that returns a list of students in the group, and a selector function that returns the group-id (group number). Both the constructor and selectors will most likely be trivial, but it is good for us to have these functions available.

The various grouping functions (discussed below) will serve as grouping constructor functions. Write a predicate that identifies a grouping object.

For practical purposes it is recommended to program (pretty)printing functions for students, groups and groupings.

Random grouping: Given a list of students sl and a list of desired group sizes gsl, program a grouping function that forms (length gsl) groups, of the sizes prescribed in gsl. This grouping function should return a grouping. The function should asserts that gsl is a list on positive integers (g1 g2 ... gk), where g1+g2+...+gk = (length sl). The grouping should be recursive, in a straightforward way: Initially, form a group of g1 students (randomly selected with use of a random function), and solve the remaining random grouping problem recursively, for the group size list (g2 ... gk).

Grouping by counting: Program a second grouping function which mimics the "manual couting approach" to the formation of k groups. In this approach, the grouping relies somehow on the order of students in the student collection. The counting goes: 1, 2, ..., k, 1, 2, ... k, ... (a total of n times where n is the number of students). This leads to a marking of each student by the allocated group number, and based on the marking, a grouping object should be created.

Balanced grouping by counting: As a variant of grouping by counting, program a third grouping function to form k groups from the n students which ensures equal distribution of sex and equal distribution of ethnicality in the constructed groups. As equal as possible in the real world. Please come up with a good, pragmatic and reasonable solution.

Random grouping with group predicate. As a variant of random grouping, add a group predicate to the parameter list of grouping function. Do your best to form groups that fulfill the group predicate. If a (random) group is formed, which breaks the group predicate, redo the random pick of the group (up to a limit, such as 1000 times). Program and play with the following group predicates:

In the 2020 version of the PP1 miniproject, the Random grouping with group predicate is considered as optional.

It is allowed to use a non-pure random function function for random grouping (such as random in Racket). In addition, you are allowed to write non-pure print functions. All other functions in your solution should be pure functions.


Generated: Friday August 13, 2021, 14:51:38