prolog - プロローグ マージ リスト内のリストを並べ替える

Question

たとえば、次のように並べ替える必要があります。

?- mergesort([8,1,[4,6,3],2],Sorted).

結果は次のようになります。

Sorted = [1, 2, 8, [3, 4, 6]]

残念ながら、どうすればよいかわかりません。自分で答えを見つけようとしましたが、解決策が見つかりませんでした。現在、結果は次のとおりです。

Sorted = [1, 2, 8, [4, 6, 3]]

私のコード:

mergesort([],[]).
mergesort([A],[A]).
mergesort([A,B|R],S) :-  
   split([A,B|R],L1,L2),
   mergesort(L1,S1),
   mergesort(L2,S2),
   merge(S1,S2,S).

split([],[],[]).
split([A],[A],[]).
split([A,B|R],[A|Ra],[B|Rb]) :-  split(R,Ra,Rb).

merge(A,[],A).
merge([],B,B).
merge([A|Ra],[B|Rb],[A|M]) :-  A @=< B, merge(Ra,[B|Rb],M).
merge([A|Ra],[B|Rb],[B|M]) :-  A @> B,  merge([A|Ra],Rb,M).

よろしくお願いします！

Answer 1

簡単な前処理ステップを書きます。

sortl([H|T],[Hs|Ts]) :-
    (   is_list(H)
    ->  mergesort(H,Gs),
        sortl(Gs,Hs)
    ;   Hs = H
    ),
    sortl(T,Ts).
sortl([],[]).

次に、このように使用できます

?- sortl([8,1,[4,6,[3,4],[1,8],3],2,[1,3,2]],T),mergesort(T,Sorted).
T = [8, 1, [3, 4, 6, [1, 8], [3|...]], 2, [1, 2, 3]],
Sorted = [1, 2, 8, [1, 2, 3], [3, 4, 6, [...|...]|...]]