/**
 * A collection of functions to process lists in a "functional" style.
 * Lists are represented by arrays and all functions always return new lists, leaving the
 * inputs untouched.
 *
 * NB: For the sake of efficiency, the implementation makes no use of recursive calls ---
 * which would be a "natural" fit indeed.  (Yes, unfortunately we have to give up the
 * conciseness and beauty of the functional style to make things perform decently in
 * JavaScript.)
 */


/**
 * Computes the recurrence:
 *
 *     r[0] = u
 *     r[k] = f(r[k-1], list[k])
 *
 * and returns r[n], where n is the length of the input list.
 * E.g.
 *   fold(function(u,x) { return u+x; }, 0, [])       ~~>  0
 *   fold(function(u,x) { return u+x; }, 0, [1])      ~~>  1
 *   fold(function(u,x) { return u+x; }, 0, [1,2,3])  ~~>  6
 */
function fold(f, u, list)
{
    var len = list.length;
    
    for (var k = 0; k < len; ++k) u = f(u, list[k]);
    return u;
}


/**
 * Computes the list r defined by the recurrence:
 *
 *     r[0] = f(u, list[0])
 *     r[k] = f(r[k-1], list[k])
 *
 * E.g. 
 *   scan(function(u,x) { return u+x; }, 0, [1,2,3])  ~~>  [1, 3, 6]
 *   scan(function(u,x) { return u+x; }, 0, [])       ~~>  []
 */
function scan(f, u, list)
{
    var len = list.length;
    var result = new Array(len);
    
    for (var k = 0; k < len; ++k)
    {
        u = f(u, list[k]);
        result[k] = u;
    }
    
    return result;
}


/**
 * Computes the list whose k-th element is given by f(left[k], right[k]).
 * The computation proceeds up to the length of the shortest list.
 *
 * E.g.
 *   zipWith(function(a,b) { return a+b; }, ['1','2','3'], ['1','2'])  ~~>  ["11", "22"]
 */
function zipWith(f, left, right)
{
    var len = Math.min(left.length, right.length);
    var result = new Array(len);
    
    for (var k = 0; k < len; ++k) result[k] = f(left[k], right[k]);
        
    return result;
}


/**
 * Intersperses the given separator between the elements of the list.
 * E.g.
 *   intersperse(0, [])       ~~>  []
 *   intersperse(0, [1])      ~~>  [1]
 *   intersperse(0, [1,2])    ~~>  [1, 0, 2] 
 *   intersperse(0, [1,2,3])  ~~>  [1, 0, 2, 0, 3]
 */
function intersperse(separator, list)
{
    var len = list.length;
    
    if (len == 0) return [];
    if (len == 1) return [list[0]];
    
    len = 2*len - 1;
    var result = new Array(len);

    for (var k = 0; k < len; ++k)
    {
        result[k] = k % 2 == 0 ? list[k/2] : separator;
    } 

    return result;    
}


/**
 * Concatenates the list of strings into one.
 * E.g.
 *   concat([])          ~~>  ""
 *   concat(["a","bc"])  ~~>  "abc"
 */
function concat(listOfStrings)
{
    return fold(function(u,x) { return u+x; }, "", listOfStrings);
}