подсчет элементов списка списков PROLOG

Question

Я пытаюсь подсчитать элементы списка списков.

Я реализовал код следующим образом:

len1([],0).
len1([_X|Xs],N) :- len1(Xs,N1), N is N1+1.

clist([[],[]],0).
clist([Xs,Ys],N):-  len1(Xs,N1),len1(Ys,N2),N is N1+N2.

я повторно использую элемент count (предикаты len1) всписок, и, кажется, работа.Любой может сказать мне, если это хорошая работа, очень плохая или может сделать это, но предпочтительнее другой (без len1).

Я не думаю, что это хорошая реализация, а в остальном кажется не общим.

Пример объявления - это работа только со списком, который содержит два списка внутри.Если я хочу сделать общий?Я думаю, что нужно использовать _Xs, но я пытаюсь изменить свой код и не работает.в частности, я пытаюсь изменить это:

clist([Xs,Ys],N):-  len1(Xs,N1),len1(Ys,N2),N is N1+N2.

в

clist([_Xs],N):-  len1(_Xs,N1),N is N1.

и, очевидно, не работают.

Answer 1

Да, вы были правы, когда хотели обобщить ваше определение.Вместо

clist([[],[]],0).

(ну, во-первых, это должно быть

clist( [] , 0).

Продолжение ...) и

clist([Xs,Ys], N):-  len1(Xs,N1), len1(Ys,N2), N is N1+N2.

, который обрабатывает два списки в списке, измените его на

clist([Xs|YSs], N):-  len1(Xs,N1), len1(YSs,N2), N is N1+N2.

для обработки любого количества списков в списке.Но теперь второй len1 является неправильно примененным .Он получает список списков, а не просто список, как раньше.Столкнувшись с необходимостью обработки списка списков (YSs), чтобы иметь возможность обрабатывать список списков ([Xs|YSs]), мы вернулись к тому, с чего начали.Не правда ли?

Не совсем.У нас уже есть предикат для обработки списка списков - это clist, который мы определяем!Чего ждать?Мы уже определили это?Да, мы еще не закончили это записывать, но мы сделаем это;и когда мы закончим записывать это, мы определим .Рекурсия - это прыжок веры:

clist([Xs|YSs], N):-  len1(Xs,N1), clist(YSs,N2), N is N1+N2.

Более того, этот второй список списков YSs на короче , чем [Xs|YSs]., что является ключом.

И если бы списки были произвольно глубоко вложенными, рекурсия была бы

clist([XSs|YSs], N):-  clist(XSs,N1), clist(YSs,N2), N is N1+N2.

с соответствующим образом исправленнымбазовый (-ые) случай (-ы).

Рекурсия - это прыжок веры: предположим, что у нас уже есть решение, используйте его для обработки небольших случаев рассматриваемой проблемы, просто объедините результаты- вот оно! Решение , которое мы предположили, возникло, потому что мы использовали его, как если бы оно уже существовало.

recursion(   Whole, Solution ) :-
    problem( Whole,           Shell, NestedCases),
    maplist( recursion,              NestedCases, SolvedParts),
    problem(        Solution, Shell,              SolvedParts).

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

Answer 2

Ну, вы можете применить такой же трюк для своего предиката clist/2: вместо решения проблемы для списков с двумя элементами, вы можете рассмотреть два случая:

1. anпустой список [], в этом случае общее число, конечно, равно нулю;и
2. непустой список [H|T], где H - список, а T - список оставшихся списков.В этом случае мы сначала вычисляем длину H, вычисляем (через рекурсию) сумму списков в T и затем суммируем их вместе.

Таким образом, мы можем реализовать это как:

clist([], 0).
clist([H|T], N) :-
    length(H, HN),
    clist(T, TN),
    N is HN + TN.

Выше можно улучшить с помощью аккумулятора: мы можем определить предикат clist/3, который имеет переменную, которая хранит общее количество элементов в списке это далеков случае, если мы достигнем конца списка, мы объединяем ответ с этой переменной, например:

clist(L, N) :-
    clist(L, 0, N).

clist([], N, N).
clist([H|T], N1, N) :-
    length(H, HN),
    N2 is N1 + HN,
    clist(T, N2, N).