.nh
.he 'CS372/272'Practical Work for Programming Paradigms.'-%-'
.fo 'L.A.'Computer Science, Monash University'1991'

This can be nroff-ed using `me' macros.

You must be able to demonstrate practical ability
to write, understand and explain functional programs in
the lambda-calculus (as implemented in /staff/inf/lloyd/Fp)
and the language Lazy-ML (LML).
Solve the problems below and keep solutions in your Decstation directory.

You will be tested at a demonstration of approximately 15 minutes duration
at a time and date to be arranged,
probably in the week 7-11 October.
It will count for 30% of the course mark.

NB. (i)  Do not use LML arrays or exceptions.
    (ii) Make sure input to `Fp' does not include tabs or trailing white space;
         there is a bug I never fixed.
         vi often inserts tabs!   try :g/<tab>/s//        /g

The specific techniques that you must master are:
  . recursive functions
  . recursive data-structures (circular programs)
  . "infinite" data-structures
  . mutual recursion, of functions, data-structures or both
  . high-order functions having functions as parameters and/or results
  . continuations
  . effects of call-by-need (lazy) evaluation

  . polymorphic type system (in LML)
  . type variables
  . type inference, most general type
  . type definition

You may be asked to do any or all of:
  . show a working program from your directory
  . explain a function
  . trace the execution of a function or program by hand
  . write a piece of code
  . infer and check types by hand

You may be tested on functions or programs for the following problems:
.br
(NB. some of these are standard LML routines,
some I have provided,
but even so you must be able to write your own and explain them on arbitrary
inputs.)

.ne 3
\fB1. In Fp and in LML:\fP
  . append 2 lists
  . merge 2 sorted lists
  . reverse a list (fast O(n) method)
  . reduce a list where     reduce op z L = L1 op (L2 op ( ... op z))
  . use map and reduce to search a list
.ne 2
  . sublist L1 L2 is true iff L1 is an uninterrupted sublist of L2
    eg. 2::3::nil  is a sublist of  1::2::3::nil  but not of  2::1::3::2::nil
.ne 2
  . flatten a hierarchical-list, or a tree, in infix order to yield a flat list
    (using accumulating parameter)
  . zip 2 lists to give a list of pairs [[A1,B1], [A2,B2], ...]
.ne 3
  . split a list L to produce 2 lists,
    [[L1, L3, L5, ...], [L2, L4, L6, ...]]
    L might be infinite.

  . Y, the paradoxical combinator.

.ne 2
  . membership, union, intersection and difference:
    treating a sorted list as a set, implement the given set operations.

.ne 2
  . transpose a "matrix" represented as a list of lists [not as an LML array].
    Can it work on an "infinite matrix"?

  . Give a corrected version of quick-sort, sort.q.fp.

.ne 5
\fB2. In LML, write at least either the parser or Ukkonen's algorithm:\fP

  . \fBParse\fP an arithmetic expression, build a parse tree and print it in
prefix form:
.(b
.ft CW
    <exp>    ::= <term>   { <addop> <term> }...       eg. x+99+x*(x-1)/4
    <term>   ::= <factor> { <multop> <factor> }...    eg. x*(x-1)/4
    <factor> ::= <identifier> | <numeral> | ( <exp> )
    <addop>  ::= + | -
    <multop> ::= * | /
    <identifier> ::= <letter> { <letter> }...         eg. x or fred
    <numeral>    ::= <digit> { <digit> }...           eg. 7 or 1234

    { } means optional
    ... means can be repeated
.ft
.)b

  . Write a symbolic differentiator for the expressions parsed above.

  . LCS longest common subsequence
    both an exponentially slow version and an O(|A|*|B|) version are given.
(Note the "slow" one is O(|A|) when A=B,
can one get this complexity when A=B for the fast one too?)
.(b
.ft CW
      string B

         0 1 2 3 4
         - A C G T
        .---------->j
     0 -|0 0 0 0 0
     1 A|0 1 1 1 1
     2 G|0 1 1 2 2    L[i,j] = LCS( A[1..i], B[1..j] )
 A   3 C|0 1 2 2 2
     4 T|0 1 2 2 3    LCS('ACGT', 'AGCT') = |'ACT'| = |'AGT'| = 3
        |
        v
         i
.ft
.)b
.(b
.ft CW
Note, L[i,j] = L[i-1,j-1]+1                         if A[i]=B[j],
             = max(L[i-1,j-1], L[i,j-1], L[i-1,j])  otherwise.
.ft
.)b

.ne 5
 . \fBUkkonen's\fP edit distance algorithm:
   The edit distance D(A,B) = the minimum number of character
insertions, deletions and changes
needed to change string A into string B.
It can be calculated, by a modification of the LCS algorithm,
in O(|A|*|B|) time.
   eg. D('ACGT', 'AGCT') = 2
   eg. D('ACGTACGTACGT', 'AGTATGTACTGT') = 3
.(b
.ft CW
              B
         0 1 2 3 4
           A G C T
        .----------->j
     0  |0 1 2 3 4
     1 A|1 0 1 2 3     DM[i,j] = D(A[1..i], B[i..j])
 A   2 C|2 1 1 1 2
     3 G|3 2 1 2 2
     4 T|4 3 2 2 2
        |
        v
         i
.ft
.)b
Note that each row, column and \fIdiagonal\fP of DM[,] is non-decreasing.
Ukkonen's algorithm does not calculate DM[,] directly.
The algorithm instead computes where "contours" in DM[,] reach along diagonals:
   U[d,c] = max i s.t. DM[i,j] = c
          = a "special" value if there is no such i
      where diagonal d=i-j and c>=0.
   Then D(A,B) = min c s.t. U[main_diag, c] = |A|
      where main_diag = |A|-|B|.

   1. What do DM and U look like if A=B?
   2. What is U[d,0] for each d?
   3. How is U[d,c] related to U[d,c-1], U[d-1,c-1] and U[d+1,c-1]?

The algorithm should take O(|A|*D(A,B)) time, fast when A and B are similar.