Primitive Recursion in Erlang

pf.erl

%% Daniel Gabriele
%% Jun 20, 2011

-module(pf).
-export([
	reverse/1, succ/1, zero/1, proj/2, pred/1, add/2, minus/2, eq/2, ne/2, 
	min/2, max/2, gt/2, ge/2, lt/2, le/2, len/1, gcd/2
]).


%% List reversal
reverse(List) -> 
	reverse(List, []).
reverse([], Acc) ->
	Acc;
reverse([Head|Tail], Acc) ->
	reverse(Tail, [Head|Acc]).

%% Zero primitive
zero(_X) -> 0.

%% Successor primitive
succ(X) -> X + 1.

%% Projection primitive
proj(Vector, Indices) ->
	proj(Vector, Indices, []).
proj(_Vector, [], Acc) ->
	reverse(Acc);
proj(Vector, [I|Rest], Acc) ->
	proj(Vector, Rest, [lists:nth(I, Vector)|Acc]).

%% Predecessor
pred(X) when X =< 0 -> 0;
pred(X) when X > 0 -> X - 1.

%% A + B
add(A, 0) -> A;
add(A, B) -> succ(add(A, B-1)).

%% A - B
minus(A, 0) -> A;
minus(A, B) -> pred(minus(A, B - 1)).

%% Minimum
min(0, _B, T) -> T;
min(_A, 0, T) -> T;
min(A, B, T) -> min(pred(A), pred(B), T+1).
min(A, B) -> min(pred(A), pred(B), 1).

%% Maximum
max(0, B, T) -> T + B;
max(A, 0, T) -> T + A;
max(A, B, T) -> max(pred(A), pred(B), T+1).
max(A, B) -> max(pred(A), pred(B), 1).

%% ==
eq(A, B) -> minus(1, add(minus(A,B), minus(B,A))).

%% !=
ne(A, B) -> minus(1, eq(A, B)).

%% <
lt(A, B) -> minus(eq(max(A, B), B), eq(A, B)).

%% <=
le(A, B) -> eq(max(A, B), B).

%% >
gt(A, B) -> minus(eq(max(A, B), A), eq(A, B)).

%% >=
ge(A, B) -> eq(max(A, B), A).

%% List length
len([], Count) ->
	Count;
len([_Head|Tail], Count) ->
	len(Tail, succ(Count)).
len(Array) ->
	len(Array, 0).