A.- Der deutsche Staatsangehörige Duelli reiste am 24. April 1972 von Konstanz herkommend mit H. H., die er in Deutschland in die Gewerbsunzucht eingeführt hatte und mit der er ein intimes Verhältnis unterhielt, nach Basel und mietete für beide bis zum 7. Juni 1972 im Hotel Klingental, und bis zur Verhaftung am 20. August 1972 im Hotel Sonne ein Zimmer. Während dieser ganzen Zeit ging Duelli keiner Arbeit nach, sondern lebte ausschliesslich vom Unzuchtserlös der H., von der er auf diese Weise rund Fr. 6000.-- erhielt. Während seiner Inhaftierung beschädigte Duelli am 22. August 1972 vorsätzlich die Lederpolsterung der Schallisolationstüre in der Arrestzelle, wobei Sachschaden in der Höhe von Fr. 430.-- entstand.

Um aus der Anstalt "Lohnhof" auszubrechen, bohrte Duelli in der Zeit vom 7.-10. September 1972 zusammen mit seinem Zellengenossen U. hinter seinem Bett ein ca. 40 cm breites und ca. 50 cm tiefes Loch in die Zellenwand. Dadurch entstand ein Sachschaden von ca. Fr. 200.--.

B.- Am 27. Februar 1973 verurteilte das Strafgericht Basel-Stadt Duelli wegen Zuhälterei im Sinne von Art. 201 Abs. 1 und 2 StGB und wegen wiederholter Sachbeschädigung im Sinne von Art. 145 Abs. 1 StGB zu 3 1/2 Jahren Zuchthaus und zu Landesverweisung auf Lebenszeit. An die Stelle der Freiheitsstrafe liess es die Verwahrung nach Art. 42 StGB treten.

Auf Appellation des Verurteilten hin setzte das Appellationsgericht des Kantons Basel-Stadt am 29. Mai 1973 die Zuchthausstrafe auf 2 Jahre herab, bestätigte die Landesverweisung auf Lebenszeit und hob die Verwahrung auf.

C.- Die Staatsanwaltschaft des Kantons Basel-Stadt ficht das Urteil des Appellationsgerichts insoweit an, als es die vom Strafgericht angeordnete Massnahme aufhob, und beantragt, die Vorinstanz sei anzuweisen, den Beschwerdegegner gemäss Art. 42 StGB auf unbestimmte Zeit zu verwahren.

Gemäss Art. 42 Ziff. 1 Abs. 1 StGB kann vom Richter verwahrt werden, wer unter anderem zahlreiche Verbrechen oder Vergehen vorsätzlich verübt hat und dem deswegen durch Zuchthaus- oder Gefängnisstrafen oder eine Arbeitserziehungsmassnahme die Freiheit während insgesamt mindestens 2 Jahren entzogen war.

Dass diese Voraussetzungen bei Duelli vorliegen, wird auch vom Appellationsgericht nicht in Abrede gestellt. Dieser wurde mit 18 Jahren erstmals straffällig und musste seither bereits 17 Mal bestraft werden, davon 10 mal wegen Diebstahls.

Namentlich seit 1954 ist Duelli immer wieder rasch nach den Verbüssungen schwerer Strafen, bzw. nach der Entlassung aus dem Arbeitshaus, rückfällig geworden. Die letzte erlittene Freiheitsstrafe hat er 1968 verbüsst. Nach seinen eigenen Angaben beträgt die Gesamtdauer des durch Strafen oder Massnahmen bedingten Freiheitsentzuges mindestens 8 Jahre.

Diese Umstände werden nicht etwa dadurch widerlegt, dass Duelli die deutsche Staatszugehörigkeit besitzt oder dass die Mehrzahl der Strafen in Deutschland ausgesprochen und verbüsst worden ist.

