12

I'm trying to write a procedure in prolog where if L1 = [1,2,3] and L2 = [4,5,6] then L3 = [1,4,2,5,3,6]

so shuffle([1,2,3],[4,5,6],[1,4,2,5,3,6])

I have this so far:

shuffle([X],[Y],[X,Y]).
shuffle([X|Xs],[Y|Ys],_) :- shuffle(Xs,Ys,Z), shuffle(X,Y,Z).

This is my first attempt at writing prolog code so I'm still trying to wrap my head around the syntax, rules and everything.

I understand the logic, I'm just not sure how to implement it so any help would be greatly appreciated!

Thanks!

Edit: I've figured it out. Here's the solution if anyone's interested:

shuffle([X],[Y],[X,Y]).  
shuffle([X|Xs],[Y|Ys],[Z1,Z2|Zs]) :- shuffle([X],[Y],[Z1,Z2]),shuffle(Xs,Ys,Zs).
Sadiq
  • 2,249
  • 2
  • 24
  • 32
  • 1
    nice :) btw you can avoid the first call to shuffle: shuffle([X|Xs],[Y|Ys],[X,Y|Zs]) :- shuffle(Xs,Ys,Zs). – Thanos Tintinidis Nov 11 '11 at 06:23
  • Often simpler is better: thanosQR shows the true solution, while your original loops on backtracking! – CapelliC Nov 11 '11 at 07:23
  • Where are you calling this `shuffle`? This is closer to a `zip` operation. Maybe `flatzip` would be an appropriate name. – Fred Foo Nov 11 '11 at 10:49
  • @larsmans: `interlace` - in analogy to `intersperse`? In any case, OP's relation remains underspecified for `shuffle([],[X],Xs)` and the like. – false Nov 11 '11 at 13:01
  • @false: yes, that would be a good name as well. Mind you, `zip` operations are commonly only defined on equal-length lists. `shuffle` raises the expectation of a [Knuth–Fisher–Yates shuffle](https://secure.wikimedia.org/wikipedia/en/wiki/Fisher%E2%80%93Yates_shuffle). – Fred Foo Nov 11 '11 at 16:41
  • @Uqi: your solution is not defined for `shuffle([], [], X)`. It's also unnecessarily complicated. – Fred Foo Nov 11 '11 at 16:45
  • @larsmans: I was rather surprised how many languages do accept different lengths - see [this comparison](http://en.wikipedia.org/wiki/Map_%28higher-order_function%29#Language_comparison). – false Nov 11 '11 at 16:47
  • 1
    @false: I only just realised that in Prolog, this matters more than in other languages, because it determines whether the reverse operation `shuffle(X,Y,Z)` where only `Z` is bound is deterministic or not. – Fred Foo Nov 11 '11 at 16:55

2 Answers2

22
shuffle([], B, B).
shuffle([H|A], B, [H|S]) :- shuffle(B, A, S).

In this kind of problems, usually the difficult part is not Prolog but identifying the simplest recursive relation that solves it.

salva
  • 9,943
  • 4
  • 29
  • 57
1

Here's the simple solution:

shuffle([], [], []).
shuffle([X|Xs], [Y|Ys], [X,Y|Zs]) :-
    shuffle(Xs,Ys,Zs).

Generalizing this to handle list of unequal length is a matter of changing the base case into:

shuffle(Xs, [], Xs).
shuffle([], Ys, Ys).

although that may generate duplicate solutions. Those can be fixed with a cut if you don't mind the predicate being "one-way".

(Though I still think you should call this flatzip or interlace instead of shuffle.)

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • If you add further facts as you suggest, the best is to enumerate all possibilities to avoid redundant answers. E.g. `shuffle([X|Xs],[],[X|Xs])`. – false Nov 11 '11 at 18:09
  • 1
    @false: I'm sorry, I don't get that remark. My suggestion is to replace the first clause with those two alternative clauses. – Fred Foo Nov 11 '11 at 18:35
  • Even then! A query `shuffle([a],[b],[a,b])` now gives you an answer and a redundant one. – false Nov 11 '11 at 18:49
  • @false: ah, right! A cut might also work here. I see this as a good reason to restrict this operation to equal-length lists ;) – Fred Foo Nov 11 '11 at 20:44
  • Sorry - I cannot understand your lang-u-age: cut? You mean **coupe choix** ?? How sorry I am for this! Ah I should say coupe-choix – false Nov 11 '11 at 20:52
  • Making generalizations to improve termination is one thing. But even to consider the introduction of this unmentionable construct is another thing! – false Nov 11 '11 at 20:53
  • @false: I see you are a Prolog puritan. I used to abhor the cut, but the SWI core developers would hardly accept my contributions without it. Knowing how and when to use the cut separates the Prolog programmers from the logicians :p – Fred Foo Nov 11 '11 at 21:15
  • There is no reason to abhor the cut - as long as it is protected by errors (most often instantiation errors) all around. But here - you want to throw it in without any such predicament! Then, I am unaware of SWI core developer**s**. – false Nov 11 '11 at 22:28
  • @false: Jan would be the BFDL for SWI of course, but I did notice others are watching the main repo closely. – Fred Foo Nov 11 '11 at 23:14