Vorbereitungshaft (Art. 13a ANAG), hat sich ergeben:
A.- Am 16. März 2000 übergab der deutsche Bundesgrenzschutz der Kantonspolizei Basel-Stadt einen Ausländer, der sich als jugoslawischer Staatsangehöriger aus dem Kosovo mit dem Namen Z._ alias Y._, geb. 1969, ausgab und der am Vorabend bei der Einreise im Zug aus Basel nach Deutschland ohne Reisepapier angehalten und festgenommen worden war. Vor den schweizerischen Behörden führte er an, am 14. März 2000 von Amsterdam über Deutschland in die Schweiz gelangt und nicht jugoslawischer Nationalität zu sein, seine wirkliche Staatsangehörigkeit aber nicht bekannt geben zu wollen. Noch am 16. März 2000 wiesen ihn die Einwohnerdienste des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als kantonale Fremdenpolizei, weg und ordneten die Ausschaffungshaft an.
Am 17. März 2000 wurde der Ausländer dem deutschen Bundesgrenzschutz wieder rückübergeben. Bei der Einvernahme durch die deutschen Behörden gab er nunmehr an, er habe die türkische Staatsangehörigkeit, heisse X._, geb. 1971, sei versteckt in einem Lastwagen aus Italien in die Schweiz eingereist und wolle Asyl beantragen. In der Folge übergab der Bundesgrenzschutz den Ausländer erneut der Kantonspolizei Basel-Stadt, welche ihn den Einwohnerdiensten zuführte.
Bei einer Einvernahme am 20. März 2000 bestätigte er die Aussagen, die er bereits vor dem deutschen Bundesgrenzschutz gemacht hatte, und stellte ein Asylgesuch in der Schweiz.
Ebenfalls am 20. März 2000 ersuchten die Einwohnerdienste mit Fax das Appellationsgericht als Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, um Genehmigung von Ausschaffungshaft. Gleichzeitig verfügten sie indessen Vorbereitungshaft. Noch am gleichen Tag prüfte und genehmigte die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht die Vorbereitungshaft. Im Entscheid wird ausgeführt, die Voraussetzungen der Vorbereitungshaft seien erfüllt; zulässig wäre aber auch die Anordnung von Ausschaffungshaft.
B.- Mit handschriftlicher Eingabe in türkischer Sprache vom 3. April 2000 wendet sich X._ gegen das Urteil der Haftrichterin und beantragt sinngemäss die Haftentlassung.
Gestützt darauf eröffnete das präsidierende Mitglied der II. öffentlichrechtlichen Abteilung des Bundesgerichts ein Verfahren der Verwaltungsgerichtsbeschwerde betreffend die Vorbereitungshaft.
Die Einwohnerdienste schliessen auf Abweisung der Beschwerde. Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht hat auf eine Stellungnahme verzichtet. Das Eidgenössische Justiz- und Polizeidepartement hat sich innert Frist nicht vernehmen lassen. Der Beschwerdeführer nahm die Gelegenheit nicht wahr, sich nochmals zur Sache zu äussern.

