[PROLOG]Hoe krijg ik een sublijst van een lijst?

[JeroenTheStig]

Ik ben bezig om mezelf door een Prolog-boek te werken, en nu ben ik aangekomen bij de lijsten. Als extra oefenopdracht staat hier om een predikaat te maken met twee lijsten als argumenten, waarbij de eerste lijst een sublist is van de tweede.

Ik zit nu al een behoorlijk tijdje aan deze opdracht te werken, maar ik kom er niet uit.

Ik had al iets, namelijk dit:

code:

mysubnet([],[]).
mysubnet([X|Xtail],[X|Ytail]) :- mysubnet(Xtail,Ytail).
mysubnet(X,[_|Y]) :- mysubnet(X,Y).

Als ik dit uitprobeer, dan zegt de listener dat [2,4,5] een sublist is van [1,2,3,4,5] en dat is niet de bedoeling.

[3,4] is bijvoorbeeld wel weer een sublist van [1,2,3,4,5].

Is er iemand die mij hiermee kan helpen?

[SWfreak]

Wat je nu doet is altijd in recursie gaan. Wat er ook gebeurt. Je zult echter iets moeten doen als blijkt dat Xtail niet meer overeenkomt met Ytail nadat je een aantal matches hebt gehad. Dat mist hier dus....

[Dr. Cheeks]

Prolog. Fantastische taal! Als het kwartje eenmaal gevallen is dan... En wat dat betreft spijt het me dat het te lang geleden is dat ik intensief in prolog programmeerde. Het kwartje is bij mij weer omhoog gegaan en ik kan je even niet helpen .

Sorry voor deze niet helpende reactie, maar ik moest even mijn enthousiasme kwijt . Succes!

[Wirf]

Volgens mij moet ie zo:

Prolog:

sublist(Lijst, Lijst).
sublist([_X|Xs], Lijst) :-
        sublist(Xs, Lijst).

wat ongeveer betekend:

- Een lijst is een subljst van een lijst als ze hetzelfde zijn
en
- Een sublijst is een sublist als de tail van de list een sublist is. (kromme, onduidelijke zin, maar duidelijker dan dit kan ik het niet uitleggen )

[ Voor 15% gewijzigd door Wirf op 07-03-2003 22:52 ]

[Dr. Cheeks]

Heb er toch nog even over nagedacht:

code:

% een lege lijst is een subnet van een lege lijst.
mysubnet([],[]).

% zoek het begin van het eventuele overeenkomst deel
% zodra gevonden, ga naar mysubnet2
mysubnet([X|Xtail],[X|Ytail]) :- mysubnet2(Xtail,Ytail).
mysubnet(X,[_|Y]) :- mysubnet(X,Y).

% stopconditie
mysubnet2([],[]).
% loop het overeenkomstige deel af
mysubnet2([X|Xtail],[X|Ytail]) :- mysubnet2(Xtail,Ytail).
% zodra de overeenkomst ophoudt, moet X leeg zijn
mysubnet2(X,[_|Y]) :- mysubnet3(X,Y).

% was X leeg? slaag dan, anders niet.
mysubnet3([], Y)

Bovenstaande is nog veels te imperatief waarschijnlijk, maar er blijkt wel uit waarom jouw code in elk geval niet goed is (en feitelijk checked of X een subset is van Y, maar dat wil je niet).

Let wel, bovenstaande is zeker niet 100% goed. Ik hoop dat bijvoorbeeld [2,3,4,5] wel slaagt als subnet van [1,2,3,4,5,6]. Maar het zal falen als subnet van [1,2,3,4,6,2,3,4,5,7], omdat het eerst een match vind (2,3,4) die niet helemaal goed is (5 ontbreekt) en dan stopt mijn code. Terwijl later in de lijst alsnog de juiste waardes naast mekaar staan.

Ik hoop dat het je helpt .

[ Voor 18% gewijzigd door Dr. Cheeks op 07-03-2003 22:57 ]

[Dr. Cheeks]

Wirf schreef op 07 March 2003 @ 22:51:
Volgens mij moet ie zo:
<snip>

Dat werkt niet. Jouw stopconditie is dat op een gegeven moment de lijsten gelijk moeten zijn als je steeds het eerste elementje van de ene lijst afsnoept. Dit hoeft natuurlijk niet waar te zijn terwijl er toch een subnet is...

[Wirf]

hmm.. volgens mij heb ik de eerste keer de vraag niet helemaal goed begrepen

poging twee:

Prolog:

sublist([], _RestLijst).

sublist([X | Xs1], [X | Xs2]) :-
        sublistMatch(Xs1, Xs2).

sublist(SubList, [_X|Xs]) :-
        sublist(SubList, Xs).

sublistMatch([], _RestLijst).

sublistMatch([X | Xs1], [X | Xs2]) :-
        sublistMatch(Xs1, Xs2).

Deze zoekt totdat ie het begin van de sublist heeft gevonden en die moet dan in zijn totaal matchen.

