// Indicates the namespace that contains the AlgebraicList module.
namespace FunctionalCollections

// Defines the EmptyList exception.
exception EmptyList of string

// Declares the AlgebraicList module.
module AlgebraicList =
    // Declares the alg_list algebraic data type.
    type 'a alg_list = Empty | Cell of 'a * 'a alg_list

    // Returns a new empty list.
    let empty = Empty

    // Adds an element at the front of a list.
    let addHead elem lst = Cell (elem, lst)

    // Returns the first element of the given list.
    // Raises EmptyList exception if needed.
    let head = function
        | Empty -> raise (EmptyList "list is empty")
        | Cell (hd,_) -> hd

    // Returns the list that remains after removing the head of the given list.
    // Raises EmptyList exception if needed.
    let tail = function
        | Empty -> raise (EmptyList "list is empty")
        | Cell (_,tl) -> tl

    // Determines the number of elements in the list.
    let rec length = function
        | Empty -> 0
        | Cell (_,tl) -> 1 + length tl

    // Determines whether a list is empty.
    let isEmpty = function
        | Empty -> true
        | _ -> false

    // Returns true if the element is a member of a list.
    let rec isMember elem = function
        | Empty -> false
        | Cell(top, rest) when top = elem -> true
        | Cell(_, rest) -> isMember elem rest

    // Concatenates a list with another list.
    let rec append node1 node2 =
        match node1 with
        | Empty -> node2
        | Cell(top,rest) -> addHead top (append rest node2)

    // Returns a new list with the elements of the given list in reverse order.
    let rev lst =
        let rec rev_helper lst lstRev =
            match lst with
            | Empty -> lstRev
            | Cell(top, rest) -> rev_helper rest (addHead top lstRev)
        rev_helper lst empty

    // Removes the first ocurrence of an element from a list.
    // Raises EmptyList exception if needed.
    let remove elem lst =
        let rec remove_helper elem tmpList = function
            | Empty -> raise (EmptyList "List is Empty")
            | Cell(top, rest) when elem = top ->  append (rev tmpList) rest
            | Cell(top, rest) -> remove_helper elem (addHead top tmpList) rest
        remove_helper elem empty lst

    // Iterates through a list using a visit function.
    let rec iter visit = function
         | Empty -> ()
         | Cell(hd,tl) -> visit hd
                          iter visit tl

    // Creates a list by calling a generator on each index.
    let init num gen =
        let rec init_helper acc num gen =
            match num with
            | 0 -> acc
            | _ -> init_helper (addHead (gen (num - 1)) acc) (num - 1) gen
        init_helper empty num gen

    // Applies a function to each element of a list, accumulating a result
    // based on an initial value.
    let rec fold fn acc = function
        | Empty -> acc
        | Cell(hd,tl) -> fold fn (fn acc hd) tl

    // Applies a function to each element of a list, creating a new list.
    let rec map fn = function
        | Empty -> Empty
        | Cell(hd,tl) -> Cell( (fn hd),(map fn tl) )

    // Creates a new list with those elements of the original for which a
    // predicate is satisfied.
    let rec filter pred = function
        | Empty -> Empty
        | Cell(hd,tl) -> if pred hd
                         then Cell(hd,(filter pred tl))
                         else filter pred tl