--[[ Cell-Based List Module
     Functional Programming Example in Lua
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-12: Prototyped list functions
2013-09-13: Restructured into module; improved precondition testing
2013-09-15: Expanded comments on module design
            Added functions copy and traverse
2013-09-26: Changed isList to return boolean (not nil/non-nil)
2013-12-27: Added function deepCopy

This Lua module exports a set of functions for a List abstract data
type (ADT). A list is an ordered sequence of values. The design of
this ADT module builds on primitive list constructor operations Cons
and Nil, accessor operations head and tail, and query operations
isList and isNil. It also provides several convenience operations
built on these primitives.

The module's functions manipulate these lists in ways similar to the
lists in Lisp, Scheme, Haskell, and other functional programming
languages.  The functions in this module are implemented in Lua using
functional programming techniques.  The names are similar to those in
the Haskell standard library.

Caveat: In most cases, Lua programs do not use "linked lists".  Most
use Lua's efficient and flexible table data structures as dynamic
arrays to implement ordered sequences. 

As a component of this course, the objectives of this extended example
are to:

(1) reinforce functional programming principles

(2) demonstrate how to use linked lists in Lua

(3) show how to design abstract data types and information hiding
    modules

(4) illustrate how to implement modules in Lua

(5) demonstrate how to build a stateless iterator to use with Lua's
    generic for.

DATA REPRESENTATION

Internally, the module represents a list by a Lua table. Each nonempty
list consists of a list cell with two fields, "head" and "tail":

  { head = some_value, tail = next_list_cell } 

The module represents he empty, or Nil, list by a special list cell
with no fields, that is, by a specific empty table denoted by the
internal constant NILLIST.

The module enables new non-empty list cells to be constructed with the
Cons constructor; the Nil constructor returns a reference to the
canonical empty list cell.

Field "head" of a list cell denotes the first element in the list.
It must be a non-nil Lua value.

Field "tail" of a list cell denotes the list remaining after the head
element is removed. It is represented by a non-nil reference to
another list cell.

The intention is that cells are immutable.  A cell-based list can be
constructed and accessed, but it should not be changed (i.e.,
mutated). Functions may take lists and create new lists that include
modified copies of cells from the original lists.  However, it is
possible to mutate elements of the list (e.g. change the values of
table entries in elements) from outside the module.

Warning: Assigning directly to the "head" and "tail" fields of a cell
is not prevented in this implementation. Doing this may destroy the
integrity of the list.  Thus it should not be done!

Are there ways to change the module to avoid this problem?

MODULE DESIGN

The List module design reflects the following principles, motivated by
good software design practices and the module implementation
recommendations given in Chapter 15 of the textbook "Programming in
Lua" (PiL).

(1) All variables and function names should be local to the module.
That is, they are Lua "local" variables.

(2) The module should only export those names that need to be exposed
to users of the module. These names form the interface to the module.
Following the recommendations in PiL, this module uses an explicit
return statement that returns a table of references to the functions
in the public interface.

(3) The design of the module should follow the information hiding
principle.  

The goal of information hiding is to enable an aspect of the overall
software system design that might change among versions to be changed
without affecting many modules.  That is, a likely change should be
isolated in one module; changes to that module's code should not break
code in other modules. The approach requires us to identify the key
design decision (e.g., the choice of a concrete data representation or
algorithm) and keep that decision "secret" to that module.

The module should:

- not reveal the internal design choices to the users of the module.
  For example, the primary "secret" of this List module is the
  representation of the data.

- use functions to abstract away from the concrete data
  representation. It should disallow or discourage the users from
  manipulating the internal representation directly.

- not rely on knowledge of the design details of other modules.

(4) The designer should identify the preconditions and postconditions
of each function and, where feasible, check the precondition of any
function in the public interface.

In this module, the comments about a function specifies its
precondition unless the precondition is obvious from the assert calls
at the beginning of the function's body. 

Warning: Most of the functions in this module assume that one or more
of the arguments are "validly structured finite lists" (i.e., cell
lists for which boolean function isValidList returns true). This is
not fully checked by any function.  For example, if a list has a
cycle, then the functions will fail to return a value.  However, if
all lists are constructed and manipulated only with the functions in
this module, it should not be possible to construct cycles.

--]]