Das Bundesgericht zieht in Erwägung:
1.- Die Verwaltungsgerichtsbeschwerde hat die Begehren, deren Begründung mit Angabe der Beweismittel und die Unterschrift des Beschwerdeführers oder seines Vertreters zu enthalten (Art. 108 Abs. 2 OG). Sie muss sich sachbezogen mit dem angefochtenen Entscheid auseinander setzen (<ref-ruling> ff.). Bei Laienbeschwerden gegen die Genehmigung einer ausländerrechtlichen Administrativhaft stellt das Bundesgericht indessen keine hohen Anforderungen an die Beschwerdebegründung (vgl. <ref-ruling> E. 3b S. 277).
Ist daraus - wie hier - ersichtlich, dass sich der Betroffene gegen seine Haft wendet, nimmt es entsprechende Eingaben als Verwaltungsgerichtsbeschwerden entgegen.
2.- a) Die Einwohnerdienste haben den Beschwerdeführer in einer ersten Phase, nachdem er ihnen erstmals überstellt worden war, in Anwendung von Art. 12 Abs. 1 ANAG formlos weggewiesen und Ausschaffungshaft angeordnet. In der Folge wurde er den deutschen Behörden übergeben - und dazu angeblich aus der Haft entlassen, wie in einem entsprechenden Formular in den Akten festgehalten ist. Nachdem er vom deutschen Bundesgrenzschutz nach Änderung seiner Darstellung der tatsächlichen Umstände wieder rücküberstellt worden war, beantragten die Einwohnerdienste zunächst per Fax beim Verwaltungsgericht die Ausschaffungshaft, ordneten in der Folge aber die Vorbereitungshaft an. Die Einzelrichterin am Verwaltungsgericht genehmigte die Haft unter dem Gesichtspunkt der Vorbereitungshaft, hielt jedoch subsidiär fest, auch für die Ausschaffungshaft seien die Voraussetzungen erfüllt. In der Vernehmlassung der Einwohnerdienste an das Bundesgericht berufen sich diese schliesslich wiederum vornehmlich auf Umstände, welche im Zusammenhang mit dem - für die Ausschaffungshaft vorgesehenen - Haftgrund der Untertauchensgefahr wesentlich sind. Es scheint demnach eine gewisse Unsicherheit darüber zu bestehen, welche Haftart im vorliegenden Fall, wenn überhaupt, zur Anwendung gelangt.
b) Nach Art. 13a ANAG kann die zuständige kantonale Behörde bei Vorliegen bestimmter Gründe einen Ausländer, der keine Aufenthalts- oder Niederlassungsbewilligung besitzt, während der Vorbereitung des Entscheides über seine Aufenthaltsberechtigung in Haft nehmen, um die Durchführung eines Wegweisungsverfahrens sicherzustellen.
Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige Behörde gemäss Art. 13b ANAG einen Ausländer zur Sicherstellung des Vollzugs in Ausschaffungshaft nehmen, sofern bestimmte Voraussetzungen erfüllt sind. Erforderlich ist lediglich ein erstinstanzlicher, nicht notwendigerweise auch ein rechtskräftiger Weg- oder Ausweisungsentscheid (vgl. <ref-ruling> E. 2a S. 379; <ref-ruling> E. 2 S. 61; <ref-ruling> ff.), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist.
c) Das Bundesgericht hat in <ref-ruling> E. 2b S. 379 f. ausführlich dargelegt, dass sich Vorbereitungs- und Ausschaffungshaft in mehrfacher Hinsicht unterscheiden.
So ist die Vorbereitungshaft für höchstens drei Monate zulässig (Art. 13a ANAG), während die Ausschaffungshaft zunächst ebenfalls nur für höchstens drei Monate verfügt werden, danach aber um höchstens sechs (weitere) Monate verlängert werden darf, wenn dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegenstehen (Art. 13b Abs. 2 ANAG). Weiter unterliegt die Anordnung von Vorbereitungs- und Ausschaffungshaft verschiedenen Voraussetzungen.
Gewisse Haftgründe sind zwar identisch (vgl. insbes. Art. 13b Abs. 1 lit. b ANAG, welcher ausdrücklich auf Art. 13a lit. b, c und e verweist), andere kommen hingegen nur bei der Vorbereitungs- (so Art. 13a lit. a und d ANAG) oder der Ausschaffungshaft vor (so Art. 13b lit. c ANAG).
Vor allem jedoch unterscheiden sich die beiden Haftarten durch ihre grundsätzliche Voraussetzung. Die Vorbereitungshaft dient - unter gewissen Umständen - der Durchführung eines Wegweisungsverfahrens, währenddem die Ausschaffungshaft die Sicherstellung des Vollzugs eines (wenigstens) erstinstanzlichen Weg- oder Ausweisungsentscheids bezweckt. Liegt ein erstinstanzlicher Weg- oder Ausweisungsentscheid vor, ist Vorbereitungshaft in der Regel nicht mehr zulässig, und es kann nur noch Ausschaffungshaft angeordnet werden. Etwas anderes kann sich einzig dann ergeben, wenn erst nachträglich, d.h. während der Ausschaffungshaft, ein Asylgesuch gestellt wird. Diesfalls ist die Fortsetzung der Ausschaffungshaft nach der Rechtsprechung unter der Voraussetzung zulässig, dass mit dem Abschluss des Asylverfahrens und dem Vollzug der Wegweisung in absehbarer Zeit zu rechnen ist (vgl. Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in RDAF 53/1997 I S. 329); im Übrigen ist Vorbereitungshaft zu prüfen und gegebenenfalls anzuordnen.
Sind die Voraussetzungen beider Haftarten erfüllt, steht den haftanordnenden Behörden mit Blick auf die prospektive Beurteilung der vermutlichen Dauer des Asylverfahrens ein gewisses Ermessen zu.
d) Vorbereitungs- und Ausschaffungshaft schliessen sich demnach gegenseitig grundsätzlich aus. Welche Haftart - mit Auswirkungen auf die zulässigen Haftgründe und die gesetzmässige Haftdauer - in Frage kommt, ist aufgrund der Umstände des Einzelfalles zu prüfen (vgl. Andreas Zünd, Die Rechtsprechung des Bundesgerichts zu den Zwangsmassnahmen im Ausländerrecht, in ZBJV 132/1996 S. 77 f.). Nicht ausgeschlossen ist zwar die Kombination von Vorbereitungs- und Ausschaffungshaft im Sinne einer zeitlichen Abfolge und mit einer theoretischen Höchstdauer von zwölf Monaten Freiheitsentzug, doch müssen auch diesfalls für jede der beiden Haftarten im Zeitpunkt der jeweiligen Anordnung der Haft die entsprechenden Voraussetzungen erfüllt sein (<ref-ruling> E. 2b). Ein gewisses Ermessen besteht einzig dann, wenn nach Anordnung der Ausschaffungshaft ein Asylgesuch eingereicht wird, die Voraussetzungen beider Haftarten erfüllt sind und die Dauer das Asylverfahrens nicht eindeutig prospektiv festgelegt werden kann.
3.- a) Im vorliegenden Fall besteht kein Ermessen bei der Wahl der Haftart, und zwar nicht, weil damit zu rechnen ist, dass das Asylverfahren längere Zeit dauern wird, sondern weil die Voraussetzungen der Vorbereitungshaft nicht erfüllt sind.
b) Nach Art. 13a lit. a ANAG ist die Anordnung der Vorbereitungshaft zulässig, wenn der Ausländer, der keine Aufenthalts- oder Niederlassungsbewilligung besitzt, während der Vorbereitung des Entscheids über seine Aufenthaltsberechtigung sich im Asyl- oder Wegweisungsverfahren weigert, seine Identität offen zu legen, mehrere Asylgesuche unter verschiedenen Identitäten einreicht oder wiederholt einer Vorladung ohne ausreichende Gründe keine Folge leistet. Mit dieser Regelung wollte der Gesetzgeber nicht jedes missliebige Verhalten während der Vorbereitung des Entscheids über die Aufenthaltsbewilligung erfassen, sondern nur die ausdrücklich erwähnten - als grob beurteilten - Pflichtverletzungen (vgl. BBl 1994 I 322; Walter Kälin, Zwangsmassnahmen im Ausländerrecht: Materielles Recht, in AJP 1995 S. 844; Nicolas Wisard, Les renvois et leur exécution en droit des étrangers et en droit d'asile, Basel/Frankfurt a.M. 1997, S. 255 ff.). Er trug damit der Schwere des mit der Haft verbundenen Eingriffs in die persönliche Freiheit und der Bedeutung des Erfordernisses einer hinreichend bestimmten gesetzlichen Grundlage Rechnung (vgl. <ref-law> sowie Art. 5 Ziff. 1 EMRK; Kälin, a.a.O., S. 843).
Diese darf deshalb nicht über ihren Sinn und Zweck, den gesetzgeberischen Willen sowie ihren Wortlaut hinaus ausgelegt werden.
Art. 13a ANAG nennt die Untertauchensgefahr nicht als Haftgrund; es kann deshalb gestützt darauf keine Vorbereitungshaft verfügt werden. Der Gesetzgeber hat davon abgesehen, den umfassenderen Haftgrund der Untertauchensgefahr auch für die Vorbereitungshaft einzuführen, weshalb Art. 13a lit. a ANAG nicht im Sinne von Art. 13b Abs. 1 lit. c ANAG ausgeweitet werden darf. Im Übrigen kann der Ausländer, der keine Bewilligung besitzt, keine solche erhalten hat oder der wegen Ablaufs, Widerrufs oder Entzugs über keine solche mehr verfügt, weggewiesen werden (vgl. insbes. Art. 12 ANAG in Verbindung mit Art. 17 Abs. 1 Satz 1 der Vollziehungsverordnung vom 1. März 1949 zum ANAG, ANAV; SR 142. 201), womit Ausschaffungshaft möglich wird (vgl. zum Ganzen die gleichzeitig mit dem vorliegenden Entscheid ergangenen Urteile des Bundesgerichts vom 27. April 2000 i.S. Kilinc und Palanci).
c) Aus den Akten geht hervor, dass die Vorinstanzen dem Beschwerdeführer in allgemeiner Weise missbräuchliches Verhalten und fehlende Mitwirkung vorwerfen und daraus ableiten, er weigere sich, seine Identität im Asyl- oder Wegweisungsverfahren offen zu legen. Wohl hat der Beschwerdeführer in einer ersten Phase offensichtlich falsche Angaben zu seiner Identität gemacht und sich auch sonst widersprüchlich und unglaubwürdig verhalten. Dennoch konnte er damals als illegal Anwesender ohne weiteres formlos weggewiesen werden. In der zweiten Phase erscheinen seine Angaben zu Identität und Herkunft als wesentlich glaubwürdiger. Zwar liegen (noch) keine Beweise dafür vor; das allein genügt aber für die Annahme, er weigere sich, seine Identität offen zu legen, nicht (vgl. Kälin, a.a.O., S. 844). Wer vor Einreichung des Asylgesuchs auf seine ursprünglichen Angaben zurückkommt, so dass angenommen werden darf, das Asylgesuch sei nunmehr unter der wahren Identität gestellt worden, erfüllt den Haftgrund von Art. 13a lit. a ANAG nicht, wenn die neuen Angaben als glaubhaft erscheinen. Der Beschwerdeführer hat sich in diesem Sinn nicht "geweigert", seine Identität im Asyl- oder Wegweisungsverfahren offen zu legen.
Im angefochtenen Hafturteil wird die Vorbereitungshaft denn auch ausschliesslich mit Umständen begründet, die sich vor Erhebung des Asylgesuches ereignet haben, und es wird gefolgert, es bestünden starke Zweifel an der Mitwirkungsbereitschaft im Asylverfahren. Einen solchen generalklauselartigen Tatbestand sieht Art. 13a lit. a ANAG indessen nicht vor.
d) Damit erweist sich die Anordnung von Vorbereitungshaft im vorliegenden Verfahren als ausgeschlossen.
4.- a) Zu prüfen ist freilich, ob die Haft allenfalls als Ausschaffungshaft genehmigt werden kann. Wie dargelegt, hat die Haftrichterin im angefochtenen Entscheid subsidiär ausgeführt, die entsprechenden Voraussetzungen seien erfüllt.
Sie hat damit das Vorliegen der Haftvoraussetzungen geprüft. Auch wenn sie die Haft im Dispositiv als Vorbereitungshaft genehmigt hat, wäre die Substituierung einer anderen Rechtsgrundlage hier im Hinblick darauf zulässig, dass die Vorbereitungshaft letztlich mit Umständen begründet wurde, welche auch zur Bejahung des Haftgrundes der Untertauchensgefahr nach Art. 13b Abs. 1 lit. c ANAG beigezogen werden. Ausserdem ist - aus gesamthafter Sicht wie auch im Hinblick auf die erstmalige Anordnung von Ausschaffungshaft - die zulässige Höchstdauer für die Haft noch nicht erreicht (vgl. <ref-ruling> E. 2c S. 381).
In verfahrenstechnischer Hinsicht ergibt sich sodann, dass die Einwohnerdienste den Beschwerdeführer in einer ersten Phase formlos weggewiesen und damals auch ausdrücklich Ausschaffungshaft angeordnet haben. Zwar liegt in den Akten ein Formular, wonach zwecks Überstellung des Beschwerdeführers an die deutschen Behörden eine Haftentlassung stattfinde. Nachdem die Ausschaffung aber daran scheiterte, dass der Beschwerdeführer wieder zurückgenommen werden musste, kann nicht von einer tatsächlichen Haftbeendigung ausgegangen werden. Vielmehr wirkte die verfügte Wegweisung genauso fort, wie auch die ursprüngliche Ausschaffungshaft andauerte. Das hält sinngemäss zu Recht auch die Haftrichterin fest. Dass die Einwohnerdienste danach zunächst - per Fax - nochmals die Ausschaffungshaft beantragten, bevor sie dann um Vorbereitungshaft ersuchten, ändert nichts. Das letztere Gesuch ist vielmehr so zu verstehen, dass eine Umwandlung in Vorbereitungshaft angestrebt wurde, was aber, wie dargelegt (E. 3), im vorliegenden Fall mangels Haftgrundes nicht möglich ist. Nach dem Wegfall der von der Haftrichterin zu Unrecht genehmigten Vorbereitungshaft greift somit die ursprünglich angeordnete Ausschaffungshaft.
In diesem Sinne ist lediglich allenfalls das Dispositiv des angefochtenen Entscheids zu substituieren, nachdem eine subsidiäre richterliche Prüfung der Ausschaffungshaft stattgefunden hat und der Beschwerdeführer damit auch keine Instanz verliert.
b) Nach Art. 13c Abs. 2 ANAG stehen für die haftrichterliche Genehmigung freilich höchstens 96 Stunden zur Verfügung. Nachdem der Beschwerdeführer am 16. März 2000 um 05.30 Uhr den schweizerischen Behörden erstmals übergeben worden ist, ab welchem Zeitpunkt die massgebliche Frist lief (zur Fristberechnung Wurzburger, a.a.O., S. 337, mit weiteren Hinweisen; Zünd, a.a.O., S. 75 f.; derselbe, Zwangsmassnahmen im Ausländerrecht: Verfahrensfragen und Rechtsschutz, in AJP 1995 S. 857), und die haftrichterliche Verhandlung am 20. März 2000 um 15.00 Uhr stattfand, wurde diese Frist an sich überschritten. Wohl hätten die Einwohnerdienste bereits früher eine Verhandlung vor dem Haftrichter beantragen können. Indessen hat der Beschwerdeführer durch sein ursprüngliches Verhalten, namentlich seine wechselnden Darstellungen der tatsächlichen Abläufe, selbst verschuldet, dass er zwischen den deutschen und schweizerischen Behörden hin und her geschoben wurde. Nachdem die Einwohnerdienste am 20. März 2000 die Haftüberprüfung beantragt hatten, fand die entsprechende Verhandlung im Übrigen noch am gleichen Tag statt. Unter diesen Umständen bleibt die kurze Verspätung um rund zehn Stunden nach der Rechtsprechung unbeachtlich (so bei vergleichbarer Sachlage die unveröffentlichten Urteile des Bundesgerichts vom 7. Juli 1999 i.S. Lakhdar und vom 25. Oktober 1999 i.S. Buana).
c) Die Anordnung von Ausschaffungshaft setzt nebst einem erstinstanzlichen Weg- oder Ausweisungsentscheid, dessen Vollzug vorläufig nicht möglich ist (vgl. oben E. 2b), das Vorliegen eines der in Art. 13b Abs. 1 ANAG genannten Haftgründe voraus (<ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3). Nach Art. 13b Abs. 1 lit. c ANAG kann Ausschaffungshaft insbesondere verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Gefahr des Untertauchens).
Das trifft namentlich zu, wenn der Ausländer bereits einmal untergetaucht ist, behördlichen Anordnungen keine Folge leistet oder sonst wie durch erkennbar unglaubwürdige und widersprüchliche Angaben die Vollzugsbemühungen der Behörden erschwert (<ref-ruling> E. 3b/aa S. 375, mit Hinweisen).
Der Beschwerdeführer wurde formlos weggewiesen.
Der Vollzug dieser Wegweisung ist mangels Reisepapieren vorläufig nicht möglich. Der Beschwerdeführer hat sich offensichtlich unglaubwürdig und widersprüchlich verhalten und dadurch die Vollzugsbemühungen der Behörden erschwert.
Da die Untertauchensgefahr vom Gesetz generalklauselartig definiert wird, ist insoweit das gesamte Verhalten des Beschwerdeführers von seiner erstmaligen Einreise in die Schweiz an massgeblich. Damit bestehen klare Anhaltspunkte dafür, dass er sich bei einer allfälligen Haftentlassung den Behörden für die Durchführung der Ausschaffung nicht zur Verfügung halten würde, womit Untertauchensgefahr erstellt ist.
d) Gemäss Art. 13c Abs. 5 lit. a ANAG darf die Ausschaffungshaft nur angeordnet oder aufrechterhalten werden, wenn der Vollzug der Weg- oder Ausweisung nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Die Haft ist im Sinne dieser Bestimmung unzulässig, wenn für die Undurchführbarkeit des Vollzugs der Wegweisung triftige Gründe vorliegen oder praktisch feststeht, dass er sich innert der gesetzlich vorgesehenen Haftdauer nicht realisieren lässt (<ref-ruling> E. 5 S. 384; <ref-ruling> E. 3 S. 152 f.).
Dabei haben die Behörden die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehren umgehend zu treffen (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; vgl. <ref-ruling> E. 5 S. 384; <ref-ruling> ff.).
Im vorliegenden Fall ist zwar das Asylgesuch des Beschwerdeführers noch hängig. Das macht aber den Vollzug der erstinstanzlichen Wegweisung nicht undurchführbar. Es gibt vorerst keine triftigen Gründe dafür, dass die Ausschaffung sich nicht innert der gesetzlich vorgesehenen Haftdauer durchführen liesse. Aufgrund der Sachlage, wie sie vor der Haftrichterin bestanden hat, kann demnach gegenwärtig nicht davon ausgegangen werden, der Vollzug der Wegweisung sei nicht innert absehbarer Frist möglich, zumal Hinweise dafür bestehen, dass das Asylgesuch wenig aussichtsreich sein dürfte. Damit hindert auch das hängige Asylverfahren die Anordnung von Ausschaffungshaft nicht (vgl. <ref-ruling> E. 5 S. 384 sowie oben E. 2c).
e) Schliesslich ist zu beachten, dass die dreimonatige Frist für die erstmalige Anordnung der Ausschaffungshaft gemäss Art. 13b Abs. 2 ANAG ab dem 16. und nicht ab dem 17. März 2000 läuft.
5.- a) Somit ist die Verwaltungsgerichtsbeschwerde in dem Sinne teilweise gutzuheissen, dass die von der Haftrichterin am 20. März 2000 als Vorbereitungshaft genehmigte Haft nicht als Vorbereitungshaft, sondern mit Wirkung ab dem 16. März 2000 für drei Monate als Ausschaffungshaft bewilligt werden kann. Im Übrigen ist die Beschwerde abzuweisen.
b) Der Beschwerdeführer unterliegt im Wesentlichen.
Gemessen am Verfahrensausgang würde er weitgehend kostenpflichtig (Art. 156 Abs. 1 und 3 OG). Es rechtfertigt sich jedoch mit Blick auf seine finanziellen Verhältnisse, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 153a Abs. 1 OG). Der Kanton Basel-Stadt hat ohnehin keine Kosten zu tragen (Art. 156 Abs. 2 OG).
c) Die Einwohnerdienste des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als kantonale Fremdenpolizei, werden ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- a) Die Verwaltungsgerichtsbeschwerde wird in dem Sinne teilweise gutgeheissen, dass die von der Haftrichterin am 20. März 2000 als Vorbereitungshaft genehmigte Haft mit Wirkung ab dem 16. März 2000 für drei Monate als Ausschaffungshaft bewilligt wird.
b) Im Übrigen wird die Verwaltungsgerichtsbeschwerde abgewiesen.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, den Einwohnerdiensten, Abteilung Internationale Kundschaft, und der Einzelrichterin für Zwangsmassnahmen am Verwaltungsgericht des Kantons Basel-Stadt sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 27. April 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: