/* Amzi! List Predicate Library This file contains library predicates that perform various list utilities.
  • append/3 - join or split lists
  • deleteN/4 - delete the Nth element of a list
  • flatten/2 - flatten a list of nested lists
  • length/2 - get the length of a list
  • length_lte/2 - compare lengths of lists
  • length_gte/2 - compare lengths of lists
  • length_lt/2 - compare lengths of lists
  • length_gt/2 - compare lengths of lists
  • member/2 - find or generate members of list
  • nth_elem/3 - find the nth element of a list
  • permutation/3 - permute elements of a list
  • remove/3 - remove an element from a list
  • replace_elem/4 - replace an element in a list
  • reverse/2 - reverse a list
  • shuffle/2 - randomly shuffle a list
  • write_list/2,3 - write separated list elements
  • writeq_list/2,3 - writeq separated list elements
  • */
    
    :- export
         append/3,
         deleteN/4,
         flatten/2,
         length/2,
         length_lte/2,
         length_gte/2,
         length_lt/2,
         length_gt/2,
         member/2,
         nth_elem/3,
         permutation/3,
         remove/3,
         replace_elem/4,
         reverse/2,
         shuffle/2,
         write_list/2,
         write_list/3,
         writeq_list/2,
         writeq_list/3.
    
    /*
    

    append(L1_LV,L2_LV,L12_VL)

    append/3 defines the relationship that lists L1 and L2, appended together, equal list L12. append/3 can be used in a number of different ways, depending on which arguments are instantiated. If the first two are, it simply joins the two lists. If just the third argument is, it generates all possible splittings of the list.

    Contents

    */
    
    append([], X, X).
    append([A|X], Y, [A|Z]) :- append(X,Y,Z).
    
    /*
    

    deleteN(N_I, Elem, In_L, Out_L)

    Delete the N_I elem of the list In_L. Elem is bound to the deleted element and Out_L is bound to the remaining list.

    Contents

    */
    
    deleteN(1, H, [H|Z], Z).
    deleteN(_, _, [], []) :- !, fail.
    deleteN(N, H, [X|Z], [X|Z2]) :-
      NN is N - 1,
      deleteN(NN, H, Z, Z2).
    
    /*
    

    flatten(L1_L, L2_VL)

    Take a list L1, that might have nested lists in it, and flatten it into list L2, that does not have any lists as elements.

    Contents

    */
    
    flatten([], []).
    flatten( [X|T], [X|T2] ) :-
      var(X),
      !, flatten(T, T2).
    flatten([ [] | T], T2) :-
      !, flatten(T, T2).
    flatten([ [H|T] | T2], [H1|T3]) :-
      flatten([H|T], [H1|T1]),
      !, flatten([T1|T2], T3).
    flatten([H|T], [H|T2]) :-
      flatten(T, T2).
    
    /*
    

    length(L, VI)

    Contents

    */
    
    length(L, N) :-length(L, 0, N).
    
      length([], N, N).
      length([_|Y], X, N) :-
        XX is X + 1,
        length(Y, XX, N).
    
    /*
    

    length_lte(L1_L, L2_L)

    Contents

    */
    
    length_lte([], _).
    length_lte([X1|Z1], [X2|Z2]) :-
      length_lte(Z1, Z2).
    
    /*
    

    length_gte(L1_L, L2_L)

    Contents

    */
    
    length_gte(L1, L2) :-
      length_lte(L2, L1).
    
    /*
    

    length_lt(L1_L, L2_L)

    Contents

    */
    
    length_lt([], [_|_]).
    length_lt([X1|Z1], [X2|Z2]) :-
      length_lt(Z1, Z2).
    
    /*
    

    length_gt(L1_L, L2_L)

    Contents

    */
    
    length_gt(L1, L2) :-
      length_lt(L2, L1).
    
    /*
    

    member(X, LV)

    Find a member of a list, or generate all members of a list.

    Contents

    */
    
    member(A, [A|_]).
    member(A, [_|Z]) :- member(A, Z).
    
    /*
    

    nth_elem(L, X, N)

    Given a list, L, nth_elem finds either the position, starting at 1, of the elem X, or the elem at position N.

    Contents

    */
    
    nth_elem(L, X, N) :-
      nth_elem(L, X, 1, N).
    
      nth_elem([X|Z], X, N, N).
      nth_elem([_|Z], X, A, N) :-
        AA is A + 1,
        nth_elem(Z, X, AA, N).  
    
    /*
    

    permutation(ListOfVars, List, LV)

    permutation/3 assigns different values to the variables in the first list from the values in the second. The third list is the list of unassigned values. It works by simply deleting elements from the list using remove/3. Because it is deleting an element which is an unbound variable, remove/3 simply deletes the next element and binds its value to the variable, thus providing a simple way to assign permuted values to a list of variables. On backtracking, of course, delete simply binds the variable to the next element of the list and deletes it, thus eventually generating all permutations of a list.

    Contents

    */
    
    permutation([],L,L).
    permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
    permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).
    
    /*
    

    remove(Elem_X, L1_L, L2_LV)

    Contents

    */
    
    remove(A,[A|X],X).
    remove(A,[B|X],[B|Y]) :- remove(A,X,Y).
    
    
    /*
    

    replace_elem(OldElem, NewElem, Lin, Lout)

    Replace OldElem in list Lin, with NewElem, returning the new list in Lout.

    Contents

    */
    
    replace_elem(_, _, [], _) :- !, fail.
    replace_elem(Old, New, [Old|Z], [New|Z]) :- !.
    replace_elem(Old, New, [X|Z], [X|Z2]) :-
      replace_elem(Old, New, Z, Z2).
    
    
    /*
    

    reverse(List_L, RevList_LV)

    Reverses List_L to RevList_LV.

    Contents

    */
    
    reverse(A, Z) :- reverse(A, [], Z).
    
       reverse([], Z, Z).
       reverse([A|X], SoFar, Z) :- reverse(X, [A|SoFar], Z).
    
    /*
    

    shuffle(In_L, Out_L)

    Randomly shuffles the list In_L and returns Out_L, the shuffled list. To get the same shuffling each time, use the built-in predicate seed_random/1 to provide an integer starting seed for random.

    Contents

    */
    
    shuffle(Tin, Tout) :-
      shuffle1(Tin, [], Tout).
    
      shuffle1([], A, A).
      shuffle1(Tin, A, Tout) :-
        length(Tin, L),
        N is 1 + integer( random * L ),
        deleteN(N, Elem, Tin, Tx),
        shuffle1(Tx, [Elem|A], Tout).
       
    /*
    

    write_list(L, Separator_AS)

    write_list/2 writes each of the elements of a list, writing the Separator between elements. For example, write_list(L, $\n $), will write the elements of list L on newlines, indented two spaces.

    Contents

    */
    
    write_list([], _).
    write_list([X], _) :-
      !, write(X).
    write_list([X|Y], Separator) :-
      write(X),
      write(Separator),
      write_list(Y, Separator).
    
    write_list(H, [], _).
    write_list(H, [X], _) :-
      !, write(H, X).
    write_list(H, [X|Y], Separator) :-
      write(H, X),
      write(H, Separator),
      write_list(H, Y, Separator).
      
    /*
    

    writeq_list(L, Separator_AS)

    writeq_list/2 writeqs each of the elements of a list, writing the Separator between elements. For example, writeq_list(L, $\n $), will write the elements of list L on newlines, indented two spaces.

    Contents

    */
    
    writeq_list([X], _) :-
      !, writeq(X).
    writeq_list([X|Y], Separator) :-
      writeq(X),
      write(Separator),
      writeq_list(Y, Separator).
    
    writeq_list(H, [X], _) :-
      !, writeq(H, X).
    writeq_list(H, [X|Y], Separator) :-
      writeq(H, X),
      write(H, Separator),
      writeq_list(H, Y, Separator).