list - Prolog 中的排序

Question

我在 Prolog 中有一个这样的数据结构:

racks =
 [
  [
   (1-1), 1,
   [
    shelf((0-0), 1, [ware_a:[0,10]]),
    shelf((0-1), 2, []),
    shelf((0-2), 3, [])
   ]
 ],
 [
  (2-1), 2,
  [
   shelf((0-0), 4, []),
   shelf((0-1), 5, []),
   shelf((0-2), 6, [])
  ]
 ].

一个货架具有坐标 (x-y)(例如 (1-1))、成本值和货架列表。货架本身具有相同的坐标(货架内)、成本值和内容列表(货架中的商品)。

现在，在执行我的程序期间，机架或架子的顺序可能会混淆。

例如:

racks =
 [
  (2-1), 2,
  [
   shelf((0-0), 4, [ware_c:[50,100]]),
   shelf((0-1), 5, []),
   shelf((0-2), 6, [])
  ]
 ],
 [
  [
   (1-1), 1,
   [
    shelf((0-1), 2, [ware_b:[1,2], ware_a:[10,20]]),
    shelf((0-0), 1, [ware_a:[0,10]]),
    shelf((0-2), 3, [])
   ]
 ].

现在，我正在寻找对此列表进行排序的可能性。它们(货架和其中的架子)应按其成本值排序(坐标无关紧要)。

我该怎么做？!

我在 Prolog 中对列表进行排序方面没有太多经验，所以我想请教一下各位!

感谢您的帮助!!

Answer 1

我认为，就性能而言，更好的选择应该是 keysort :创建一个服务谓词(事实上，确实如此)，从 term 中“提取”键，对配对列表进行键排序，然后相同的服务谓词可以“反转”并丢弃排序列表中的键:

extract_key([A,K|T], K-[A,K|T]).

% note the uppercase Racks. It's a variable!
Racks = [[...]], % your complex structure here
maplist(extract_key, Racks, Keyed),
keysort(Keyed, KeySorted),
maplist(extract_key, Sorted, KeySorted),
% use Sorted in futher processing

效率较低，有predsort/3，使用标准术语顺序可以更容易编写，即 compare/3，但要注意不要返回相等性，否则算法将丢弃整个记录(predsort，像排序一样，丢弃重复项)。

cmprecords(R,[_,K1|_],[_,K2|_]) :- compare(R,K1,K2). % beware, discards on K1==K2

% note the uppercase Racks. It's a variable!
?- Racks = [...], predsort(cmprecords, Racks, Sorted).