2

Test Case

?- decompose([[1,2,8],[3,4],[5,6]], L1, L2).
L1 = [1,3,5], L2 = [[2,8],[4],[6]] ? ;
no

I had tried another implementation however the feedback given was that it was inefficient.

The inefficient implementation

listFirst([], []).
listFirst([H1|T1], [H2|Z]):-
    H1 = [H2|_],
    listFirst(T1, Z).

listFollowers([], []).
listFollowers([H1|T1], [T2|Z]):-
    H1 = [H2|T2],
    listFollowers(T1, Z).

decompose(A,L1,L2) :-
    listFollowers(A, L2),
    listFirst(A, L1).
repeat
  • 18,496
  • 4
  • 54
  • 166
Krishna Kalyan
  • 1,672
  • 2
  • 20
  • 43
  • 2
    The implementation you're showing is inefficient because it's going through the list twice instead of just once. You can combine what your `listFirst` does with what your `listFollowers` does just by including an additional argument. – lurker Dec 07 '15 at 23:38
  • Arguably, said implementation has some inefficiency... but you need not worry about it! – repeat Dec 08 '15 at 07:19

2 Answers2

3

Following up on @findall's previous answer... How about using maplist/4?

list_head_tail([X|Xs], X, Xs).

decompose(Mss, Hs, Ts) :-
   maplist(list_head_tail, Mss, Hs, Ts).

Sample queries:

?- decompose([[a,b,c],[d,e,f]], Heads, Tails).
Heads = [a,d], Tails = [[b,c],[e,f]].

?- decompose([[1,2,8],[3,4],[5,6]], L1, L2).
L1 = [1,3,5], L2 = [[2,8],[4],[6]].
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
2

As lurker says, the functions of your listFirst and listFollowers can be combined into a predicate to do those at once. Like this;

decompose([[H|T]|T0], [H|L1], [T|L2]) :- decompose(T0, L1, L2).
decompose([], [], []).
findall
  • 2,176
  • 2
  • 17
  • 21
  • What's the use of `!` in the first clause? – repeat Dec 08 '15 at 06:30
  • Sorry, I've rearranged that and removed the un-meaningful cut. My poor-functioning interpreter (which I used for testing that) cannot guess there actually is no other choice as entering the 1st case of the predicate. – findall Dec 08 '15 at 06:57
  • 1
    OK. The cut would have rendered the most general query `decompose(Mss,Hs,Ts)` quite incomplete! Which interpreter do you use? – repeat Dec 08 '15 at 07:08
  • Thank you for the correction. That is what I made just for learning purpose. You can see it in my Github page linked from my profile. – findall Dec 08 '15 at 07:21