Vorbereitungshaft (Art. 13a ANAG), hat sich ergeben:
A.- Gestützt auf einen anonymen Hinweis hielt die Kantonspolizei Basel-Stadt am 28. März 2000 den aus der Türkei stammenden K._ (geb. 1975) in der Firma X._ an, wo er als Küchenhilfe gearbeitet haben soll. K._ machte gegenüber der Polizei falsche Angaben zu seiner Person, bevor er unter seinem angeblich richtigen Namen um Asyl nachsuchte, worauf ihn die Fremdenpolizei tags darauf in Vorbereitungshaft nahm. Eine Abklärung bei den deutschen Behörden ergab, dass diese am 3. Juli 1996 ein Asylgesuch von K._ abgewiesen hatten, worauf er seit dem
17. November 1997 als verschwunden galt.
B.- Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht prüfte die Haft am 31. März 2000 und bewilligte sie bis zum 27. Juni 2000. Sie stellte fest, dass zwar kein Haftgrund im Sinne von Art. 13a des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) vorliege, doch sei das Asylgesuch offensichtlich rechtsmissbräuchlich, weshalb nicht die Voraussetzungen der Vorbereitungshaft, sondern jene der Ausschaffungshaft (Art. 13b ANAG) zu prüfen seien. Bei K._ bestehe Untertauchensgefahr im Sinne von Art. 13b Abs. 1 lit. c ANAG, da er mit Hilfe von Schleppern in die Schweiz eingereist sei, falsche Angaben zu seiner Person gemacht und hier illegal gearbeitet habe.
C.- Gegen diesen Entscheid gelangte K._ am 4. April 2000 in türkischer Sprache an das Bundesgericht, welches seine Eingabe auf Deutsch übersetzen liess. Er beantragt darin sinngemäss, er sei aus der Haft zu entlassen und in einem Asylantenheim unterzubringen.
Das Verwaltungsgericht des Kantons Basel-Stadt und dessen Einwohnerdienste beantragen, die Beschwerde abzuweisen.
Das Eidgenössische Justiz- und Polizeidepartement liess sich nicht vernehmen. K._ hat sich innert der ihm gesetzten Frist zu den Stellungnahmen nicht mehr geäussert.

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 auseinandersetzen (<ref-ruling> ff.). Bei Laienbeschwerden gegen die Genehmigung der Vorbereitungs- oder Ausschaffungshaft 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 (zumindest auch) gegen seine Haft wendet, nimmt es entsprechende Eingaben als Verwaltungsgerichtsbeschwerden entgegen. Gegenstand des Verfahrens bildet jedoch allein die Rechtmässigkeit der ausländerrechtlichen Administrativhaft, nicht auch die Asyl- bzw. die Wegweisungsfrage (vgl. <ref-ruling> E. 2b S. 61). Soweit der Beschwerdeführer um Asyl nachsucht, ist auf seine Beschwerde deshalb nicht einzutreten; sein entsprechendes Gesuch wird durch das Bundesamt für Flüchtlinge zurzeit bearbeitet.
2.- a) Die zuständige kantonale Behörde kann einen Ausländer, der keine Aufenthaltsbewilligung oder Niederlassungsbewilligung besitzt, während der Vorbereitung des Entscheids über seine Aufenthaltsberechtigung für höchstens drei Monate in Vorbereitungshaft nehmen, wenn er einen der in Art. 13a ANAG genannten Haftgründe erfüllt. Die Fremdenpolizei nahm im vorliegenden Fall an, der Beschwerdeführer habe sich im Asyl- oder Wegweisungsverfahren geweigert, seine Identität offenzulegen, und sei damit seinen Mitwirkungspflichten nicht nachgekommen, weshalb er in Anwendung von Art. 13a lit. a ANAG in Vorbereitungshaft genommen werden könne. Die Haftrichterin ihrerseits stellte ausdrücklich fest, dass kein Haftgrund gemäss Art. 13a ANAG vorliege, das Asylgesuch jedoch rechtsmissbräuchlich erscheine und beim Beschwerdeführer "Untertauchensgefahr" bestehe, weshalb die Vorbereitungshaft gestützt auf den Haftgrund von Art. 13b Abs. 1 lit. c ANAG zu genehmigen sei.
b) Der Auffassung der Haftrichterin kann nicht beigepflichtet werden:
aa) Vorbereitungs- und Ausschaffungshaft unterscheiden sich sowohl in Sinn und Zweck als auch in ihrer Dauer sowie den zu ihrer Anordnung erforderlichen Voraussetzungen.
Die eine dient der Sicherstellung des Wegweisungsverfahrens, wobei der Entscheid über die Aufenthaltsberechtigung in Vorbereitung ist, die andere bezweckt die Sicherstellung des Vollzugs eines bereits ergangenen (wenigstens erstinstanzlichen) Weg- oder Ausweisungsentscheids.
Liegt ein solcher vor, ist die Vorbereitungshaft in der Regel nicht mehr zulässig, und es kann nur noch Ausschaffungshaft angeordnet werden, es sei denn, das Asylgesuch werde erst nachträglich, d.h. nach Anordnung der Ausschaffungshaft gestellt. In diesem Fall lässt das Asylgesuch den bereits vorliegenden Wegweisungsentscheid nicht entfallen und die Ausschaffungshaft kann fortdauern, solange mit dem Abschluss des Asylverfahrens und dem Vollzug der Wegweisung in absehbarer Zeit zu rechnen ist (<ref-ruling> E. 2b S. 380, mit Hinweisen). In den übrigen Fällen ist die Vorbereitungshaft zu prüfen und gegebenenfalls anzuordnen.
Vorbereitungs- und Ausschaffungshaft schliessen sich grundsätzlich aus. Welche Haftart - mit Auswirkungen auf die zulässigen Haftgründe und die gesetzmässige Haftdauer - zu wählen ist, hat die zuständige Behörde aufgrund der konkreten Umstände im Einzelfall 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 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 in diesem Fall für jede der beiden Haftarten im Zeitpunkt der jeweiligen Anordnung die entsprechenden Voraussetzungen erfüllt sein (<ref-ruling> E. 2b S. 380).
bb) Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht hat - im Gegensatz zur Fremdenpolizei - festgestellt, dass kein Haftgrund gemäss Art. 13a ANAG vorliege.
Unter diesen Umständen hätte sie die mit Blick auf das Asylgesuch angeordnete Vorbereitungshaft aber nicht genehmigen dürfen: Soweit sie ausführt, beim Beschwerdeführer bestehe gestützt auf sein bisheriges Verhalten Untertauchensgefahr im Sinne von Art. 13b Abs. 1 lit. c ANAG (vgl. hierzu <ref-ruling> E. 2a), verkennt sie, dass dies zwar eine Ausschaffungshaft, indessen nicht auch eine Vorbereitungshaft zu rechtfertigen vermag. Die Untertauchensgefahr ist kein in Art. 13a ANAG vorgesehener Haftgrund; es kann gestützt darauf keine Vorbereitungshaft verfügt werden (so zu Art. 13a lit. d ANAG das unveröffentlichte Urteil vom 9. Juli 1998 i.S. Mohamed Nasser, E. 2; vgl. Zünd, a.a.O., S. 77), auch wenn dem Haftrichter das vor einem drohenden erstinstanzlichen Wegweisungsentscheid eingereichte Asylgesuch missbräuchlich erscheinen mag.
Nach Art. 33 des Asylgesetzes vom 26. Juni 1998 (SR 142. 31) wird auf das Gesuch einer Person, die sich illegal in der Schweiz aufhält, nicht eingetreten, wenn sie offensichtlich bezweckt, den drohenden Vollzug einer Weg- oder Ausweisung zu vermeiden. Diese Absicht wird vermutet, wenn das Gesuch in engem zeitlichem Zusammenhang mit einer Verhaftung, einem Strafverfahren, dem Vollzug einer Strafe oder dem Erlass einer Wegweisungsverfügung gestellt wird (<ref-law>); indessen gilt diese gesetzliche Vermutung nicht, wenn eine frühere Einreichung des Gesuchs nicht möglich oder nicht zumutbar war oder sich Hinweise auf eine Verfolgung ergeben (<ref-law>). Die Beurteilung der Frage, ob ein Asylgesuch in diesem Sinn missbräuchlich nachgereicht wird, obliegt nicht dem Haftrichter, weshalb er nicht statt auf die (fehlenden) Voraussetzungen der Vorbereitungshaft auf jene der Ausschaffungshaft zurückgreifen darf, um eine Vorbereitungshaft zu genehmigen. Für die Feststellung der Missbräuchlichkeit des Asylgesuchs ist das Bundesamt für Flüchtlinge zuständig, welches die entsprechende Verfügung in der Regel innerhalb von 20 Arbeitstagen seit der Gesuchstellung zu treffen und summarisch zu begründen hat (vgl. <ref-law>). Hinsichtlich der Voraussetzungen für die Vorbereitungshaft ändert sich nichts.
Die Ausschaffungshaft ist nur zulässig bei Vorliegen eines (zumindest erstinstanzlichen) Wegweisungsentscheids, der hier noch nicht ergangen war. Die Vorbereitungshaft ihrerseits kann bloss angeordnet werden, soweit ein entsprechender Haftgrund gegeben ist. Der Bundesrat hat es in der Botschaft vom 4. Dezember 1995 zur Totalrevision des Asylgesetzes sowie zur Änderung des Bundesgesetzes über Aufenthalt und Niederlassung der Ausländer ausdrücklich abgelehnt, einen allgemeinen "zusätzlichen Nichteintretenstatbestand des Rechtsmissbrauchs zu schaffen", da hierzu eine materielle Prüfung des Gesuchs erforderlich wäre (BBl 1995 II 1 ff., insbesondere S. 56). Der Haftrichter kann deshalb nicht seinerseits gestützt auf das Rechtsmissbrauchsverbot einen entsprechenden neuen Haftgrund einführen. Die Vorbereitungshaft bildet einen schweren Eingriff in das verfassungsmässige Recht der persönlichen Freiheit; sie bedarf deshalb einer klaren gesetzlichen Grundlage, die der Richter nicht in Ergänzung des Gesetzes schaffen darf.
3.- a) Es bleibt zu prüfen, ob der Beschwerdeführer den von der Fremdenpolizei angenommenen Haftgrund von Art. 13a lit. a ANAG erfüllt. Das Bundesgericht hat es zwar als problematisch bezeichnet, nicht nur die Haftart, sondern auch den Haftgrund zu substituieren, da es dabei gänzlich neue Voraussetzungen prüfen müsste, welche im kantonalen Verfahren noch gar nicht zur Diskussion standen (vgl. <ref-ruling> E. 2c S. 381; bestätigt im unveröffentlichten Entscheid vom 10. Februar 2000 i.S. Shah, E. 3c). Es ist nicht am Bundesgericht, auf Beschwerde hin die ausländerrechtliche Administrativhaft erst rechtsgültig anzuordnen; es hat lediglich zu prüfen, ob die verfügte und durch den Richter genehmigte Haft Bundesrecht verletzt. Im verwaltungsgerichtlichen Beschwerdeverfahren sind bloss Rechtsverhältnisse zu beurteilen, zu denen die zuständige Behörde vorgängig verbindlich - in Form einer Verfügung - Stellung genommen hat (<ref-ruling> E. 1b S. 36; <ref-ruling> E. 3b S. 313; bezüglich der Ausschaffungshaft: unveröffentlichtes Urteil vom 9. Juli 1998 i.S. Nasser, E. 3). Dies trifft hier insofern zu, als die Fremdenpolizei ihrerseits die Vorbereitungshaft gestützt auf Art. 13a lit. a ANAG angeordnet und die Haftrichterin lediglich deren rechtliche Begründung geändert hat. An diese ist das Bundesgericht indessen nicht gebunden; es kann den angefochtenen Haftentscheid deshalb mit der Begründung bestätigen, die zwar von jener der Vorinstanz abweicht, aber derjenigen der Behörde entspricht, welche die Haft verfügt hat (vgl. Art. 114 Abs. 1 in fine OG; <ref-ruling> E. 2c S. 381; <ref-ruling> E. 1b S. 477; <ref-ruling> E. 4a S. 117).
b) Die Haftrichterin verneinte jedoch zu Recht das Vorliegen dieses Haftgrunds:
aa) 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 offenzulegen, 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 irgendein missliebiges Verhalten während der Vorbereitung des Entscheids über die Aufenthaltsbewilligung erfassen, sondern nur die ausdrücklich erwähnten - als grob beurteilten - Pflichtverletzungen (vgl. 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.; Walter Kälin, Zwangsmassnahmen im Ausländerrecht: Materielles Recht, in: AJP 7/1995, S. 844). 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). Nach dem Bestimmtheitsgebot haben die massgeblichen, die Haft rechtfertigenden Gesichtspunkte im Rechtssatz selber enthalten zu sein (vgl. Haefliger/Schürmann, Die Europäische Menschenrechtskonvention und die Schweiz, 2. Aufl. , Bern 1999, S. 52; Mark E. Villiger, Handbuch der europäischen Menschenrechtskonvention [EMRK], 2. Aufl. , Zürich 1999, Rzn 324 ff.
und 547; Frowein/Peukert, Europäische Menschenrechtskonvention,
2. Aufl. , Kehl/Strassburg/Arlington 1996, Rz. 5 zu Art. 5). Dieser darf deshalb nicht über seinen Sinn und Zweck, den gesetzgeberischen Willen sowie seinen Wortlaut hinaus ausgelegt werden.
bb) Art. 13a ANAG nennt die Untertauchensgefahr nicht als Haftgrund; es kann deshalb gestützt darauf - wie dargelegt - keine Vorbereitungshaft verfügt werden. Dem Gesetzgeber hätte es freigestanden, den umfassenderen Haftgrund der Untertauchensgefahr auch für die Vorbereitungshaft einzuführen. Er hat hiervon indessen abgesehen, weshalb Art. 13a lit. a ANAG nicht im Sinne von Art. 13b Abs. 1 lit. c ANAG ausgeweitet werden darf. Sollte der Gesetzgeber nicht an Fälle wie den vorliegenden gedacht haben, kann die entsprechende Lücke nicht durch den Richter gefüllt werden.
Es erscheint im Übrigen zweifelhaft, ob insofern überhaupt eine echte planwidrige Unvollständigkeit besteht: Der Ausländer, der keine Bewilligung besitzt, keine solche erhalten hat oder der wegen Ablaufs, Widerrufs oder Entzugs über keine solche mehr verfügt, kann weggewiesen werden. Die Wegweisung konkretisiert seine Verpflichtung zur Ausreise und greift grundsätzlich nicht in das Bewilligungsverhältnis ein (vgl. Urs Bolz, Rechtsschutz im Ausländer- und Asylrecht, Basel/Frankfurt a.M. 1990, S. 47; Peter Sulger Büel, Vollzug von Fernhalte- und Entfernungsmassnahmen gegenüber Fremden nach dem Recht des Bundes und des Kantons Zürich, Diss. Bern 1983, S. 88 u. 90), weshalb sie unter Umständen auch formlos erfolgen kann (vgl. 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; siehe indessen auch die Kritik bei Bolz, a.a.O., S. 47 u. S. 132 bzw. Sulger Büel, a.a.O., S. 90 ff.); ihr Vollzug kann in diesem Fall aber, soweit die erforderlichen Voraussetzungen gegeben sind, unmittelbar durch Ausschaffungshaft sichergestellt werden, weshalb keine eigentliche Gesetzeslücke bestehen dürfte. Soweit zwischen den Haftgründen von Art. 13a ANAG und dem am 1. Oktober 1999 in Kraft getretenen <ref-law> ein gewisser Koordinationsbedarf besteht, liegt es allenfalls am Gesetzgeber, hier tätig zu werden.
c) Der Beschwerdeführer hat anfänglich der Polizei gegenüber falsche Angaben gemacht und insofern seine Identität verheimlicht (vgl. Walter Kälin, a.a.O., S. 844). In der Folge hat er jedoch unter seinen durch die Abklärungen in Deutschland erhärteten Personalien um Asyl nachgesucht. Zwar "weigert" sich auch derjenige, seine Identität offenzulegen, der falsche Angaben zu seiner Person macht, doch setzt der Haftgrund von Art. 13a lit. a ANAG eine gewisse Schwere seines Verhaltens und insbesondere die Verletzung einer klaren Mitwirkungspflicht voraus (Wisard, a.a.O., S. 254; Kälin, a.a.O., S. 844). Wer - wie der Beschwerdeführer - ohne Weiteres auf seine ursprünglichen Angaben vor der (formlosen) Wegweisung zurückkommt und seine Ausführungen etwa durch eine Identitätskarte, ein anderes Papier oder sonstwie glaubhaft machen kann, so dass angenommen werden darf, das Asylgesuch sei nunmehr unter der wahren Identität eingereicht, erfüllt den Haftgrund von Art. 13a lit. a ANAG nicht. Der Beschwerdeführer hat sich in diesem Sinn nicht "geweigert", seine Identität im Asyl- oder Wegweisungsverfahren offenzulegen. Seine anfänglich falschen Angaben gegenüber der Polizei erfolgten im Rahmen einer blossen Identitätsabklärung, und sein "nachgeschobenes" Asylgesuch vereitelte zwar eine unmittelbare formlose Wegweisung im Sinne von Art. 12 Abs. 1 ANAG, deren Vollzug mittels Ausschaffungshaft (Art. 13b Abs. 1 lit. c ANAG) hätte sichergestellt werden können (vgl. Kälin, a.a.O., S. 850). Art. 13a lit. a ANAG sanktioniert jedoch nicht alle möglichen Pflichtverletzungen, sondern bloss die dort abschliessend aufgezählten "während der Vorbereitung des Entscheids über [die] Aufenthaltsberechtigung" (BBl 1994 I 322; AB 1994 N 110, AB 1994 S 126). Falsche Angaben bei der Anhaltung durch die Polizei, welche der Betroffene in der Folge im Rahmen seines Asylgesuchs - wie hier - berichtigt, vermögen den Haftgrund von Art. 13a lit. a ANAG nicht zu begründen, auch wenn das Asylgesuch als solches "missbräuchlich" erscheinen mag. Nur Missachtungen von Mitwirkungspflichten, die derart gravierend sind, dass sie die ordnungsgemässe Durchführung des mit dem Asylentscheid verbundenen Wegweisungsverfahrens nicht nur beeinträchtigen, sondern erheblich gefährden, bilden einen Haftgrund im Sinne dieser Bestimmung (Kälin, a.a.O., S. 844).
4.- a) Besteht der einzig geltend gemachte Haftgrund für die Vorbereitungshaft (Art. 13a lit. a ANAG) somit nicht, ist die Verwaltungsgerichtsbeschwerde gutzuheissen und der Beschwerdeführer unverzüglich aus der Haft zu entlassen.
Zwar hat das Bundesgericht wiederholt festgehalten, dass nicht jede Verletzung von Verfahrensvorschriften zu einer Haftentlassung führt (vgl. <ref-ruling> E. 2c S. 109, 110 E. 2a S. 113); vorliegend geht es jedoch nicht um eine solche, sondern um das Fehlen einer materiellen Haftvoraussetzung, was praxisgemäss die Freilassung des Betroffenen zur Folge hat (vgl. Art. 13c Abs. 5 lit. a ANAG; so unveröffentlichtes Urteil vom 9. Juli 1998 i.S. Nasser, E. 3). Selbstverständlich ist es den kantonalen Behörden unbenommen, im Rahmen des bei einem hängigen Asylverfahren Zulässigen die nötigen weiteren Vorkehren für die Sicherstellung einer allfälligen Wegweisung des Beschwerdeführers zu treffen. Sie können ihn verpflichten, sich für weitere Abklärungen zur Verfügung zu halten, und ihm beispielsweise einen festen Aufenthaltsort zuweisen.
b) Weil der Beschwerdeführer obsiegt, ist keine Gerichtsgebühr zu erheben (Art. 156 Abs. 2 OG). Ihm ist keine Parteientschädigung geschuldet, da er sich im vorliegenden Verfahren nicht anwaltlich vertreten liess (vgl.
Art. 159 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, soweit darauf einzutreten ist, und der Entscheid der Einzelrichterin für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt vom 31. März 2000 wird aufgehoben.
2.- Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
3.- Es werden keine Kosten erhoben, und es wird keine Parteientschädigung zugesprochen.
4.- 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: