<Write a BST:Work and Span

programming › functional programming

materials: 15-150, http://www.cs.cmu.edu/~15150/index.html

Goal of this article is to learn how to write a balanced binary search tree as an example to dip into the flavour of functional programming.

Problem 1: how to exploit parallelism?

Expression evaluation has no side-effects on correctness of program. Evaluation order has no effect on values. Thus evaluation on independent code in parallel is workable.

A more procedural way to analyse is work and span. To calculate the runtime, go back to recurrence. Work runs in sequential while span is in parallel. Work of an expression is the work for sub-expressions. Span of an expression needs to max the span for independent sub-expressions first and add them up.

Definition of work and span.

  1. , the work of expression is the evaluation time in sequential on a single processor.
  2. , the span of e is the evaluation time in parallel for independent code.
  3. The applicative work/span / is the work/span of when v is a value of size n.

Problem 2: How to use trees to represent integers? -> How to design a datatype for trees : int?

To design a datatype, we need to consider:

  1. constructor

Basics

ML has syntax features as:

  • Only well-typed expressions can be evaluated (int, real, bool, tuples, fun, list)
  • Functions are values (f(x) = x + 1) or functions (f(x) = f(x-1) + 1)
  • List items have the same type.
  • User defines their own types.

ML systems:

  • expressions are evaluated to values
  • declarations are checked with types
  • ML reports value and type

Pitfalls and notices:

  1. warning: the indication of redundant code of the pattern.

    1
    2
    3
    - val 49 = sq (~7);
    stdIn:44.5-44.17 Warning: binding not exhaustive
              49 = ...

  2. import file in interpretor: must add double quotation marks

    1
    - use "eval.sml";

  3. marks: =>* means equivalent to in finitely many steps, :: is the constructor for lists.

  4. nil is an empty list