Hi there, I’ve been learning prolog for a few months now, on and off, and I thought I was getting it, but this one looked simple but has me stumped.
I should note I’m using CLP(FD) for this, which I have only just started using on the basis of the voices who say it is more relational and easier to understand its behaviour than the usual prolog arithmetic. I am quite new to it so maybe there is something I don’t understand.
I want to have a predicate that relates a list to its padded version and a number representing the length of a padded version, and I would like this to be two-way, and it should be deterministic as there is only one solution. And of course being pure would be nice (avoiding cuts etc).
E.g. lzp([1,2], L, 4) should give L=[0,0,1,2], and lzp(L, [0,0,1,2], 4) should give L=[1,2].
‘Great’, I thought. ‘An opportunity to try out my relational thinking!’
This seems straightforward enough. A list L is related to it’s padded version P and the padded length N by:
- P is the concatenation of a list of zeroes Z and L.
- the length of Z + the length of L = N
- the first element of L > 0
(condition 3 is true in my use case, and means stripping the padding is unambiguous — without a condition of this sort you can’t tell where the padding ends and the list begins, of course.)
(I should also note in passing N could be treated better in the below, at the moment in my implementations it always needs to be specified, even though it’s redundant in the stripping case and doesn’t allow for the most general case of lzp(X, Y, Z). This isn’t the biggest problem though…)
This seemed like a reasonable implementation:
lzp_rel(L, L1, N) :-
length(L, L_len),
#(L_len) #=< #(N),
#(N_es) #= N - L_len,
#(N_es) #>= 0,
length(Es, N_es),
L = [H |_ ],
#(H) #> 0,
maplist(=(0), Es),
append(Es, L, L1).
and it works:
?- lzp_rel([1,2], L, 4).
L = [0, 0, 1, 2].
?- lzp_rel(L, [0,0,1,2], 4).
L = [1, 2];
except that last call isn’t deterministic, and if you hit that ; it goes off into infinity.
The reason is that length keeps trying larger and larger lists.
So I thought “maybe I need a CLP(FD) aware length”, leading to:
len([], 0).
len([H | T], N) :-
#(N1) #= #(N) - 1,
len(T, N1).
len_to_n(L, N) :-
Len in 1..N,
length(L, Len).
But this still winds up in infinity after the last ; :
?- len_to_n(L, 3).
L = [_] ;
L = [_, _] ;
L = [_, _, _] ;
I don’t understand the behaviour here. doing a trace only shows the following after the last answer:
L = [_, _, _] ;
Redo: (11) length([_5716, _8774, _11842|_11844], _4408{clpfd = ...}) ?
and then no further output. It looks like it’s starting to try larger lists again?
(I think I can probably figure out how to get lists of length ≤ N on backtracking, so that’s my next avenue of attack.)
Anyway, so I tried a recursive approach, which seems, well, more like you’d do it in Lisp:
lzp_rec_(L, L, N) :-
length(L, Length),
#(Length) #= #(N).
lzp_rec_(L, L2, N) :-
#(N) #>= 0, %needed otherwise backtracking will take this to -inf.
L2 = [0 | L3],
#(N1) #= #(N) - 1,
lzp_rec_(L, L3, N1).
lzp_rec(L, L2, N) :-
lzp_rec_(L, L2, N),
L = [H | _],
#(H) #> #(0).
This behaves better but isn’t deterministic in either case, even though there’s only one
result.
?- lzp_rec(L, [0,0,1,2], 4).
L = [1, 2] ;
false.
?- lzp_rec([1, 2], L, 4).
L = [0, 0, 1, 2] ;
false.
The reason of course is that the second lzp_rec_ definition is there to try after the base case. Many prolog list recursion definitions have the base case and recursive case distinguished by pattern matching, e.g. [] in the first and [H | T] in the second, so there isn’t another definition that matches the pattern to try. This must be the first time I’ve ended up writing something different to that, so I haven’t had to think about that before…
I can of course ‘fix’ my definitions by wrapping them in once but that isn’t very satisfactory.
Anyway, I’ve got an avenue to try to writing something that’ll generate lists up to a certain length which might fix the first definition. And perhaps pattern matching (or (shiver) a cut) could fix the second.
But I feel like I must have missed something, because this seemingly simple problem has been hard to find a satisfactory solution to!
)
