11

I tried to create something what would work like this:

?- unpacking([[1], [1,2], [3]], Lst1, NewLst).
NewLst=[1,3]

I wrote it like this:

unpacking([], Lst1, Lst1).
unpacking([[H]|T], Lst1, NewLst):-
    append([H], Lst2),
    unpacking(T, Lst2, NewLst).
unpacking([_|T], Lst1, NewLst):-
    unpacking(T, Lst1, NewLst).

and I know that I am doing something wrong. I am starting in Prolog so, need to learn from my mistakes :)

peterh
  • 11,875
  • 18
  • 85
  • 108
Bl4ckCoding
  • 121
  • 9
  • What do you expect for `[[],[1],[2]]`? – false May 01 '17 at 17:40
  • What does this do? What is it supposed to do? What is your problem?... –  May 01 '17 at 18:19
  • @false actually never thought about that input :) because im working with lists that normally have something inside. – Bl4ckCoding May 01 '17 at 18:25
  • @Boris what this does is unpacks a list into another list, but only keep the one-elements list, so instead of a list of lists is a list with non-list elements, which only keeps the one-elements list, kinda confusing i see. – Bl4ckCoding May 01 '17 at 18:26
  • 1
    But why do you have three arguments? Two arguments should be enough I have the feeling.... –  May 01 '17 at 18:43
  • @Bl4ckCoding: You do not "keep the one-elements list" - rather you keep the elements of one-element lists. – false May 01 '17 at 19:06
  • @false ok yeh, my english is not that good, but yeh thats it! – Bl4ckCoding May 01 '17 at 19:26
  • unpack(Xs,Ys) is easiest described as: "Ys is the concatenation of all singleton lists in Xs (in the order they appear in Xs)". – lambda.xy.x May 12 '17 at 13:48

5 Answers5

6

You probably meant:

unpacking([], []).
unpacking([[E]|T], [E|L]) :-
   unpacking(T, L).
unpacking([[]|T], L) :-
   unpacking(T, L).
unpacking([[_,_|_]|T], L) :-
   unpacking(T, L).

There are more concise ways to write this - and more efficient, too.

