Improving list generation over a range in Prolog

Question

I'm fairly new to Prolog, and falling in love with it more and more. I'm wondering if this implementation can be further generalized or improved upon, and whether it is idiomatic Prolog code?

%% range/2
range(End, List) :-
    End > 0, !,
    range_ascend(0, End, 1, List).

range(End, List) :-
    End < 0,
    range_descend(0, End, 1, List).

%% range/3
range(Start, End, List) :-
    ((Start =< End) ->
        (range_ascend(Start, End, 1, List))
    ;
        (range_descend(Start, End, 1, List))).

%% range/4 (+Start, +End, +Step, -List)
range(Start, End, Step, List) :-
    ((Start =< End) ->
        (range_ascend(Start, End, Step, List))
    ;
        (range_descend(Start, End, Step, List))).

range_descend(Start, End, _, []) :-
    End >= Start, !.
range_descend(Start, End, Step, [Start|Rest]) :-
    Next is Start - Step,
    range_descend(Next, End, Step, Rest).

range_ascend(Start, End, _, []) :-
    Start >= End, !.
range_ascend(Start, End, Step, [Start|Rest]) :-
    Next is Start + Step,
    range_ascend(Next, End, Step, Rest).

Answer 1

One of the main problems of your implementation is that it only works "one way", that is that your code works well when End is set to a certain value, but does not work when it is a variable:

?- range(X,[0,1,2,3]).
ERROR: >/2: Arguments are not sufficiently instantiated

Maybe you do not need such behavior to work but in Prolog it is usually both desirable and elegant that your predicate acts as a true relation, that works in multiple different ways.

However, implementing predicates as such is often more difficult than implementing them to work in a functional way, especially if you're a beginner to Prolog.

I am not going to go into details as to how to improve your code specifically (I think this is more of a question for the Code Review SE site). I am however presenting below a range predicate with better behavior than yours:

range(I, S, [I|R]) :-
    I #=< S,
    if_(I = S,
        R = [],
        (   J #= I + 1,
            range(J, S, R)
        )
    ).

This predicate requires if_/3 and (=)/3 from library(reif), as well as library(clpfd) (which you can include in your program with :- use_module(library(clpfd)).).

As you can see it is much shorter than your implementation, but also works well in multiple different scenarios:

?- range(0,5,L).             % Same behavior as your predicate
L = [0, 1, 2, 3, 4, 5].

?- range(-5,0,L).            % Different behavior from your predicate, but logically sounder
L = [-5, -4, -3, -2, -1, 0]

?- range(1,S,[1,2,3,4,5]).   % Finding the max of the range
S = 5 ;
false.

?- range(I,S,[1,2,3,4,5]).   % Finding both the min and max of the range
I = 1,
S = 5 ;
false.

?- range(I,S,[1,2,X,Y,5]).   % With variables in the range
I = 1,
S = 5,
X = 3,
Y = 4 ;
false.

?- range(1,S,L).             % Generating ranges
S = 1,
L = [1] ;
S = 2,
L = [1, 2] ;
S = 3,
L = [1, 2, 3] ;
S = 4,
L = [1, 2, 3, 4] ;
…

?- range(I,1,L).             % Generating ranges
I = 1,
L = [1] ;
I = 0,
L = [0, 1] ;
I = -1,
L = [-1, 0, 1] ;
I = -2,
L = [-2, -1, 0, 1] ;
…

?- range(I,S,L).             % Generating all possible ranges
I = S,
L = [S],
S in inf..sup ;
L = [I, S],
I+1#=S,
S#>=I,
dif(I, S) ;
L = [I, _G6396, S],
I+1#=_G6396,
S#>=I,
dif(I, S),
_G6396+1#=S,
S#>=_G6396,
dif(_G6396, S) ;
…

I think you can see how many behaviors are displayed here, and how useful it can be to have access to all of them with only one predicate.

This predicate uses Constraint Logic Programming (the clpfd library). CLP allows to write relations between integers (which are the #=< and #= that you see in the code, as opposed to the classic =< and is that you use in low-level arithmetic). This is what does most of the heavy-lifting for us and allows to write short, declarative code about integers (which you cannot do easily with is).

I recommend you to read The Power of Prolog's arithmetic chapter by Markus Triska to learn about CLP arithmetic in Prolog, which is definitely a subject you need to learn if you intend to use Prolog seriously (as I hope I have illustrated in this answer).