Elm-Spreadsheet

Elm-spreadsheet provides the means to represent and compute with spreadsheets in Elm. A spreadsheet is a two-dimensional array of cells, each of which may contain either data (values) or formulas. To evaluate a spreadsheet is to apply the formulas to create a new spreadsheet. If the new spreadsheet contains no formulas, we say that it is fully evaluated.

Representation

Spreadsheets can be represented in a variety of ways.

1. As a String

     100.0             1.1       row * 1 2
     120.0             1.4       row * 1 2
     140.0             0.9       row * 1 2
         -     col sum 1 3     col sum 1 3

   The entry row * 1 2 in row r, column 3 means "add the cell contents at (r, 1) to those at (r, 2) and put the result in the cell at (r,3)." At the text level, we use "human numbering," with indices starting at 1, not 0.

2. As a List (List String)

   > TestData.text
   [
        ["100.0","120.0","140.0","-"]
       ,["1.1","1.4","0.9","col sum 1 3"]
       ,["row * 1 2","row * 1 2,"row * 1 2,"col sum 1 3]
   ]

3. As a List (List Cell)

   > parse TestData.text
   [ [Right (Real 100),Right (Real 120),Right (Real 140),Right Undefined]
    ,[Right (Real 1.1),Right (Real 1.4),Right (Real 0.9),Left (ColOp "sum" 1 3)]
    ,[Left (RowOp "*" 1 2),Left (RowOp "*" 1 2),Left (RowOp "*" 1 2),Left (ColOp "sum" 1 3)]
   ]

   where

   type alias Cell =
       Either Formula Value
   
   
   type Formula
       = RowOp String Col Col
       | ColOp String Row Row
   
   
   type Value
       = Integer Int
       | Real Float
       | Boolean Bool
       | String String
       | Undefined

   One can convert this format back into a text represention:

   render : List Cell -> List (List String)
   render sheet =
       List.map renderColumn sheet

Evaluation

The function eval carries out the computations specified in the formula cells. Thus the sequence

  TestData.text |> parse |> eval |> render |> Pretty.print

yields the data

  100    1.1    110.0
  120    1.4    168.0
  140    0.9    126.0
    -    3.4    404.0

The eval function always produces a transformed spreadsheet. When fully evaluated, all cells are of typeRight Value. In this early version of the package, not all valid spreadsheets are fully evaluated.

Remarks on eval

The current strategy is to evaluate row formulas from left to right and then evaluate column formulas from top to bottom. This strategy always succeeds in that it yields a spreadsheet. However, the result is fully evaluated only if certain restrictions hold:

1. A row operation in a cell at (row, col) must refer only to columns i, j where i < col, j < col. Moreover, the cells at (row, i) and (row, j) must contain values.

2. A column operation in a cell at (row, col) must refer only to rows i, j where i < row and j < row. Moreover after all row operations have been carried out as in (1), the cells referred to must contain values.

To lift these restrictions, we must "solve" the spreadsheet by finding an order in which to evaluate the operations which results in a fully evaluated spreadsheet. To do this, consider the dependencies of the operations. If an operation in cell A, which we label as "op A", depends on an operation in cell B, then we say that op B is a child of op A:

op A -> op B

Thus the operations constitute the nodes of a graph in which the edges represent dependencies. A depth-first traversal of the graph, assuming no cyclic dependencies, will result in full evaluation.

Thus it remains to (a) derive dependency graphs from spreadsheets, (b) traverse the graph depth-first, performing the indicated computations as each node is visited.

Plans

1. Implement a depth-first evaluation strategy

2. Detect cyclic dependencies

3. Add formulas