Как отсортировать список строк «a», «bcd», «ef» и «ghij» в порядке убывания длины? - PullRequest
Новая
       53

Как отсортировать список строк «a», «bcd», «ef» и «ghij» в порядке убывания длины?

2 голосов
/ 03 апреля 2020

Пол Грэм спросил :

Как вы сортируете список строк «a», «bcd», «ef» и т. Д. «ghij» в порядке убывания длины?

Одно предлагаемое решение было: 

tag_negative_len(Str, NegLen-Str) :-
  atom_length(Str, StrLen),
  NegLen is -1*StrLen.

rem_tag(_-Val, Val).

sort_desc_len(StrLs, Sorted) :-
  maplist(tag_negative_len, StrLs, TaggedLs),
  keysort(TaggedLs, SortedTaggedLs),
  maplist(rem_tag, SortedTaggedLs, Sorted).

Я предполагаю, что приведенный выше код был написан для ISO Prolog, потому что он не использует специфичные для реализации c функции. Пример использования: 

?- sort_desc_len(["a", "bcd", "ef", "ghij"], L).
L = ["ghij", "bcd", "ef", "a"].

Я бы решил это аналогичным образом. Однако решение является чрезвычайно многословным (по сравнению с одним или двумя строками других языков программирования) и загрязняет программу вспомогательными предикатами. Есть ли лучший способ решить проблему в ISO Prolog?

Ответы [ 3 ]

3 голосов
/ 03 апреля 2020 
sort_desc_len(L,S) :-
  findall(N-T,(member(T,L),atom_length(T,M),N is -M),LT),
  keysort(LT,ST),
  findall(T,member(_-T,ST),S).

, то есть findall / 3 реализует замыкания с помощью member / 2. setof / 3 позволит объединить первые вызовы findall и сортировки ключей, но удалит дубликаты ...

Обратите внимание, что atom_length / 2 не может работать с процессором, совместимым с ISO. Строки в двойных кавычках - это списки кодов, а не атомов.

В любом случае, я согласен, что Пролог довольно многословен, когда дело доходит до функционального программирования. Я думаю, причина в том, что у него реляционная модель данных.

1 голос
/ 03 апреля 2020

В моем ответе на вопрос Пола Грэма в Твиттере используются предикат библиотеки Logtalk list::msort/3 и лямбда-выражение, вызывающее предикат стандарта ISO Prolog compare/3 и стандарт де-факто * Предикат 1007 *length/2. Предполагая, что флаг double_quotes установлен в codes (наиболее переносимый параметр; фактически, только некоторые параметры поддерживают некоторые системы Prolog): 

| ?- {types(loader)}.
yes

| ?- list::msort(
         [Order, List1, List2]>>(
             length(List1, N1), M1 is -N1,
             length(List2, N2), M2 is -N2,
             compare(Order, M1, M2)
         ),
         ["a", "bcd"",cd", "ef", "ghij"],
         Sorted
     ).
Sorted = [[98,99,100,34,44,99,100],[103,104,105,106],[101,102],[97]]
yes

При работе на поддерживаемых бэкэнд-компиляторах Prolog, которые не поддерживают предоставить предикат length/2 в качестве встроенного предиката, который мы можем использовать вместо: 

| ?- {types(loader)}.
yes

| ?- list::msort(
         [Order, List1, List2]>>(
             list::length(List1, N1), M1 is -N1,
             list::length(List2, N2), M2 is -N2,
             compare(Order, M1, M2)
         ),
         ["a", "bcd"",cd", "ef", "ghij"],
         Sorted
     ).
Sorted = [[98,99,100,34,44,99,100],[103,104,105,106],[101,102],[97]]
yes

Достаточно забавно, это одно из самых переносимых решений, представленных на сегодняшний день, работающих на 12 системах Prolog (т.е. в все системы, поддерживаемые Logtalk).

Как заметил @ Capelli C, реляционный язык всегда будет обеспечивать более подробное решение по сравнению с функциональным языком.

1 голос
/ 03 апреля 2020

Я просто думаю функционально:

Очевидно, predsort - это предикат для использования. Это на самом деле не ISO, а от library(list)

my_cmp(X,L,R) :- 
   atom_length(L,Llen),atom_length(R,Rlen),
   ((Llen < Rlen) -> X = '>' ;
    (Llen > Rlen) -> X = '<' ;
    X = '=').

sort_desc_len(L,S) :- predsort(my_cmp,L,S).

В зависимости от того, как вычисляется atom_length/2 (т.е. в зависимости от того, нужно ли просто получить скрытую длину значение вместо того, чтобы пересечь строку атома), это может быть довольно быстро. 

:- begin_tests(sort_desc_len).
test(empty)      :- sort_desc_len([],[]).
test(nop)        :- sort_desc_len([aaa,bb,c],[aaa,bb,c]).
test(reverse)    :- sort_desc_len([a,bb,ccc],[ccc,bb,a]).
test(duplicates) :- sort_desc_len([a,bb,bb,ccc],[ccc,bb,a]).
test(stability)  :- sort_desc_len([i,j,k],[i,j,k]).
test(random)     :- sort_desc_len([a,xx,fg,hhh,jk],[hhh,xx,fg,jk,a]).
test(exercise)   :- sort_desc_len([a,bcd,ef,ghij],[ghij,bcd,ef,a]).
:- end_tests(sort_desc_len).

Итак, я Стадо У Лика Тесты ... 

?- run_tests(sort_desc_len).
% PL-Unit: sort_desc_len ....
ERROR: user://4:87:
        test stability: failed

ERROR: user://4:88:
        test random: failed

. done
% 2 tests failed
% 5 tests passed

К сожалению, predsort/3 удаляет дубликаты. Абсолютно должно быть predsort/4, указывающее, должны ли дубликаты быть гонерами. 

?- sort_desc_len([i,j,k],X).
X = [i].

?- sort_desc_len([a,xx,fg,hhh,jk],X).
X = [hhh, xx, a].

FAIL.

Приложение

Менее шумно при использовании compare/3, как предлагается в комментарии repeat .

NB compare/3 вызов с обменом длины влево и вправо. 

my_cmp(X,L,R) :- 
   atom_length(L,Llen),
   atom_length(R,Rlen),
   compare(X,Rlen,Llen).

sort_desc_len(L,S) :- predsort(my_cmp,L,S).

?- run_tests(sort_desc_len).
% PL-Unit: sort_desc_len ....
ERROR: user://1:20:
        test stability: failed

ERROR: user://1:21:
        test random: failed

. done
% 2 tests failed
% 5 tests passed
false.
...