9.2.1 Charts as arrays

Recall that the chart is a graph whose nodes are numbered. Generally, we need to be able to refer to positions in the chart: we want to add edges to the chart between two given position or we might want to search the chart for all edges starting/ending at a given position. One simple way to model such a structure is to use an array. How exactly do we represent a chart using an array? First, we set the length of the array to the number of words contained in the input string. Initially, each position in the array is bound to the empty list but as the chart is built, they become bound to lists of edges representation. Specifically, an edge stretching from Begin to End and labelled with category Cat is represented at position Begin in the array by the record edge(cat:Cat begin:Begin 'end':End).

<edge.oz>=

functor 
import 
export 
   %% type cat = atom
   %% type edge = unit(cat:cat begin:int 'end':int)
   make:MakeEdge % cat x int x int -> edge
define 
   fun{MakeEdge C B E}
      edge(cat:C begin:B 'end':E)
   end 
end

Next we need to be able (i) to add edges to the chart and (ii) to search the chart for edges ending/starting at a given position. To do this, we use the predefined procedures Put and Get.

<chart.oz>=

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  NewChart creates a new chart of the following type:
%%  
%%  type edge= 'a
%%  type chart('a) = unit(add:edge ->
%%                        get:int -> list(edge)  
%%                        min:int
%%                        max:int
%%                        words:list(atom)
%%                        toList: -> list(edge))
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
functor 
export 
   new:NewChart
define 
    
   fun{NewChart Sentence}
      MinPos = 0
      MaxPos = {Length Sentence}   
      Chart = {Array.new MinPos MaxPos nil}
      fun{GetChart Pos}
         {Array.get Chart Pos}
      end  
      proc{Add Edge}
         {Array.put Chart Edge.begin   
          Edge|{Array.get Chart Edge.begin}}
      end 
      fun{ToList}
         for 
            Pos in MinPos..MaxPos
            collect:Collect
         do 
            for Edge in {GetChart Pos} do 
               {Collect Edge}
            end 
         end 
      end 
   in 
      unit(add:Add       %% edge ->
           get:GetChart  %% int -> list(edge)  
           min:MinPos    %% int
           max:MaxPos    %% int
           words:Sentence%% list(atom)
           toList:ToList)%% -> list(edge)
   end 
end

The function NewChart binds the variable Chart to an array with key range MinPosition (1) to MaxPosition (the number of words in the input string plus one) with all items initialised to the empty list nil. It returns a record with two features add and get whose values are operations on Chart. GetC simply retrieves the content of Chart (an array) at a given position. Add takes an edge as input (i.e. a record of the form cat:C begin:B 'end':E)) and modify the array Chart as follows: at position End in Chart it adds to the current list value {Get Chart End} the element left(Cat
Begin) and at position Begin in Chart it adds to the current list value {Get Chart Begin} the element right(Cat
End).