Re: sorting a linked list
- From: Roby Gamboa <regamboa@xxxxxxxxxxx>
- Date: Fri, 05 Dec 2008 13:57:43 GMT
Hi, Garvin:
I've just joined this news group, and saw your article. Question for you
and the other members of the newsgroup: would it not be more efficient to
go with a direct approach, something like:
% sort_list/2 identifies the head of the sorted list and sorts
% remaining elements using sort_list/3.
sort_list([],[]).
sort_list(List, [e(null,X) | Sorted]) :-
select(e(null,X), List, S1),
sort_list(X, S1, Sorted).
% sort_list/3 selects the list element that has the first
% parameter in the element's first slot, then sorts the
% remaining elements
sort_list(_,[],[]).
sort_list(X, List, [e(X,Y) | Sorted]) :-
select(e(X,Y), List, S1),
sort_list(Y, S1, Sorted).
% sample list provided in the first post.
sample_list([e(c,d),e(null,a),e(b,c),e(a,b)]).
In trying this out with the sample list that you provided, I'm thinking
that this approach is deterministic without relying on cuts or existential
checks (\=) in the body of the clauses, and is fairly efficient with
regard to choice-points and back-tracking. Of course, I haven't really
tried it with a poorly-formed list (no start element, broken links, etc.).
Cheers,
Roby
On Mon, 10 Nov 2008 04:55:37 -0800, garvin wrote:
forget it - now i have the solution. sometimes it helps just writing(RestList,
down the problem. ;)
sort_pairs(PairList, OrderedList) :-
remove_member(PairList, (null, Next), RestList),
sort_pairs__(RestList, Next, OrderedList).
sort_pairs__([], Elem, [Elem]).
sort_pairs__([(null,Next)], _, [Next]). sort_pairs__(PairList, Elem,
[Elem|OrderedList]) :-
Elem \= null,
PairList \= [],
remove_member(PairList, (Elem,Next) , RestList), sort_pairs__
Next, OrderedList).
regards,
garvin
.
- Prev by Date: 15th Prolog Programming Contest
- Next by Date: Very strange bug
- Previous by thread: 15th Prolog Programming Contest
- Next by thread: Very strange bug
- Index(es):
Relevant Pages
|
