In Prolog, how to sort even and odd numbers represented with symbols and chains of predicates?

Question

The title might be fuzzy, just see the code

number(one, odd).
number(two, even).
number(three, odd).
number(four, even).
number(five, odd).

greaterThan(five, four).
greaterThan(four, three).
greaterThan(three, two).
greaterThan(two, one).

if_larger(A,B):- elder_than(A,B).
if_larger(A,B):- elder_than(A,X),greaterThan(X,B).

even(A):- number(A, even).
odd(A):- number(A, odd).

largest(A):-
    not(greaterThan(_,A)).

largestEven(A):-
    even(A),
    not((if_larger(X,A), even(X))).

largestOdd(A):-
    odd(A),
    not((if_larger(X,A), odd(X))).

how to sort the numbers in the following order: one, three, five, two, four.

I think the solution should be in the following form, however I couldn't figure them out.

next(A, Next):- 
    odd(A), odd(Next),
    ...

next(A, Next):- 
    even(A), even(Next),
    ...

next(A, Next):- 
    odd(A), even(Next),
    ...

Or, is it possible to generate a list, like [one, three, five, two, four].

Answer 1

I will answer my own question. The idea is using final/3 to construct a list of all the numbers, then apply insertion sort on the numbers list.

Implementation

number(five, odd).
number(one, odd).
number(two, even).
number(three, odd).
number(four, even).

greaterThan(five, four).
greaterThan(four, three).
greaterThan(three, two).
greaterThan(two, one).

even(A):- number(A, even).
odd(A):- number(A, odd).

is_larger(A,B):- greaterThan(A,B).
is_larger(A,B):- greaterThan(A,X),is_larger(X,B).

% the order considered even and odd
% which is odd before even, small before large
in_order(A,B):- odd(A), even(B).
in_order(A,B):- odd(A), odd(B), is_larger(B,A).     % smaller numbers comes first
in_order(A,B):- even(A), even(B), is_larger(B,A).   % smaller numbers comes first


% apply insertion sort on A 
insertion_sort(A,B):- sort_helper(A, [], B).
sort_helper([], OldList, OldList).
sort_helper([H|T], OldList, Result):- insert(H, OldList, NewList), sort_helper(T, NewList, Result).

% insert(A,L,Result) put A into L 
insert(A, [], [A]).
insert(A, [H|T], [A,H|T]):- in_order(A,H).
insert(A, [H|T], [H|NewList]):- not(in_order(A,H)), insert(A, T, NewList).

% Interface
oddEvenSortedList(OddEvenSortedList):- findall(A, number(A,_), Numbers), insertion_sort(Numbers, OddEvenSortedList).

Result

?- ['number.pl'].
true.

?- oddEvenSortedList(OddEvenSortedList).
OddEvenSortedList = [one, three, five, two, four].

This question is actually a modified version of my school assignment. The original question is Royal Family Succession in Prolog. I have asked a lot of friends on how to solve this problem, and finally got this solution. I will post the original question here as well.

The old Royal succession rule states that the throne is passed down along the male line according to the order of birth before the consideration along the female line – similarly according to the order of birth. Queen Elizabeth, the monarch of United Kingdom, has four offsprings; namely:- Prince Charles, Princess Ann, Prince Andrew and Prince Edward – listed in the order of birth.