Monomorphic types such as list correspond to first order skeletons
(RUL programs, as we have seen).
The work on shape and polytypism uses polymorphic types such as
list(T), where T is a type parameter.
Polymorphic types correspond to higher order skeletons
with additional arguments. A type t(T1,T2)
can be mapped to a predicate t(T1,T2,X) which succeeds if
X is of type t(T1,T2). If the definition of type
t contains the constructor c(E1,E2)
(where E1 and E2 are type expressions) then
t/3 will have the clause
t(T1, T2, c(X, Y)) :- call(E1, X), call(E2, Y).
Instances of call/N can be specialised if their first argument
is a nonvariable.
For example, the type list(T) leads to the predicate
list/2 in Program 11. The type rtree(T), an M-way tree
consisting of a term rt(X,Y) where X is of type T
and Y is of type list(rtree(T)) can be defined using
the predicate rtree/2.
list(T, []).
list(T, [X|Xs]) :-
call(T, X), list(T, Xs).
rtree(T, rt(X, RTs)) :-
call(T, X), list(rtree(T), RTs).
Program 11: Higher order skeletons for list(T) and rtree(T)
Higher order skeletons go against the spirit of simplicity embodied in
stepwise enhancement and the control flow of the program above (mutual
recursion through call/N) would certainly be confusing for a
novice programmer. The advantage is that it saves having multiple
copies of similar code. Rather than have separate skeletons for
simple lists, lists of lists, lists of rtrees et cetera, a single higher
order definition can be given. A specialised definition of a type such
as rtree(any) can be obtained by partial evaluation
(eliminating all instances of call/N) and a version of
foldr can be derived as described above. For rtree/1,
the result is Program 12.
rtree_any(rt(X, RTs)) :-
list_rtree_any(RTs).
list_rtree_any([]).
list_rtree_any([RT|RTs]) :-
rtree_any(RT),
list_rtree_any(RTs).
foldrrt(FR, FC, B, rt(X, RTs), V) :-
foldrlrt(FR, FC, B, RTs, V1),
call(FR, X, V1, V).
foldrlrt(FR, FC, B, [], V) :-
B = V.
foldrlrt(FR, FC, B, [RT|RTs], V) :-
foldrrt(FR, FC, B, RT, V1),
foldrlrt(FR, FC, B, RTs, V2),
call(FC, V1, V2, V).
Program 12: Specialised skeleton and version of foldr for rtree