[Soultaker]

Mijn suggestie: mooi top-down redeneren. Wat ik uit jouw verhaal opmaak, is dat een lijst X een sublijst is van lijst Y, wanneer Y gelijk is aan X met een willekeurig aantal elementen ervoor en erachter. Klopt dat? Je zegt dus eigenlijk:

Prolog:

deellijst(Lijst, _ + Lijst + _).

Maar dit is geen geldige prolog code (die + bestaat helemaal niet). Met behulp van "append" kun je de dit effect echter wel via een omweg bereiken:

Prolog:

deellijst(Deellijst, Lijst) :-
    append(X, _, Lijst),
    append(_, Deellijst, X).

Et voila! Een prachtige declaratieve implementatie. Als jouw Prolog-variant geen append kent (zoals bijvoorbeeld VisualProlog) dan is daar wel een versie van te vinden op internet of in je boek. Ook wel leuk om zelf te ontwerpen, trouwens (erg leerzaam).

Prolog is overigens een echte kuttaal (en zeker de dialecten waar ik mee gewerkt heb). Ik wil het best wel eens onderbouwen, maar niet nu. De beste manier om hier achter te komen, is om er gewoon een tijdje mee te werken. Het is een leuke concepttaal, maar voor de meeste serieuze toepassingen absoluut ongeschikt.

Ik heb trouwens al in geen tijden meer in Prolog geprogrammeerd, dus het kan zijn dat er wat foutjes in m'n code zitten.

edit:
Ja dus; met de recursie in het achterhoofd had ik de twee append-regels omgekeerd. Nu klopt de code.

Leuk bijeffect van een declaratieve specificatie zoals deze, is trouwens dat 'ie ook omgekeerd kan worden. Met "deellijst(Welke, [1,2,3,4,5])" kunnen bijvoorbeeld alle deellijsten van [1,2,3,4,5] opgenoemd worden. Daar zitten echter in de huidige implementatie wel dubbelen tussen, omdat de lege lijst als deellijst tussen elk paar elementen gezien wordt!

[ Voor 41% gewijzigd door Soultaker op 08-03-2003 01:43 ]

[JeroenTheStig]

Wow wat een enthousiasme Ik zal even de reacties doorlezen, en dan krijgen jullie zo te horen of het is gelukt!
bedankt!

[JeroenTheStig]

Ik ben eruit gekomen!

dit is het uiteindelijk geworden:

Prolog:

subnet([],[]).

subnet([X|Xtail],[X|Ytail]) :- subnet2(Xtail,Ytail).
subnet(X,[_|Y]) :- subnet(X,Y).

subnet2([],List).
subnet2([X|Xtail],[X|Ytail]) :- subnet2(Xtail,Ytail).

als je eenmaal doorhebt hoe het moet, dan is het eigenlijk best wel simpel

op naar de wiskundige berekeningen

Thanx voor jullie hulp!

[ Voor 4% gewijzigd door JeroenTheStig op 08-03-2003 13:29 ]

[smokalot]

Soultaker schreef op 08 maart 2003 @ 00:09:
Mijn suggestie: mooi top-down redeneren. Wat ik uit jouw verhaal opmaak, is dat een lijst X een sublijst is van lijst Y, wanneer Y gelijk is aan X met een willekeurig aantal elementen ervoor en erachter. Klopt dat? Je zegt dus eigenlijk:

Prolog:

deellijst(Lijst, _ + Lijst + _).

Maar dit is geen geldige prolog code (die + bestaat helemaal niet). Met behulp van "append" kun je de dit effect echter wel via een omweg bereiken:

Prolog:

deellijst(Deellijst, Lijst) :-
    append(X, _, Lijst),
    append(_, Deellijst, X).

Et voila! Een prachtige declaratieve implementatie. Als jouw Prolog-variant geen append kent (zoals bijvoorbeeld VisualProlog) dan is daar wel een versie van te vinden op internet of in je boek. Ook wel leuk om zelf te ontwerpen, trouwens (erg leerzaam).

Prolog is overigens een echte kuttaal (en zeker de dialecten waar ik mee gewerkt heb). Ik wil het best wel eens onderbouwen, maar niet nu. De beste manier om hier achter te komen, is om er gewoon een tijdje mee te werken. Het is een leuke concepttaal, maar voor de meeste serieuze toepassingen absoluut ongeschikt.

Ik heb trouwens al in geen tijden meer in Prolog geprogrammeerd, dus het kan zijn dat er wat foutjes in m'n code zitten.

edit:
Ja dus; met de recursie in het achterhoofd had ik de twee append-regels omgekeerd. Nu klopt de code.

Leuk bijeffect van een declaratieve specificatie zoals deze, is trouwens dat 'ie ook omgekeerd kan worden. Met "deellijst(Welke, [1,2,3,4,5])" kunnen bijvoorbeeld alle deellijsten van [1,2,3,4,5] opgenoemd worden. Daar zitten echter in de huidige implementatie wel dubbelen tussen, omdat de lege lijst als deellijst tussen elk paar elementen gezien wordt!