-- PRIMITIVE OPERATIONS AND CONSTANTS

-- These primitive definitions directly access and manipulate the Lua
-- data representation for the lists.  They provide a layer of
-- functional abstraction that the non-primitive and user functions
-- use to create and manipulate lists. In some sense, these primitive
-- definitions are themselves an information-hiding module hiding the
-- secret of how the lists are represented.


-- Define a constant for a Nil list singleton object
local NILLIST = {}


-- Function "isNil" returns true if and only if argument "l" is the
-- Nil list.

local function isNil(l) return l == NILLIST end


-- Function "isList" returns true if and only if argument "l" is a
-- valid non-Nil list cell. (That is, the list cell must have both
-- fields "head" and "tail". The function does not disallow list cell
-- table from having extra fields and does not recursively check the
-- head or tail for validity.)

local function isList(l)
  return type(l) == "table" and l.head ~= nil and l.tail ~= nil
end


-- Function "Nil" returns the canonical representation for the Nil
-- list.

local function Nil()
  return NILLIST
end


-- Function "Cons" takes a non-nil head element "h" and a tail list
-- cell "t" and returns a new list cell for the list with head "h" and
-- tail "t". If "t" is nil or absent, then it defaults to the Nil
-- list. Cons does not recursively verify the validity of the tail of
-- the tail list.

local function Cons(h,t)
  t = t or Nil()
  assert(h ~= nil, "head element in Cons call must be non-nil.")
  assert(isList(t) or isNil(t),
         "tail element in Cons call must be a valid list.")
  return { head = h, tail = t }
end


-- Functions "head" and "tail" return the respective fields of the
-- list "l".

local function head(l)
  assert(isList(l),
    "head function not defined for lists without head field.")
  return l.head
end
    
local function tail(l)
  assert(isList(l),
    "tail function not defined for lists without tail field.")
  return l.tail  
end


-- NON-PRIMITIVE CONVENIENCE FUNCTIONS

-- These operations do not directly access the data structure
-- implementing the list cell table. They build on the primitive
-- operations above.


-- Function "isValidList" returns true if and only if argument "l" is
-- a validly structured finite list.  If does not return if the list
-- is infinite (e.g., contains cycles).  (Calling this function does a
-- deep validity check on the list, but does not look at data embedded
-- in the head elements of cells.)

local function isValidList(l)
  if isList(l) then
    return isValidList(tail(l))
  else
    return isNil(l)
  end
end


-- Function "listToString" converts list "l" to a convenient string
-- format and returns the string. If an element of a list is itself a
-- list, this function recursively converts that element to a list.

-- Precondition: isValidList(l)

local function listToString(l)
  if isList(l) then
    local h, hstr = head(l), ""
    if isList(h) or isNil(h) then
      hstr = listToString(h)
    else
      hstr = tostring(h)
    end
    return "Cons(" .. hstr .. ", " .. listToString(tail(l)) .. ")"
  else
    assert(isNil(l),
      "Argument of listToString is not a validly structured list.")
    return "Nil"
  end
end


-- Function "copy" constructs a "shallow" copy of list "l" and returns
-- the copy.  That is, it creates duplicates of the cells in the list
-- itself, but it does not copy the data embedded within the head
-- elements of the cells.

-- Precondition: isValidList(l)

local function copy(l) 
  if isList(l) then 
    return Cons(head(l),copy(tail(l))) 
  else 
    assert(isNil(l),"Can only copy validly structured lists.")  
    return Nil() 
  end
end


-- Function "deepCopy" constructs a "deep copy" of its argument "l".
-- That is, if any element of the list "l" is itself a list, the
-- function copies that list.  It also does a shallow copy of any
-- other table encountered.

