%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Ex. 1

insert( X, Lst, P, Res ) :- append( Pre, Post, Lst ),
                            append( Pre, [X|Post], Res ),
                            length( Pre, P ),
                            !.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Ex. 2

insertAll( X, Lst, Res ) :- bagof( R, insertSub( X, Lst, R ), Res ).

insertSub( X, Lst, Res ) :- length( Lst, L ),
                            for( P, 0, L ),
                            insert( X, Lst, P, Res ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Ex. 3

selsort( [], [] ) :- !.
selsort( Lst, S ) :- min_list( Lst, M ),
                     findall( X, (member( X, Lst ), X == M), First ),
                     findall( X, (member( X, Lst ), X =\= M), Rest ),
                     selsort( Rest, SortRest ),
                     append( First, SortRest, S ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Ex. 4

% folds the function Fn with terminator T over the A list.
%
foldr( Fn, T, [A|[]], Res ) :- !,
                               X =.. [Fn, A, T, Res],
                               call( X ).
foldr( Fn, T, [A|As], Res ) :- foldr( Fn, T, As, Next ),
                               X =.. [Fn, A, Next, Res],
                               call( X ).

% returns the lesser of two arbitrary terms
min( A, B, M ) :- (A @=< B -> M = A; M = B ).

% returns the head of a list
head( [A|_], A ).

% returns the minimum of a list of arbitrary terms
mymin( Lst, M ) :- head( Lst, H ),
                   foldr( min, H, Lst, M ).

selsort2( [], [] ) :- !.
selsort2( Lst, S ) :- mymin( Lst, M ),
                      findall( X, (member( X, Lst ), X == M), First ),
                      findall( X, (member( X, Lst ), X \== M), Rest ),
                      selsort2( Rest, SortRest ),
                      append( First, SortRest, S ).