Mooie oplossing, declaratief gezien. Maar wat ik heb geleerd is dat je append waar mogelijk moet vermijden, omdat het erg veel querries doet, die over het algemeen niet noodzakelijk zijn.

Prolog wordt hier vaak afgeschilderd als kut, klote, [vul een ander scheldwoord in], en op zich kan ik me dat voorstellen vanuit de algemene bedoelingen van de progsels van ons tweakers, maar Prolog heeft ook echt wel hele mooie toepassingen, waar het zeer geschikt voor is. Een van de meestgebruikte toepassingen is denk ik toch taalonderzoek, vandaar ook de ingebouwde DCG-implementatie. Ik moet er niet aan denken dat ik dat soort dingen in Java op zou moeten schirjven...

[Dr. Cheeks]

Jouw code is niet helemaal goed (om dezelfde reden waarom mijn code hierboven niet helemaal sluitend is). Bijvoorbeeld [2,3,4,5] slaagt wel als subnet van [1,2,3,4,5,6]. Maar het zal falen als subnet van [1,2,3,4,6,2,3,4,5,7], omdat het eerst een match vind (2,3,4) die niet helemaal goed is (5 ontbreekt) en dan faalt het predikaat. Terwijl later in de lijst alsnog de juiste waardes naast mekaar staan.

Als 'subnet2' faalt wil dat niet meteen zeggen dat 'subnet' ook moet falen. Dat weet je pas als je de hele lijst afgelopen hebt. Misschien is er later in de lijst nog een match. Maakt het wel wat lastiger, omdat je X moet onthouden. Maar misschien kan dat automatisch recursief opgelost worden.

[Soultaker]

smokalot schreef op 08 March 2003 @ 14:48:
Mooie oplossing, declaratief gezien. Maar wat ik heb geleerd is dat je append waar mogelijk moet vermijden, omdat het erg veel querries doet, die over het algemeen niet noodzakelijk zijn.

Dan hebben ze het je verkeerd geleerd. Je moet nadenken over wat je doet, en bij een taal als Prolog ook heel goed nadenken over hoe de code die je schrijft uitgevoerd gaat worden.

Als je vindt dat mijn code inefficient is, dan wil ik dat graag uitgelegd zien in termen van complexiteit. Ik heb er zelf nog niet over nagedacht, maar op het eerste gezicht zie ik niet in waarom mijn oplossing zo slecht zou zijn (vergeleken met een eenvoudige oplossing zonder append). Kom dus alsjeblieft met een beter argument dan "jouw code is slecht want je gebruikt append".

Prolog wordt hier vaak afgeschilderd als kut, klote, [vul een ander scheldwoord in], en op zich kan ik me dat voorstellen vanuit de algemene bedoelingen van de progsels van ons tweakers, maar Prolog heeft ook echt wel hele mooie toepassingen, waar het zeer geschikt voor is. Een van de meestgebruikte toepassingen is denk ik toch taalonderzoek, vandaar ook de ingebouwde DCG-implementatie. Ik moet er niet aan denken dat ik dat soort dingen in Java op zou moeten schirjven...

Voor algoritmisch programmeren is Prolog waardeloos, omdat je vastzit aan een veel te beperkt aantal datastructuren (alleen lijsten, feitelijk) en te weinig zoektechnieken (alleen backtracking). Je moet dus allerlei slecht leesbare (en schrijfbare) work-arounds gaan verzinnen om toch tot degelijke implementaties te komen.

Daarbij is het typesysteem ofwel afwezig (zoals in GNU Prolog) ofwel beperkt het de herbruikbaarheid van functies (zoals in VisualProlog, waarin je bijvoorbeeld geen generieke append/3, of length/2 kan schrijven ), wat het ontwikkelen van grote complexe applicaties danig in de weg staat. Daarbij verdwijnt in veel praktische implementaties ook de "omkeerbaarheid" van predicaten (dus de eigenschap dat je invoer- en uitvoertermen kunt afwisselen).

Verder zijn predicaten meestal niet vrij van neveneffecten, wat tot gevolg heeft dat de uitwerking van een programma niet los gezien kan worden van optimalisaties op codenivo (red cuts). Dat vind ik een erg vervelende eigenschap, voor een hoog-nivo taal, en druist tegen de declaratieve natuur van de taal in (het hoort niet uit te maken hoe een feit geconstateerd wordt).

Tenslotte is het praktisch onmogelijk om vanuit Prolog op een nette wijze om te gaan met bestaande libraries, waardoor de integratie met externe tools uiterst moeizaam verloopt.

Al met al vind ik Prolog dus een kuttaal voor algemene toepassingen, al zijn er vast wel een aantal specifieke domeinen waar de taal wel handig voor is (maar dan wordt het meer een domeintool dan een programmeertaal, als je het mij vraagt).