Implementieren Sie die member-Prädikat als ein one-liner

Interview-Frage!

Dies ist, wie Sie normalerweise definieren die member relation in Prolog:

member(X, [X|_]).        % member(X, [Head|Tail]) is true if X = Head 
                         % that is, if X is the head of the list
member(X, [_|Tail]) :-   % or if X is a member of Tail,
  member(X, Tail).       % ie. if member(X, Tail) is true.

Definieren, die es mit nur einer Regel.

InformationsquelleAutor der Frage Claudiu | 2009-11-16

  1. 36

    1. Lösung:

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

    2. Demonstration:

      ?- member(a, []).
fail.
?- member(a, [a]).
true ;
fail.
?- member(a, [b]).
fail.
?- member(a, [1, 2, 3, a, 5, 6, a]).
true ;
true ;
fail.

    3. Wie es funktioniert:

      • Suchen wir für ein auftreten des ersten Arguments, Xin dem das zweite argument, [Y|T].
      • Das zweite argument wird davon ausgegangen, dass eine Liste. Y entspricht Ihrem Kopf, T entspricht den Schwanz.
      • Als Ergebnis das Prädikat fehlschlägt, für die leere Liste (wie es sollte).
      • Wenn X = Y (d.h. X werden kann, vereint mit Y) fanden wir dann auch X in der Liste. Ansonsten (;) wir testen, ob X ist in den Schwanz.

    4. Bemerkungen:

      • Dank demütig Kaffee für den Hinweis, dass die Verwendung = (Vereinigung) Erträge flexibler code als mit == (Test auf Gleichheit).

      • Dieser code kann auch verwendet werden, um aufzählen der Elemente einer gegebenen Liste:

        ?- member(X, [a, b]).
X = a ;
X = b ;
fail.

      • Und es kann verwendet werden, um "auflisten" alle Listen enthalten, die ein gegebenes element:

        ?- member(a, X).
X = [a|_G246] ;
X = [_G245, a|_G249] ;
X = [_G245, _G248, a|_G252] ;
...

      • Ersetzen = durch == im obigen code macht es viel weniger flexibel: es würde sofort scheitern member(X, [a]) führen und einen stack-überlauf auf member(a, X) (getestet mit SWI-Prolog-version 5.6.57).

    InformationsquelleAutor der Antwort Stephan202

  2. 20

    Da Sie nicht angegeben, welche anderen Prädikate, die wir erlaubt sind zu verwenden, ich werde versuchen zu betrügen, ein bisschen. :P 

    member(X, L) :- append(_, [X|_], L).

    InformationsquelleAutor der Antwort bcat

  3. 5
    newmember(X, Xs) :-
   phrase(( ..., [X] ),Xs, _).

    Mit

    ... --> [] | [_], ... .

    Tatsächlich, die folgende definition sorgt auch dafür, dass Xs ist eine Liste:

    member_oflist(X, Xs) :-
   phrase(( ..., [X], ... ), Xs).

    InformationsquelleAutor der Antwort false

Schreibe einen Kommentar