Lists and Trees: Introduction

Reminder:

• Subject is about problem solving [e.g.], i.e. abstract algorithms and data structures
  
  
• not programming (in C) as such

• List
• (more) Trees
• Parse Trees and parsing
• Manipulating Trees

The abstract data type (ADT) ``List''

• A (linked) list is either
  • the empty list or ( | )
  • constructed (cons) from an element and a list
• List t   =   nil   |   cons t (List t)
  
  
• operator:  null: List t -> Boolean    (aka isEmpty etc)
• operator:  hd: List t -> t       (aka head, first, etc)
• operator:  tl: List t -> List t    (aka tail, next, rest etc)

  -- rules

• the operators obey the rules:
  • null ( nil ) = true
  • null ( cons e l ) = false
  • hd ( cons e l ) = e
  • tl ( cons e l ) = l

Many useful functions on Lists, e.g.:

• append: List t × List t -> List t
  
  
• e.g. append [1, 2] [3, 4, 5] = [1, 2, 3, 4, 5]
  
  
• Definition:
  • append nil L₂ = L₂
  • append (cons e L₁) L₂ = cons e (append L₁ L₂)
  
  
• can be implemented [in C] of course.

It is much easier to reason formally about ADTs and (abstract) algorithms than about C structures and programs...

• Theorem: append L₁ (append L₂ L₃) = append (append L₁ L₂) L₃
  
  
• proof part (a), the base case, if L₁ = nil
  
  
  • append nil (append L₂ L₃)
    
    
  • = append L₂ L₃
    
    
  • = append (append nil L₂) L₃
    
    
  • = append (append L₁ L₂) L₃
    
    

• proof part (b), the general case, if L₁ = cons h t
  
  
  • append (cons h t) (append L₂ L₃)
    
    
  • = cons h (append t (append L₂ L₃))
    
    
  • = cons h (append (append t L₂) L₃)    --[*]
    
    
  • = append (cons h (append t L₂)) L₃
    
    
  • = append (append (cons h t) L₂) L₃
    
    
  • = append (append L₁ L₂) L₃
    
    

ADT Tree

• A (binary) Tree (of some Element type) is either
  
  
  • the empty tree or
    
    
  • a fork made of an element `E', a left sub-tree `L' and a right sub-tree `R'.
  
  
• Tree t = Empty_Tree  |  Fork t (Tree t) (Tree t)
  
  
• [See Ops.c in .../C/Tree/]

possible representation in C:

  #include "TreeElement.h"

  struct node
   { TreeElementType elt;
     struct node *left, *right;
   };
  typedef struct node Node;

  typedef Node *Tree;

  /* Tree Type. */

Many useful functions on Trees, e.g.

• flatten: Tree t -> List t
  
  
• Definition
  • flatten Empty_Tree = nil
    
    
  • flatten (Fork e L R)
    = append (flatten L) (cons e (flatten R))
  
  
• This Defn takes O( n² )-time, because [___________________]
  
  

. . . by the way, this `flatten' is faster, O(n)-time:

• flatten T   =   flatten2 T nil
  
  
• where
  
  
  • flatten2 Empty_Tree Ans   =   Ans
    
    
  • flatten2 ( Fork e L R ) Ans   = flatten2 L ( cons e ( flatten2 R Ans ) )
    
    

Propositional Logic

• Already discussed parser and arithmetic expressions
  
  
• Can "easily" change it to parse propositional logic ~ Boolean expressions:
  
  

  `+'    ---> `or'
  
  

  `*'    ---> `and'
  
  

  unary `-'    ---> `not'

  
  

• & distributes over or:
  
  

    p & (q or r)      =       (p & q) or (p & r)

                                      or
         and                         .  .
        .   .        --->           .    and
       .     .                |----.-----| .
      .      or               |   .         .
     .       . .              |  and         .
    .       .   .             | .    .        .
   .       .     .            |.      .        .
.---.   .---.   .---.        .---.   .---.   .---.
| p |   | q |   | r |        | p |   | q |   | r |
.---.   .---.   .---.        .---.   .---.   .---.

• useful for DNF (disjunctive normal form)

Example

• This html FORM can prove theorems in propositional logic may be useful later in `Formal Methods'.
  
  
• [lecturer: e.g. do the `or' over `and' pointer manipulation; class: take notes]

Lists and Trees:   Summary:

• Abstract data type (ADT) ``List''
  
  
• reasoning about algorithms and ADTs
  
  
• ADT ``Tree''
  
  
• Manipulating Trees