local function deepCopy(l)
  if isList(l) then
    return Cons(deepCopy(head(l)),deepCopy(tail(l)))
  elseif isNil(l) then
    return Nil()
  elseif type(l) == "table" then
    print("DEBUG: table")
    local newl = {}
    for k,v in pairs(t) do
      newl[k] = v
    end
    return newl
  else
    return l
  end
end


-- Function "length" returns the length of list "l".  The length is
-- the number of cells in the list, not counting the Nil at the end.

-- Precondition: isValidList(l)

local function length(l)
  if isList(l) then 
    return 1 + length(tail(l))
  else 
    assert(isNil(l),
           "Can only evaluate length for validly structured lists.")
    return 0  
  end
end


-- Function "take" returns the list constructed by extracting the
-- first "n" elements from list "l".

-- Precondition: n >= 0 and isValdList(l)
-- This function does not do a deep validity check on "l".

local function take(n,l)
  assert(n >= 0,
         "Cannot take negative number of elements from a list.")
  local msg = 
    "Second argument of take must be a validly structured list."
  if n == 0 then
    assert(isList(l) or isNil(l), msg)
    return Nil()
  elseif isList(l) then
    return Cons(head(l),take(n-1,tail(l)))
  else
    assert(isNil(l),msg)
    return Nil()
  end
end


-- Function "drop" returns the the list constructed by removing the
-- first n elements of list "l".

-- Precondition: n >= 0 and isValdList(l)
-- This function does not do a deep validity check on "l".

local function drop(n,l)
  assert(n >= 0,
         "Cannot drop negative number of elements from a list.")
  local msg = "Second argument of take must be a list."
  if n == 0 then
    assert(isList(l) or isNil(l), msg)
    return l
  elseif isList(l) then
    return drop(n-1,tail(l))
  else
    assert(isNil(l), msg)
    return Nil()
  end
end


-- Function "append" takes lists "x" and "y" and returns a new
-- list consisting of the elements of "x" followed by the
-- elements of "y".

-- Precondition: isValidList(x) and isValidList(y)
-- This function does not do a deep validity check on "y".

local function append(x,y)
  if isNil(x) then
    assert(isList(y) or isNil(y),
      "Second argument of append must be a list.")
    return y
  else
    assert(isList(x),
      "First argument of append must be a validly structured list.")
    return Cons(head(x),append(tail(x),y))
  end
end


-- Function "traverse" sets up a stateless iterator compatible with
-- Lua's generic-for statement. The function takes a list and returns
-- three values needed by the generic-for: the iterator function
-- "getnext", the invariant state (the entire list), and the
-- control variable (initially the first cell).  

-- When used with the generic for, the "getnext" iterator steps from
-- cell to cell through the list, returning the next (tail) cell and
-- the current head value for each step. (See sections 7.2 and 7.3,
-- pages 63-65, of PiL for an explanation.)

-- Precondition of getnext: 
--   isValidList(l) and cell is some tail segment of l

local function getnext(l,cell)
  if not cell or isNil(cell) then
    return nil
  else
    assert(isList(cell),
      "Argument to traverse must be a structurally valid list.")
    return tail(cell), head(cell)
  end
end

-- Precondition of traverse: isValidList(l)

function traverse(l)
  assert(isList(l) or isNil(l),
    "Argument to traverse iterator must be a list.")
  return getnext, l, l
end


-- Function "map" applies (i.e., maps) function "f" to every element
-- of list "l" and returns the resulting list, preserving the relative
-- order of the elements. 

-- Precondition: isValidList(l) and "f" is a one argument function
-- defined for all elements in "l".

local function map(f,l)
  if isList(l) then
    return Cons(f(head(l)),map(f,tail(l)))
  else 
    assert(isNil(l),
      "Second argument to map must be a validly structured list.")
    return Nil()
  end
end


-- Function "filter" applies boolean function (i.e., a predicate)
-- "pred" to every element of list "l" and returns the new list
-- consisting of those elements for which the predicate is true.

-- Precondition: isValidList(l) and "pred" is a one-argument boolean
-- function defined for all elements in "l"