Der Vorinstanz ist auch insoweit nicht zu folgen, als sie zur Begründung ihres Entscheides anführt, dem Schutzbedürfnis der schweizerischen Öffentlichkeit werde durch die Landesverweisung auf Lebenszeit genügend Rechnung getragen, weshalb von einer Verwahrung abzusehen sei. Während Art. 42 Ziff. 1 StGB in der Fassung vor der Revision von 1971 dem Richter noch erlaubte, bei einem zu einer Freiheitsstrafe verurteilten Ausländer anstelle der Verwahrung auf Landesverweisung zu erkennen, besteht diese Möglichkeit in der neuen Bestimmung gemäss Bundesgesetz vom 18. März 1971 betreffend die Änderung des Schweizerischen Strafgesetzbuches nicht mehr. Der Richter war daher im vorliegenden Fall nicht befugt, von der strafrechtlichen Massnahme, die anstelle der Strafe zu verhängen ist, deswegen abzusehen, weil er die Landesverweisung für zweckmässiger oder geeigneter hält.

Nicht zugestimmt werden kann ferner der Begründung der Vorinstanz, wonach Duelli sich auch für die in der Schweiz begangenen Delikte vor deutschen Gerichten zu verantworten haben werde, weshalb anzunehmen sei, dass er nach der Ausweisung aus der Schweiz in Deutschland umgehend inhaftiert werde; dadurch sei ihm die Möglichkeit einer Bewährung in der Freiheit verwehrt, was eine unverantwortliche Härte darstelle. Zwar sagt das Gesetz nicht, der Richter müsse nach Art. 42 StGB verfahren, wenn die dort genannten Voraussetzungen erfüllt sind, sondern es stellt die Anordnung einer solchen Massnahme in das Ermessen des Richters; dieser kann sie verhängen. Ermessen bedeutet jedoch nicht freies Belieben. Da Art. 42 StGB die Verwahrung vorsieht, um die Gesellschaft vor dem unverbesserlichen Gewohnheitsverbrecher wirksamer zu schützen, als eine Freiheitsstrafe dies vermöchte, darf der Richter entsprechend diesem Zweckgedanken von der Anordnung der Verwahrungsmassnahme nur absehen, wenn er überzeugt ist, dass schon der Vollzug der Strafe den Verurteilten dauernd vor neuen Rückfällen bewahren werde (BGE 92 IV 79 Erw. 3, BGE 84 IV 147 Erw. 2). Ist von einer Bestrafung des Täters eine solche Wirkung nicht zu erwarten und besteht auch sonstwie keine zureichende Sicherung der Gesellschaft gegen den Rechtsbrecher, so muss der Richter unter den Voraussetzungen des Art. 42 StGB die Verwahrung anordnen. Er darf nicht, wie das die Vorinstanz getan hat, von dieser Massnahme absehen, nur weil der Verurteilte wahrscheinlich in Deutschland in Haft genommen werden wird. Im Hinblick darauf, dass einerseits das Appellationsgericht im angefochtenen Urteil nirgends seine Überzeugung zum Ausdruck bringt, dass allein der Strafvollzug Duelli dauernd vor neuen Rückfällen bewahren werde, und anderseits eine sofortige Inhaftierung des Verurteilten in Deutschland nach Ansicht der Staatsanwaltschaft auf Grund der deutschen Strafprozessordnung als fraglich erscheint, ist im vorliegenden Fall die Verwahrung anzuordnen, da die bisherigen Strafen ihre Wirkung versagten, sich der Täter jeder erzieherischen Beeinflussung als unzugänglich erwies und die Gesellschaft wirksam vor ihm geschützt werden muss. Denn die Verwahrung bezweckt in erster Linie die Sicherung der Öffentlichkeit vor unverbesserlichen und sozialgefährlichen Rechtsbrechern. Für die Entscheidung der Frage nach der Anordnung dieser Massnahme kommt daher den von der Vorinstanz angeführten Gründen nur untergeordnete Bedeutung zu.

Demnach erkennt der Kassationshof:

Die Nichtigkeitsbeschwerde wird gutgeheissen, der angefochtene Entscheid aufgehoben und die Sache zur Neubeurteilung an die Vorinstanz zurückgewiesen.