false
  • 10,264
  • 13
  • 101
  • 209
  • yep, it works man thanks! But could you explain the code a little bit? – Bl4ckCoding May 01 '17 at 19:38
  • It's a pattern matching on the head of the list - the element is either ```[E]``` or ```[]``` or ```[ _, _ |_ ]```. In all cases, you obtain the remaining elements ```L``` by a recursion on the tail ```T```. In the one-element case, ```E``` is prepended to ```L``` whereas in the other cases, ```L``` by itself suffices. – lambda.xy.x May 04 '17 at 11:40
  • 1
    unpacking([[_,_|_]|T, L) is a typo I think. – user27815 May 04 '17 at 15:55
  • Thx! Where is your answer? – false May 04 '17 at 16:05
6

What about this :

%?-unpacking([[a,b,c],[a],[b],[c,d]],Items).
unpacking(Lists,Items):-
 my_tpartition(length_t(1),Lists,Items,Falses).

my_tpartition(P_2,List,Ts,Fs) :- my_tpartition_ts_fs_(List,Ts,Fs,P_2).

my_tpartition_ts_fs_([],[],[],_).
my_tpartition_ts_fs_([X|Xs0],Ts,Fs,P_2) :-
 if_(call(P_2,X), (X=[NX],Ts = [NX|Ts0], Fs = Fs0),
                (Ts = Ts0,     Fs = [X|Fs0])),
my_tpartition_ts_fs_(Xs0,Ts0,Fs0,P_2).

length_t(X,Y,T):-
 length(Y,L1),
 =(X,L1,T).

This is based on Most general higher-order constraint describing a sequence of integers ordered with respect to a relation

* Update*

You could change to 

length_t(X,Y,T):-
 L1 #=< X,
 fd_length(Y,L1),
 =(X,L1,T),!.

length_t(_X,_Y,false).

fd_length(L, N) :-
 N #>= 0,
 fd_length(L, N, 0).

fd_length([], N, N0) :-
 N #= N0.
fd_length([_|L], N, N0) :-
 N1 is N0+1,
 N #>= N1,
 fd_length(L, N, N1).

giving:

?-unpacking([[1],[2,3],[4],[_,_|_]],U).
U= [1,4].

but:

?-unpacking([X],Xs).
X = Xs, Xs = [].
Community
  • 1
  • 1
user27815
  • 4,767
  • 14
  • 28
  • The name tpartition is a bit misleading, for partitioning is typically x -> [x] -> [x] -> [x] – false May 06 '17 at 13:26
  • What do you suggest? how about rel_list_fillers_segments? – user27815 May 08 '17 at 05:52
  • partition'n concat a Haskeller would say. – false May 08 '17 at 11:26
  • 2
    I like the idea behind this proposal very much, +s(0) for that. Unfortunately, due to the use of length/2, the query `?- unpacking([[1],[2,3],[4],[_,_|_]],U).` loops, yielding the solution `U = [1, 4]` over and over again. The accepted version, in comparison, is leaving an unnecessary choice point after yielding the only solution but terminates after hitting `;`. – tas May 10 '17 at 12:02
  • but with the 4th item in the list of the first argument you asking for infinite solutions I think... so it should not terminate? – user27815 May 10 '17 at 16:14
  • btw I think the joke should be s(X) not +s(0) as we dealing with nice peano arithmetic! – user27815 May 10 '17 at 16:18
  • 3
    Yes, exactly. No matter what you substitute for the underscores in `[_,_|_]` it certainly can't become a list with a single element. Hence it's not in the list anyway and it's pointless to iterate possibilities. However, I was thinking along the same lines and couldn't come up with a deterministic solution that terminates for that case so far. Concerning the nice peano arithmetic I submit and regret, please feel s(X)'ed instead ;-) – tas May 10 '17 at 17:33
6

Based on @coder's solution, I made my own attempt using if_ and DCGs:

one_element_([], true).
one_element_([_|_],false).

one_element([], false).
one_element([_|Xs], T) :-
    one_element_(Xs, T).

f([]) -->
    [].
f([X|Xs]) -->
    { if_(one_element(X), Y=X, Y=[]) },
    Y,
    f(Xs).

unpack(Xs,Ys) :-
    phrase(f(Xs),Ys).

I only tried for about 30s, but the queries:

?- Xs = [[] | Xs], unpack(Xs,Ys).
?- Xs = [[_] | Xs], unpack(Xs,Ys).
?- Xs = [[_, _ | _] | Xs], unpack(Xs,Ys).

didn't stop with a stack overflow. In my opinion, the critical one should be the last query, but apparently, SWI Prolog manages to optimize:

?- L = [_,_|_], one_element(L,T).
L = [_3162, _3168|_3170],
T = false.

Edit: I improved the solution and gave it a shot with argument indexing. According to the SWI Manual, indexing happens if there is exactly a case distinction between the empty list [] and the non-empty list [_|_]. I rewrote one_element such that it does exactly that and repeated the trick with the auxiliary predicate one_element_. Now that one_element is pure again, we don't lose solutions anymore:

?- unpack([A,B],[]).
A = [_5574, _5580|_5582],
B = [_5628, _5634|_5636] ;
A = [_5574, _5580|_5582],
B = [] ;
A = [],
B = [_5616, _5622|_5624] ;
A = B, B = [].

but

?- unpack([[a,b,c],[a],[b],[c,d]],Items).
Items = [a, b].

is still deterministic. I have not tried this solution in other Prologs, which might be missing the indexing, but it seems for SWI, this is a solution.

Update: Apparently GNU Prolog does not do this kind of indexing and overflows on cyclic lists:

| ?- Xs = [[] | Xs], unpack(Xs,Ys).

Fatal Error: global stack overflow (size: 32770 Kb, reached: 32768 Kb, environment variable used: GLOBALSZ)
lambda.xy.x
  • 4,918
  • 24
  • 35
  • I wouldn't call it perfect, but it should be at least complete. I'm still unhappy with this choice between two implementations depending on the instantiation of ```Vs```. – lambda.xy.x May 11 '17 at 18:44
  • `unpack([[X|Xs]], []).` fails incorrectly while `Xs = [_|_], unpack([[X|Xs]], []).` succeeds as expected. Why do you use impure constructs at all? Edging cut? – false May 11 '17 at 19:19
  • Cut is a tempting way to make ```oe``` deterministic. I'll see if i can get rid of the impure constructs. – lambda.xy.x May 11 '17 at 19:31
  • 1
    I found a solution, but I'm not sure how specific to SWI it is (it relies on indexing of ```[]``` and ```[_|_]``` arguments). What do you think? – lambda.xy.x May 11 '17 at 20:29
  • Interesting, I have rather expected something along a reified Xs = [] and the like. – false May 11 '17 at 21:36
  • I tried a nested reified ```if_``` but that left choice points open. I'll play around with it tomorrow to check if i missed something. – lambda.xy.x May 11 '17 at 21:55
  • GNU would need full expansion or GC. – false May 12 '17 at 09:22
  • 1
    `one_element` is better called `one_element_t` to insist that the last arg is a truth value. – false Sep 27 '19 at 19:08
  • 1
    With [`set_prolog_flag(double_quotes, chars)`](https://stackoverflow.com/a/8269897/772868) the goal `unpack([[a,b,c],[a],[b],[c,d]],Items).` shrinks to `unpack(["abc","a","b","cd"],Items).`. And `help("append")` is now written as `help(append)` – false Sep 27 '19 at 19:18
5

After some thought, here is my implementation using if_/3:

unpacking(L,L1):-if_( =(L,[]), L1=[], unpack(L,L1)).

unpack([H|T],L):-if_(one_element(H), (H = [X],L=[X|T1],unpacking(T,T1)), unpacking(T,L)).

one_element(X, T) :-
   (  var(X) ->(T=true,X=[_]; T=false,X=[])
    ;  X = [_] -> T = true
    ;  X \= [_] -> T = false).

Some testcases:

?- unpacking([Xss],[]).

Xss = [].

?- unpacking([[1],[2,3],[4],[_,_|_]],U).
U = [1, 4].

?- unpacking([[1],[2,3],[4]],U).
U = [1, 4].

?- unpacking([[E]],[1]), E = 2.
false.

?- unpacking(non_list, []).
false.

?- unpacking([Xs],Xs).
Xs = [_G6221] ;
Xs = [].

UPDATE
To fix the case that @false referred in the comment we could define:

one_element([],false).
one_element([_],true).
one_element([_,_|_],false).

But this leaves some choice points...

coder
  • 12,832
  • 5
  • 39
  • 53
  • 2
    `one_element([_|L], false), L = [_].` fails but `L = [_], one_element([_|L], false).` succeeds. – false May 10 '17 at 16:51
  • @false, but to fix this I don't think that unpacking predicate could be deterministic since we must leave some choice points in one_element/2 ?? – coder May 10 '17 at 18:37
  • Also I don't think this causes inconsistency in unpacking/2 predicate.. – coder May 10 '17 at 18:47
  • 1
    of course it does cause inconsistency! Take `?- unpacking([Xss],[]).` which fails with `Xss = [_,_|_]`. – false May 10 '17 at 19:37
  • OK...I get it but , can we fix that and still retain full determinism ?? A simple solution would be the updated answer but it has some choice points..?? – coder May 10 '17 at 19:57
  • 1
    Correctness first, then you can think about the rest. – false May 10 '17 at 20:09
  • What about the update version (as for correctness) ?? – coder May 10 '17 at 20:10
  • 1
    Correctness OK, now go for efficiency! Preferably **clean** efficiency. – false May 10 '17 at 20:14
  • The different versions are for one_element predicate only which is a small part, I prefer the second because it is clean and simple version (below the first update) but it leaves some choice points, the last attempt is more efficient in my opinion but it is not so pure (due to ground/2 ) so i think second is better... – coder May 11 '17 at 15:54
  • ground/1 is certainly not needed. – false May 11 '17 at 15:59
  • Why? it offers determinism when the list is fully instantiated so no choice points wasted.... It is an attempt to reduce choice point when it is possible...If you think it is not needed due to impurity, that's why I would prefer second, Is it any other reason that you think it is not needed? – coder May 11 '17 at 16:03
  • But it is efficient for, say `[[A,B,C],[V]]` while it could be determinate – false May 11 '17 at 16:06
  • Ok, I see maybe it wasn't a good idea, I will remove the last update... – coder May 11 '17 at 16:07
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/143996/discussion-between-coder-and-false). – coder May 11 '17 at 18:00
1

One way to do it is with a findall I dont think its what the bounty is for though ;)

unpacking(Lists,L1):-
   findall(I,(member(M,Lists),length(M,1),M=[I]),L1).

or 

unpacking2(Lists,L1):-
   findall(I,member([I],Lists),L1).
user27815
  • 4,767
  • 14
  • 28