%% lists.pl
%%
%% Author(s):
%%
%% CS 60 Hw 8, part 2
%%
%%


% some "nice" prolog settings...  see assignment
% description for the details on what these do
% -- but it's not crucial to know the details of these Prolog internals
:- set_prolog_flag( prompt_alternatives_on, groundness ).
:- set_prolog_flag(toplevel_print_options, [quoted(true),
     portray(true), attributes(portray), max_depth(999), priority(699)]).

%% Example fac code...

fac( 0, 1 ).
fac( X, N ) :- fac( Y,M ),
	       X is Y+1,
	       N is X*M.


%% Example len code...

len( [], 0 ).
len( [_|R], N ) :- len(R,LenR),
		   N is LenR + 1.


%
% member( E, L ) should be true if
% E is a top-level member of the list L
% member should work when E is a
% variable or bound; L should be bound
%
%





mem( E, [E|_] ).
mem( E, [_|R] ) :- mem( E, R ).



%%
% app( L, M, Both )   (implements append)
%

% base case
app( [], M, M ).
% rec . case
app( [F|R], M, [F|A] ) :- app(R,M,A).

%





% a helper predicate to define a graph
graph1(  [ [a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z] ] ).

% a helper predicate to define a tree
tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
             [ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).

tree2( [ 42, [20, [], []], [] ] ).


%
% nn( BSTree, NNodes ).  (implements nnodes)
%









/*
len( [], 0 ).
len( [_|R], N ) :- len( R, LenR ), N is LenR + 1.

app( [], M, M ).
app( [F|R], M, [F|App] ) :- app( R, M, App ).
*/
% open in order to demo...
nnodes( [], 0 ).
nnodes( [_, L, R], N ) :- nnodes( L, NL ), nnodes( R, NR ), N is 1 + NL + NR.


lastof( E, [E] ).
lastof( E, [_|R] ) :- lastof( E, R ).
/*
rev( [], [] ).
rev( [F|R], Rev ) :- rev( R, RevR ), append( RevR, [F], Rev ).
*/
treefind( E, [E, _, _] ).
treefind( E, [_, L, R] ) :- treefind( E, L ) ; treefind( E, R ).

kid( Par, Graph, K ) :- member( [Par,K], Graph ).  % Succinct!


%% showing off var and nonvar

reverse60( L, Rev ) :- var(L), var(Rev),
    write( 'If you insist...' ), nl,
    L = [42], Rev = [42].

reverse60( L, Rev ) :- var(L), nonvar(Rev),
                        reverse60(Rev, L).

reverse60( [], [] ).

reverse60( [F|R], Rev ) :- nonvar(F), nonvar(R),
                            reverse60( R, RRev ), append( RRev, [F], Rev ).

