Пролог - самый длинный подсписок в списке

Я пытаюсь получить самый длинный подсписок в списке. Мне нужно правило, которое рекурсивно просматривает список списков и определяет, какой из списков имеет наибольшую длину.

Например:
ввод: [[1],[1,2],[],[1,2,3,4],[5,6]]
вывод: [1,2,3,4]

Это то, что у меня есть до сих пор:

max([H|T], Path, Length) :-
  length(H, L),
  (L @> Length -> 
  max(T, H, L) ;
  max(T, Path, Length) ).

Я бы хотел, чтобы max() работало так:

? max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance).
Path = [1,2,3,4]
Distance = 4

Когда я запускаю трассировку, это вывод:

{trace}
| ?- max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance).
      1    1  Call: max([[1],[1,2],[],[1,2,3,4],[5,6]],_307,_308) ? 
      2    2  Call: length([1],_387) ? 
      2    2  Exit: length([1],1) ? 
      3    2  Call: 1@>_308 ? 
      3    2  Exit: 1@>_308 ? 
      4    2  Call: max([[1,2],[],[1,2,3,4],[5,6]],[1],1) ? 
      5    3  Call: length([1,2],_462) ? 
      5    3  Exit: length([1,2],2) ? 
      6    3  Call: 2@>1 ? 
      6    3  Exit: 2@>1 ? 
      7    3  Call: max([[],[1,2,3,4],[5,6]],[1,2],2) ? 
      8    4  Call: length([],_537) ? 
      8    4  Exit: length([],0) ? 
      9    4  Call: 0@>2 ? 
      9    4  Fail: 0@>2 ? 
      9    4  Call: max([[1,2,3,4],[5,6]],[1,2],2) ? 
     10    5  Call: length([1,2,3,4],_587) ? 
     10    5  Exit: length([1,2,3,4],4) ? 
     11    5  Call: 4@>2 ? 
     11    5  Exit: 4@>2 ? 
     12    5  Call: max([[5,6]],[1,2,3,4],4) ? 
     13    6  Call: length([5,6],_662) ? 
     13    6  Exit: length([5,6],2) ? 
     14    6  Call: 2@>4 ? 
     14    6  Fail: 2@>4 ? 
     14    6  Call: max([],[1,2,3,4],4) ? 
     14    6  Fail: max([],[1,2,3,4],4) ? 
     12    5  Fail: max([[5,6]],[1,2,3,4],4) ? 
      9    4  Fail: max([[1,2,3,4],[5,6]],[1,2],2) ? 
      7    3  Fail: max([[],[1,2,3,4],[5,6]],[1,2],2) ? 
      4    2  Fail: max([[1,2],[],[1,2,3,4],[5,6]],[1],1) ? 
      1    1  Fail: max([[1],[1,2],[],[1,2,3,4],[5,6]],_307,_308) ? 

(2 ms) no

Я считаю, что проблема в том, что я не обрабатываю появление пустого набора "[]". Однако я пробовал несколько разных методов и не смог получить желаемый результат.


list recursion longest-path prolog
person bcr    schedule 05.04.2018    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы должны определить предложение окончания цикла и нужен еще один параметр для возврата.

max([], _, Length, Length).
max([H|T], Path, Length, RetLength) :-
  length(H, L),
  ( L @> Length -> 
    max(T, H, L,RetLength) ;
    max(T, Path, Length,RetLength) 
  ).

Тестовое задание:

?- max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance,Len).
Len = 4.
person Taku Koyahata    schedule 05.04.2018