local function filter(pred,l)
  if isList(l) then
    local h = head(l)
    if pred(h) then
      return Cons(h,filter(pred,tail(l)))
    else
      return filter(pred,tail(l))
    end
  else
    assert(isNil(l),
      "Second argument to filter must be a validly structured list.") 
    return Nil()
  end
end


-- Function "foldr" inserts the binary operator "op" between every
-- pair of elements in the list "l" with value "init" after the last
-- element of the tail. It computes the resulting value with operator
-- "op" binding from the right: op(x1,op(x2,op(x3,init))) for list
-- {x1,x2,x3}. Often, "init" is the right identity element of the
-- operation "op".

-- Precondition: isValidList(l) and "op" is a binary operator that
-- takes an element of the list as its left operand and elements of
-- the same kind as "init" as its right operand and returns a value of
-- the same kind as its right operand.

-- For example, if "op" is addition of numbers and we wish to add the
-- numbers in the list, we can set "init" to 0, which is the identity
-- element and, hence, both the right and left identity element.`

local function foldr(op,init,l)
  if isList(l) then
    return op(head(l),foldr(op,init,tail(l)))
  else
    assert(isNil(l),
      "Third argument to foldr must be a validly structured list.")
    return init
  end
end


-- Function "foldl" inserts the binary operator "op" between every
-- element in the list "l" with value "init" added before the head. It
-- computes the resulting value with the operators binding from the
-- left: op(op(op(init,x1),x2),x3) for list {x1,x2,x3}. Often, "init"
-- is the left identity element of the operation "op".

-- Precondition: isValidList(l) and "op" is a binary operator that
-- takes an element of the list as its right operand and elements of
-- the same kind as "init" as its left operand and returns a value of
-- the same kind as its left operand.

local function foldl(op,init,l)
  if isList(l) then
    return foldl(op,op(init,head(l)),tail(l))
  else
    assert(isNil(l),
      "Third argument to foldr must be a validly structured list.")
    return init
  end
end


-- Function "toList" constructs a list from array-style table "t" and
-- returns the list.

local function toList(t)
  assert(type(t) == "table","Argument to toList must be a table.")

  local function toList_iter(t,i,l)
    if i == 0 then
      return l
    else
      return toList_iter(t,i-1,Cons(t[i],l))
    end
  end

  return toList_iter(t,#t,Nil())
end


-- Function "fromList" takes a list "l" and constructs the equivalent
-- array-style table "t".

-- Precondition: isValidList(l)

local function fromList(l)
 
  local function toTable(l,t)
    if isList(l) then
      t[#t+1] = head(l)
      return toTable(tail(l),t)
    else
      assert(isNil(l),
        "Argument to fromList must be a validly structured list.")
      return t
    end
  end

  return toTable(l,{})
 end


--[[ MODULE EXPORT LIST (the external interface)

This module chunk (script) is compiled into a zero-argument function.
Another Lua chunk can load this module using the Lua "requires"
function, supplying "requires" the base filename of this module as the
argument.  When this module is loaded, it executes and returns the
following table to that chunk.

A module's table usually consists of references to functions and
values that the developer of the module wishes to make available
(i.e., export) to the user. The module can keep some functions and
values local to the module and not export them. (Remember that a
reference to a "function" is really a reference to a "closure" object.
So it can access and update the local variables and closures that are
not exported.)

The table returned below has fields defines as "outside = inside". The
key "outside" is the name that can be used to access the field from
outside the module. The "inside" is the internal value being exported.
These are often the same name, but they can be different.

--]]

return { Nil          = Nil,
         Cons         = Cons,
         head         = head,
         tail         = tail,
         isList       = isList,
         isNil        = isNil,
         isValidList  = isValidList,
         copy         = copy,
         deepCopy     = deepCopy,
         length       = length,
         take         = take,
         drop         = drop,
         append       = append,
         traverse     = traverse,
         map          = map,
         filter       = filter,
         foldr        = foldr,
         foldl        = foldl,
         toList       = toList,
         fromList     = fromList,
         listToString = listToString
       }