% -*- Mode:Prolog -*-

%  working_directory(_,'/Users/robin/Desktop/UofC/class/449/2021Fall/prolog/').

/*
      This is code for implementing a fold in Prolog.

      All datatypes are represented as structures in Prolog ... because 
      Prolog is untyped it is quite possible to use a fold on a tree 
      datatype for which it is not intended. While part of this code 
      simply recognizes the constructors this does not guarantee that 
      rubbish in will not produce rubbish out! If Prologit does not 
      recognize a structure then it treats that structure as if it 
      were a value.

      The code also demonstrates how the builtin predicate =../2 can 
      be used to build structures which can be evaluated.
      
*/

fold(T,Name,Ans):-
    T=..[Cons|Args],
    length(Args,N),
    fold_fun(Cons,Name,N,ConsFun),!,  % is the functor a constrctor?
    fold_args(Args,Name,Values),    % recursively call the fold
    P =.. [ConsFun,Ans|Values],
    call(P).
fold(T,_,T).       % if it is not a constructor treat it like a value

fold_args([],_,[]).
fold_args([A|As],Name,[B|Bs]):-   %  Evaluate the arguments.
    fold_args(As,Name,Bs),
    fold(A,Name,B).

/*
   Here are some uses of fold to sum the nodes of a search tree
   and to collect the values.
   Recall a seach tree is 
         data STree a = Tip | Branch (STree a) a (STree a)
   we translate a Haskell search tree by transposing to 
   the constructors to start with lowercase.  This gives:
    tip, branch(tip,8,tip), branch(branch(tip,1,tip),8,branch(tip,3,tip))
   as structures corresponding to the elements of STree Int.

   A fold has functions which correspond to the constructors: these 
   are specified in fold_fun/4 below.

*/


:-discontiguous fold_fun/4.  % Prolog likes predicates to be contiguous
                             % to avoid errors one must mark predicates
                             % which may not be contiguous.

% Let us start by summing the elements of the STree ...
% first we name the functions corresponding to the
% constructors using fold_fun.

fold_fun(tip,sumSTree,0,gtip).
fold_fun(branch,sumSTree,3,gbranch).

% Then we define the functions which replace the constructors:

gtip(0).
gbranch(S,N1,N2,N3):- S is N1+N2+N3.

% Try:
%       fold(branch(branch(tip,2,tip),8,branch(tip,14,tip)),
%            sumSTree,Sum)
%
% Try:  fold(branch(t1,t2,t3),sumSTree,Sum)
% Try:  fold(branch(rubbish),sumSTree,Sum)
%  What goes wrong and why?

% Let us collect the values at the nodes in the search tree into a
% list:

fold_fun(tip,collectSTree,0,ctip).
fold_fun(branch,collectSTree,3,cbranch).

ctip([]).
cbranch(X,As,V,Bs):- append(As,[V|Bs],X).

% Try:
%      fold(branch(branch(tip,2,tip),8,branch(tip,14,tip)),
%            collectSTree,Sum)

%   The down side of the lack of typing in prolog is that it harder 
%   to ensure that the program only takes legal inputs.