Член (расширенный) предикат - найти элемент в списке списков (любого уровня)

Question

Мы все знаем классический предикат Пролога для члена:

member(X, [X|T]).
member(X, [Y|T]) :- member(X,Y).

Я изо всех сил пытаюсь придумать предикат расширенного члена, который я искал для элемента в списке списков (списков и так далее ...). Например:

member(4, [1,2,[3,4,[5]],[6,7,9]]).
TRUE

Answer 1

Мы можем определить такой предикат по трем правилам. X является членом списка L дано L является непустым списком с:

1. X - это его первый элемент;
2. X является членом его первого элемента (который также является списком); или
3. X является членом остальной части списка (его " tail ").

С этими тремя условиями мы можем написать предикат rmember/2 ( рекурсивный член), например:

rmember(X, [X|_]).    %% (1)
rmember(X, [H|_]) :-  %% (2)
    rmember(X, H).
rmember(X, [_|T]) :-  %% (3)
    rmember(X, T).

Первое и третье условие также присутствуют в простом предикате member/2, только второе условие является "уникальным" для рекурсивной проверки члена.

Мы можем немного повысить эффективность описанного выше, сделав предикат с тремя параметрами, с хвостом списка первым, элементом для поиска второго и заголовком списка третьим. Это популярный подход, такой как, например, реализация SWI-Prolog member/2 [swi-doc] .

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

rmember_(_, El, El).
rmember_(_, El, [H|T]) :-
    rmember_(T, El, H).
rmember_([H|T], El, _) :-
    rmember_(T, El, H).

затем мы можем определить rmember/2 в терминах _rmember/3:

rmember(X, [H|T]) :-
    rmember_(T, X, H).