root/trunk/library/list.lgt

:- object(list,
    implements(listp),
    extends(compound)).

    :- info([
        version is 1.4,
        author is 'Paulo Moura',
        date is 2008/4/22,
        comment is 'List predicates.']).

    :- public(as_difflist/2).
    :- mode(as_difflist(+list, -list), one).
    :- info(as_difflist/2,
        [comment is 'Converts a list to a difference list.',
         argnames is ['List', 'Diffist']]).


    append([], List, List).
    append([Head| Tail], List, [Head| Tail2]) :-
        append(Tail, List, Tail2).


    as_difflist([], Back-Back).
    as_difflist([Head| Tail], [Head| Tail2]-Back) :-
        as_difflist(Tail, Tail2-Back).


    delete([], _, []).
    delete([Head| Tail], Element, Remaining) :-
        (   Head == Element ->
            delete(Tail, Element, Remaining)
        ;   Remaining = [Head| Tail2],
            delete(Tail, Element, Tail2)
        ).

    delete_matches([], _, []).
    delete_matches([Head| Tail], Element, Remaining) :-
        (   \+ \+ Head = Element ->
            delete_matches(Tail, Element, Remaining)
        ;   Remaining = [Head| Tail2],
            delete_matches(Tail, Element, Tail2)
        ).

    empty(List) :-
        List == [].

    flatten(List, Flatted) :-
        flatten(List, [], Flatted).

    flatten(Var, Tail, [Var| Tail]) :-
        var(Var),
        !.
    flatten([], Flatted, Flatted) :-
        !.
    flatten([Head| Tail], List, Flatted) :-
        !,
        flatten(Tail, List, Aux),
        flatten(Head, Aux, Flatted).
    flatten(Head, Tail, [Head| Tail]).

    keysort(List, Sorted) :-
        {keysort(List, Sorted)}.        

    last([Head| Tail], Last) :-
        last(Tail, Head, Last).

    last([], Last, Last).
    last([Head| Tail], _, Last) :-
        last(Tail, Head, Last).

    length(List, Length) :-
        (   integer(Length) ->
            Length >= 0,
            make_list(Length, List)
        ;   length(List, 0, Length)
        ).

    make_list(0, []):-
        !.
    make_list(N, [_| Tail]):-
        M is N-1,
        make_list(M, Tail).

    length([], Length, Length).
    length([_| Tail], Acc, Length) :-
        Acc2 is Acc + 1,
        length(Tail, Acc2, Length).

    max([N| Ns], Max) :-
        max(Ns, N, Max).

    max([], Max, Max).
    max([N| Ns], Aux, Max) :-
        (   N @> Aux ->
            max(Ns, N, Max)
        ;   max(Ns, Aux, Max)
        ).

    member(Element, [Element| _]).
    member(Element, [_| List]) :-
        member(Element, List).


    memberchk(Element, [Element| _]) :-
        !.
    memberchk(Element, [_| List]) :-
        memberchk(Element, List).

    min([N| Ns], Min) :-
        min(Ns, N, Min).

    min([], Min, Min).
    min([N| Ns], Aux, Min) :-
        (   N @< Aux ->
            min(Ns, N, Min)
        ;   min(Ns, Aux, Min)
        ).

    new([]).

    nextto(X, Y, [X, Y| _]).
    nextto(X, Y, [_| Tail]) :-
        nextto(X, Y, Tail).

    nth0(Nth, List, Element) :-
        nth(Element, List, 0, Nth, _).

    nth0(Nth, List, Element, Tail) :-
        nth(Element, List, 0, Nth, Tail).

    nth1(Nth, List, Element) :-
        nth(Element, List, 1, Nth, _).

    nth1(Nth, List, Element, Tail) :-
        nth(Element, List, 1, Nth, Tail).

    nth(Element, List, Acc, Nth, Tail) :-
        (   integer(Nth),
            Nth >= Acc,
            nth_aux(NthElement, List, Acc, Nth, Tail) ->
            Element = NthElement
        ;   var(Nth),
            nth_aux(Element, List, Acc, Nth, Tail)
        ).

    nth_aux(Head, [Head| Tail], Position, Position, Tail).
    nth_aux(Head, [_| List], Count, Position, Tail) :-
        Count2 is Count + 1,
        nth_aux(Head, List, Count2, Position, Tail).

    permutation(List, Permutation) :-
        same_length(List, Permutation),
        permutation2(List, Permutation).

    permutation2([], []).
    permutation2(List, [Head| Tail]) :-
        select(Head, List, Remaining),
        permutation2(Remaining, Tail).

    prefix([], _).
    prefix([Element| Tail], [Element| Tail2]) :-
        prefix(Tail, Tail2).

    reverse(List, Reversed) :-
        reverse(List, [], Reversed, Reversed).

    reverse([], Reversed, Reversed, []).
    reverse([Head| Tail], List, Reversed, [_| Bound]) :-
        reverse(Tail, [Head| List], Reversed, Bound).

    same_length([], []).
    same_length([_| Tail1], [_| Tail2]) :-
        same_length(Tail1, Tail2).

    select(Head, [Head| Tail], Tail).
    select(Head, [Head2| Tail], [Head2| Tail2]) :-
        select(Head, Tail, Tail2).

    sort(List, Sorted) :-
        {sort(List, Sorted)}.       

    sublist(List, List).
    sublist(Sublist, [Head| Tail]):-
        sublist(Tail, Head, Sublist).

    sublist(Sublist, _, Sublist).
    sublist([Head| Tail], _, Sublist):-
        sublist(Tail, Head, Sublist).
    sublist([Head| Tail], Element, [Element| Sublist]):-
        sublist(Tail, Head, Sublist).

    subtract([], _, []).
    subtract([Head| Tail], List, Rest) :-
        (   ::memberchk(Head, List) ->
            subtract(Tail, List, Rest)
        ;   Rest = [Head| Tail2],
            subtract(Tail, List, Tail2)
        ).

    suffix(List, List).
    suffix(List, [_| Tail]) :-
        suffix(List, Tail).

    valid(-) :-     % catch variables and lists with unbound tails
        !,
        fail.
    valid([]).
    valid([_| List]) :-
        valid(List).

:- end_object.