Sachverhalt:
A.
Am 9. Januar 2014 ging A._ nach malischem Recht die polygame Ehe mit dem malischen Staatsangehörigen C._ ein, welcher bereits mit zwei Frauen verheiratet war. Dadurch hat sie die malische Staatsangehörigkeit erworben. Mit Entscheid vom 10. April 2014 hat die Cour d'appel de Bamako, Tribunal de Première Instance de la Commune V du District de Bamako (Mali) die gemeinschaftliche Adoption des am 1. Juli 2012 in Bamako geborenen B._ durch die vorgenannten Ehegatten ausgesprochen.
B.
In der Folge beantragte A._ die Anerkennung und Eintragung dieser Adoption im Schweizerischen Zivilstandsregister. Mit Verfügung vom 18. November 2014 wies das Zivilstandsamt Basel-Stadt das Begehren mit Hinweis auf den Ordre public ab.
Den hiergegen erhobenen Rekurs wies das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt ab.
In teilweiser Gutheissung des hiergegen erhobenen Rekurses anerkannte das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht mit Urteil vom 12. Januar 2016 das malische Adoptionsurteil vom 10. April 2014 für das Mutter-Kind-Verhältnis und wies das Zivilstandsamt an, die betreffende Adoption im Zivilstandsregister einzutragen; es erhob keine Verfahrenskosten, sprach aber auch keine Parteientschädigung zu (Urteil VD.2015.116).
C.
Mit Beschwerde vom 25. Februar 2016 verlangen A._ und B._, in entsprechender Aufhebung des diesbezüglich abweisenden appellationsgerichtlichen Urteils sei ihnen für die kantonalen Rechtsmittelinstanzen eine Parteientschädigung von Fr. 30'065.20 (Fr. 14'390.90 und Fr. 15'674.30) zuzusprechen und im departementalen Verfahren sei überdies die Verfahrensgebühr zu erlassen. Es wurden keine Vernehmlassungen, aber die Akten eingeholt.

Erwägungen:
1.
Angefochten ist die Kostenregelung eines kantonal letztinstanzlichen Entscheides über die Anerkennung und Eintragung einer Adoption. In der Hauptsache stünde die Beschwerde in Zivilsachen offen (Art. 72 Abs. 2 lit. b Ziff. 2, Art. 74 Abs. 1 lit. b, Art. 75 Abs. 1 und Art. 90 BGG). Als ein Teil des Sachentscheids kann auch die Kostenfrage mit dem gleichen Rechtsmittel wie der Sachentscheid an das Bundesgericht weitergezogen werden (vgl. <ref-ruling>). Im Übrigen geht es um Kosten in einem Fr. 30'000.-- übersteigenden Betrag, so dass unter diesem Gesichtspunkt der Beschwerde in Zivilsachen ohnehin nichts im Wege stünde (vgl. <ref-law>).
Die Beschwerdeführerin reicht die Beschwerde auf dem Papier ihrer Gemeinschaftskanzlei ein, unterschreibt aber selbst und legt keine Vollmacht für das ebenfalls als Beschwerdeführer auftretende Kind bei. Gemäss ihrer Darstellung handelt sie nicht anwaltlich, sondern im eigenen Namen und im Übrigen zufolge unangefochtener appellationsgerichtlicher Anerkennung der Adoption als gesetzliche Vertreterin für das Kind.
Die angefochtene Kostenregelung stützt sich auf kantonales Recht, welches nicht unter den Beschwerdegrund von <ref-law> fällt; zulässig sind mithin einzig Verfassungsrügen, namentlich die Rüge der willkürlichen Anwendung der betroffenen kantonalen Normen (BGE 138I 1 E. 2.1 S. 3; <ref-ruling> E. 2.3 S. 231; <ref-ruling> E. 3.1 S. 224; <ref-ruling> E. 5.4 S. 324).
Für Verfassungsrügen, insbesondere für Willkürrügen gilt das strenge Rügeprinzip gemäss <ref-law>. Das Bundesgericht prüft in diesem Bereich nur klar und detailliert erhobene und, soweit möglich, belegte Rügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt; ausserdem ist aufzuzeigen, inwiefern die Behebung der aufgezeigten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-ruling> E. 2.3 S. 266). Soweit es um die Sachverhaltsfeststellung bzw. Beweiswürdigung geht, welche für das Bundesgericht grundsätzlich verbindlich ist (<ref-law>), liegt Willkür vor, wenn der Richter den Sinn und die Tragweite eines Beweismittels offensichtlich nicht erkannt, ohne vernünftigen Grund ein entscheidendes Beweismittel ausser Acht gelassen oder aus den vorhandenen Beweismitteln einen unhaltbaren Schluss gezogen hat; keine Willkür in der Beweiswürdigung ist hingegen gegeben, wenn die von Sachgerichten gezogenen Schlüsse nicht mit der eigenen Darstellung des Beschwerdeführers übereinstimmen (<ref-ruling> E. 4.2 S. 560; <ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 2.3 S. 266). In Bezug auf die Rechtsanwendung liegt Willkür nach ständiger bundesgerichtlicher Praxis nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre; sie ist erst gegeben, wenn ein Entscheid auf einem offensichtlichen Versehen beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 4.3 S. 319; <ref-ruling> E. 6.1 S. 205; <ref-ruling> E. 2.1 S. 168; <ref-ruling> E. 1.2 S. 308 f.).
2.
Das Departement ist von einer in Mali gültig ausgesprochenen gemeinschaftlichen Adoption ausgegangen, welche aber in der Schweiz nicht eintragungsfähig sei, weil der vorausgegangene polygame Eheschluss in der Schweiz nicht anerkennungsfähig und die Mutter im schweizerischen Zivilstandsregister nach wie vor als ledig eingetragen sei; die erfolgte gemeinschaftliche Adoption sei nur Ehepaaren möglich und deshalb in der Schweiz nicht anerkennungsfähig. Im Übrigen würde die Eintragung aufgrund des konkreten Vorgehens der Mutter (polygame malische Heirat ohne eheliches Zusammenleben mit dem dortigen Ehemann bzw. gemäss Einwohnerregister hiesiges Zusammenleben mit einem anderen Mann, welcher nach den Aussagen der Mutter dem Adoptivsohn mitbetreuen soll, in der Absicht, dadurch die malische Staatsangehörigkeit zu erlangen und die Voraussetzungen zur Anerkennung einer gemeinschaftlichen malischen Adoption zu schaffen) auch am Ordre public-Vorbehalt scheitern, zumal die Mutter die in Mali erfolgte gemeinschaftliche Adoption damit faktisch zu einer Einzeladoption werden lasse. Im Zusammenhang mit der von der Mutter geltend gemachten menschlichen Komponente ergebe sich, dass Mutter und Kind zur Zeit in Mali leben würden, wobei auch eine Beziehung zum Adoptivvater bestehe. Es sei nachvollziehbar, dass es für die Mutter eine grosse Härte bedeuten würde, wenn sie das Kind nicht mit in die Schweiz nehmen könnte; umgekehrt müsste es diesfalls aber dauernd auf einen Kontakt zu seinem Vater verzichten und es sei auch ein Aufwachsen des Kindes in der väterlichen Grossfamilie denkbar, zumal das getrennte Familienleben von den Adoptiveltern von Anfang an selbst gewählt worden sei. Im Übrigen könnte die Mutter in der Schweiz mit reellen Chancen auf Gutheissung auch eine Pflegekinderbewilligung beantragen; die schweizerischen Behörden hätten dann die Möglichkeit, die Verhältnisse und Lebensumstände des Kindes fundiert abzukären.
Das Appellationsgericht hat befunden, <ref-law> setze für die Anerkennung einer im Ausland erfolgten Adoption nicht voraus, dass die für eine entsprechende Adoption in der Schweiz vorausgesetzten Anforderungen in allen Teilen erfüllt seien; mithin könne nicht grundsätzlich verlangt werden, dass bei der gemeinschaftlichen Adoption die adoptierenden Eltern verheiratet seien. Zudem würden auch einer polygamen Zweit- oder Drittehe unbekümmert um die fehlende Anerkennungsmöglichkeit dennoch gewisse Rechtswirkungen vor allem im Hinblick auf gemeinsame Kinder zuerkannt. Zwar erscheine das Vorgehen der Beschwerdeführerin insgesamt als missbräuchlich: Nach einer negativen Auskunft der schweizerischen Adoptionsbehörde im Jahr 2012 für eine Adoption nach dem Haager Adoptionsübereinkommen (HAÜ, SR 0.211.221.311) habe sie den bereits zweifach verheirateten, damals rund 60-jährigen malischen Staatsangehörigen C._ geheiratet, offensichtlich um Adoptionsvoraussetzungen zu schaffen; sie habe selbst ausgeführt, "die Option der Adoption in Mali via Eheschliessung mit ihrem langjährigen Freund C._ zu wählen." Mit dem Eheschluss habe sie die malische Staatsbürgerschaft erlangt und damit die Voraussetzung geschaffen für eine binnenstaatliche Adpotion nach malischem Recht einerseits sowie für deren Anerkennung aufgrund der Heimatzugehörigkeit (<ref-law>) andererseits. Nach erfolgter Adoption habe sie offensichtlich nie in einem gemeinsamen Haushalt mit ihrem Mann gelebt, sondern das Kind in Mali vorwiegend allein betreut und "dans un provisoire" in einem Hotel bzw. später mit einer Freundin in einer Wohnung gelebt. Der polygame Eheschluss habe vorliegend der Ermöglichung eines davon unabhängigen weiteren Rechtserfolges, nämlich einer Adoption, gedient; es liege daher mit dem Eheschluss nicht nur eine ungewöhnliche, sondern auch eine sachwidrige Rechtsgestaltung vor. Dies lasse sich auch daraus erkennen, dass die Beschwerdeführerin den schweizerischen Behörden eine vom Ehemann erwirkte Bescheinigung über eine angeblich monogame Ehe eingereicht habe; sie sei sich also der Problematik des von ihr gewählten Weges bewusst gewesen und habe die schweizerischen Behörden durch Vorspiegelung einer gelebten monogamen Ehe mit Blick auf die Anerkennung der Adoption täuschen wollen. Weil die Adoption nach der eigenen Darstellung der Beschwerdeführerin unabdingbare Voraussetzung dafür gewesen sei, dass sie das Kind überhaupt in ihre Obhut habe nehmen können, habe die malische Adoptionsbehörde den Adoptionsentscheid nicht auf der Grundlage einer Kindeswohlprüfung bei bestehender Obhut fällen können; der Entscheid äussere sich nicht zur konkreten Situation des zu adoptierenden Kindes in der Schweiz, wie dies nach dem HAÜ erforderlich wäre und für die Anerkennung gemäss <ref-law> zentral sei. Auch wenn die Beschwerdeführerin seit vielen Jahren Bezüge zu Mali gepflegt und eine Beziehung zu C._ aufgebaut habe, liege insgesamt eine Getzesumgehung vor. Daran habe jedoch das Kind nicht mitgewirkt. Dies allein bedeutet freilich noch nicht, dass a priori mit einer automatischen Anerkennung dem Kindeswohl am besten gedient sei, zumal sonst jeder Form des Adoptionstourismus Tür und Tor geöffnet würde. Vielmehr sei im konkreten Fall zu prüfen, ob die Anerkennung des Resultates der Gesetzesumgehung angesichts der heutigen Situation in einem unerträglichen Widerspruch zur schweizerischen Rechtsauffassung stehe. Dabei könne die seit der angefochtenen Verfügung erfolgte Entwicklung nicht unberücksichtigt bleiben. Die Beschwerdeführerin sei bereits acht Monate vor der Adoption monatlich für rund eine Woche nach Mali gereist und habe dort mit dem Kind Zeit im Kinderheim verbracht. Nach der erfolgten Adoption habe sich die beabsichtigte Ausreise in die Schweiz verzögert, weil das Kind zunächst keine Einreisebewilligung in die Schweiz erhalten habe. Die Beschwerdeführerin habe mit ihm in einem Hotel in Bamako gewohnt, wo sie vom 800 Kilometer entfernt wohnenden Adoptivvater gelegentlich besucht worden sei. Die Beschwerdeführerin habe das Kind nunmehr seit April 2014 ausschliesslich betreut und erzogen und sie habe durch ihre monatelange Landesabwesenheit auch eine Gefährdung ihrer beruflichen und wirtschaftlichen Existenz als selbständig erwerbstätige Anwältin in Kauf genommen. Dieses Engagement sei ein starker Hinweis dafür, dass der Adoption keine fremden Motive zu Grunde gelegen hätten und sie sich für das Wohl des Kindes sorge. Eine heutige Rückkehr für das Kind nach Mali komme nicht in Frage, zumal das Kind noch nie in der dortigen polygamen Familie gelebt habe. Die Beschwerdeführerin sei eine geeignete Adoptivmutter und die Voraussetzungen einer Adoption nach <ref-law> wären grundsätzlich erfüllt. Angesichts der konkreten Umstände des Einzelfalles im jetzigen Zeitpunkt könne die Adoption zwischen Mutter und Kind anerkannt werden, ohne dass dadurch der Ordre public verletzt werde, nicht jedoch diejenige zwischen Vater und Kind, weil zu ihm keine gelebte Beziehung bestehe und auch zwischen den Adoptiveltern keine in der Schweiz eintragungsfähige Ehe bestehe.
Was die vorliegend strittige Kostenregelung anbelangt, hat das Appellationsgericht auf Verfahrenskosten verzichtet, aber befunden, es sei keine Entschädigung für die kantonalen Verfahren auszurichten und im Übrigen an der Spruchgebühr für den Departementsentscheid festzuhalten. Einerseits hätten sich die Voraussetzungen für die teilweise Gutheissung der Begehren erst aufgrund der Entwicklung während des appellationsgerichtlichen Verfahrens verwirklicht und sei der angefochtene Entscheid im Zeitpunkt des Erlasses korrekt gewesen. Zum anderen habe die Beschwerdeführerin durch ihr eigenes Verhalten, welches grundsätzlich gegen den schweizerischen Ordre public verstossen habe, das vorliegende Verfahren provoziert. Durch das Einreichen einer auf monogam lautenden malischen Heiratsurkunde habe sie zudem gegen Normen des schweizerischen Rechts und gegen ihre Mitwirkungspflicht im Verfahren verstossen. Insgesamt habe sie in zivilrechtlich vorwerfbarer Weise gegen Verhaltensnormen verstossen und dadurch das Verfahren veranlasst. Aus all diesen Gründen sei ihr Gesuch um Ausrichtung einer Parteientschädigung für die kantonalen Verfahren abzuweisen und im Übrigen auch das Erheben einer Spruchgebühr für den Departementsentscheid zu bestätigen.
3.
Für das appellationsgerichtliche Verfahren gilt der im angefochtenen Entscheid angeführte § 30 Abs. 1 VRPG/BS, dessen willkürliche Anwendung gerügt wird und der wie folgt lautet: In der Verwaltungsrechtspflege sind dem Rekurrenten oder einem Beigeladenen im Falle des Unterliegens in der Regel die Verfahrenskosten aufzuerlegen. Die unterliegende Partei, Vorinstanz oder ursprünglich verfügende Behörde, sofern sie sich am Verfahren beteiligt hat, kann ferner zu einer Parteientschädigung verurteilt werden. Zu Gunsten der Vorinstanz und der ursprünglich verfügenden Behörde werden keine Parteientschädigungen zugesprochen.
Im Zusammenhang mit dem departementalen Verfahren wird eine willkürliche Anwendung von § 6 und § 7 Abs. 1 des baselstädtischen Gesetzes über die Verwaltungsgebühren gerügt. § 6 lautet wie folgt: Im Verwaltungsrekursverfahren können dem Beschwerdeführer oder dem Beigeladenen, der das Verfahren veranlasst hat, im Falle des vollständigen oder teilweisen Unterliegens seines Standpunktes die amtlichen Kosten... ganz oder teilweise auferlegt werden. § 7 Abs. 1 lautet wie folgt: Dem teilweise oder ganz obsiegenden Beschwerdeführer oder Beigeladenen, dem Anwaltskosten entstanden sind, kann, sofern es sich nicht um einen offensichtlichen Bagatellfall handelt, eine angemessene Parteientschädigung zugesprochen werden.
3.1. Die Beschwerdeführer machen geltend, dass es sich bei den genannten Normen zwar um kann-Formulierungen handle, jedoch in der Praxis von einem eigentlichen Anspruch auf Parteientschädigung ausgegangen werde und die Kosten jeweils der unterliegenden Partei aufzuerlegen seien. Inwiefern dies als Grundsatz der Fall ist, kann offen gelassen werden, weil das Appellationsgericht bewusst keinen Grundsatz zur Anwendung gebracht, sonder spezifisch begründet hat, warum im vorliegenden Einzelfall keine Parteientschädigung zugesprochen werden kann und die departementale Spruchgebühr zu bestätigen ist. Dies sehen letztlich auch die Beschwerdeführer so, versuchen sie doch, sowohl die Sachverhaltsfeststellung im angefochtenen Entscheid als auch die rechtlichen Schlussfolgerungen mit Willkürrügen zu Fall zu bringen.
Aus den gleichen Gründen muss auch nicht abschliessend beantwortet werden, wie das kantonale Verfahren einzuordnen ist. Jedenfalls handelt es sich um ein registerrechtliches Verfahren, welches beim Zivilstandsregister Basel-Stadt mit dem Begehren auf Anerkennung und Eintragung der malischen Adoption anhängig gemacht worden ist. Ersichtlich ist sodann, dass auch das Rechtsmittelverfahren als Einparteienverfahren durchgeführt worden ist. Im angefochtenen Entscheid sind die heutigen Beschwerdeführer (Mutter und Kind) mit "Rekurrentin" und "Rekurrent" bezeichnet, während auf der Gegenseite zwar das Zivilstandsamt Basel-Stadt aufgeführt ist, allerdings nicht als "Rekursgegner", sondern ohne spezielle Bezeichnung und damit offensichtlich in seiner Funktion als erste Entscheidinstanz. Noch deutlicher kommt dies zum Ausdruck im Entscheid des Departementes, wo im Rubrum nicht das Zivilstandsamt, sondern bloss dessen Entscheid als Anfechtungsobjekt aufgeführt ist. Bei registerrechtlichen Verfahren geht es wie bei der freiwilligen Gerichtsbarkeit darum, dass ausschliesslich die gesuchstellende Partei vom anbegehrten Entscheid profitiert (vgl. zur Publ. vorgesehenes Urteil 5A_619/2015 vom 21. Dezember 2015 E. 3.3 m.w.H.). Wie die Kostenfrage im Grundsatz zu handhaben ist, wenn die gesuchstellende Partei erst im Rahmen des Rechtsmittelverfahrens (teilweise) durchdringt, kann wie gesagt offen gelassen werden, weil das Appellationsgericht von einer speziellen Situation ausgegangen ist und dies spezifisch begründet hat. Entsprechend ist nachfolgend zu prüfen, ob die Beschwerdeführer diese mit hinreichend substanziierten Willkürrügen anzufechten vermögen.
3.2. Kernpunkt der appellationsgerichtlichen Argumentation ist, dass im Zeitpunkt des Erlasses des departementalen Entscheides - die Beschwerdeführerin hielt sich zu jenem Zeitpunkt mit dem Kind mangels erfolgter Einreisegenehmigung für die Schweiz noch in Mali auf - die Voraussetzungen für die Anerkennung der Adoption in der Schweiz nicht gegeben waren, sondern diese vielmehr erst während des appellationsgerichtlichen Verfahrens eingetreten sind, als die Mutter mit dem Kind in die Schweiz einreisen und dieses hier betreuen konnte, so dass das Appellationsgericht in seine Erwägungen zwangsläufig das weitere Schicksal des Kindes miteinzubeziehen hatte, indem sich insbesondere die Frage stellte, ob das Kind bei unterbleibender Anerkennung der Adoption nach Mali zurückkehren und bei seinem dortigen Adoptivvater leben müsste.
Die Beschwerdeführer machen zunächst geltend, massgeblich für den Sachentscheid seien die tatsächlichen Verhältnisse im Zeitpunkt des appellationsgerichtlichen Entscheides gewesen; das Appellationsgericht halte dies selbst ausdrücklich fest. Die Begründung sei widersprüchlich, wenn es im Zusammenhang mit der beantragten Parteientschädigung dann plötzlich auf einen früheren Zeitpunkt, nämlich auf denjenigen des vorinstanzlichen Entscheides abstellen wolle.
Mit diesen Vorbringen lässt sich keine willkürliche Anwendung der fraglichen kantonalen Normen begründen. Wenn <ref-law> sowie § 6 und 7 des Verwaltungsgebührengesetzes die Möglichkeit eröffnen, der im Rechtsmittelverfahren durchdringenden Partei eine Entschädigung zuzusprechen, liegt dem offensichtlich der Gedanke zugrunde, dass ein Rechtsmittelverfahren in der Regel nötig wird, weil eine Vorinstanz materiell falsch entschieden hat, und nicht der Gesuchsteller die finanziellen Konsequenzen des materiell unrichtigen vorinstanzlichen Entscheides tragen soll. Dieser Normzweck greift dort nicht, wo der vorinstanzliche Entscheid im Zeitpunkt seiner Fällung materiell richtig war (was die Beschwerdeführer mit weiteren Rügen ebenfalls anzufechten versuchen, dazu unten).
Durfte das Appellationsgericht willkürfrei von der Richtigkeit des departementalen Entscheides ausgehen, was noch zu prüfen sein wird, ist mithin keine willkürliche Anwendung von § 30 VRPG/BS und im Übrigen von § 6 und 7 des Verwaltungsgebührengesetzes ersichtlich, wenn es von dem durch die kann-Bestimmungen eröffneten Ermessen dahingehend Gebrauch gemacht hat, dass es keine Parteientschädigung zugesprochen und das Erheben einer Spruchgebühr für den Departementsentscheid geschützt hat: Die Beschwerdeführer machen selbst nicht geltend, dass sie für einen erstinstanzlich gutheissenden, d.h. auf Eintragung lautenden Registerentscheid keine Spruchgebühr bezahlen müssten und eine Parteientschädigung zugute hätten. Entsprechend kann für einen Rechtsmittelentscheid jedenfalls unter Willkürgesichtspunkten nichts anderes gelten, wenn sich die Anerkennungs- und Eintragungsvoraussetzungen erst im Laufe dieses Verfahrens verwirklicht haben. Willkür lässt sich in diesem Zusammenhang auch nicht dartun mit der Ausführung, weshalb die Einreise nicht früher möglich gewesen sei und man unter grossen Gefahren in Mali habe ausharren müssen. Weder war das Departement für die Frage der Einreise zuständig noch waren die Einreisemodalitäten für die (noch zu behandelnde) Frage der sachlichen Richtigkeit des departementalen Entscheides entscheidend.
3.3. Die Unrichtigkeit des departementalen Entscheides in dessen Erlasszeitpunkt versuchen die Beschwerdeführer ferner mit einer Willkürrüge dahingehend zu begründen, dass die Auffassung des Departementes, <ref-law> setzte für die Anerkennung der gemeinschaftlichen Adoption die Anerkennungsfähigkeit der malischen Ehe voraus, gemäss den appellationsgerichtlichen Erwägungen falsch sei. Sodann sei widersprüchlich, wenn das Appellationsgericht einerseits von der fehlenden Anerkennbarkeit der Adoption im Zeitpunkt des departementalen Entscheides ausgehe, andererseits für die Anerkennbarkeit im Zeitpunkt des appellationsgerichtlichen Entscheides darauf abstelle, dass die Mutter bereits seit September 2013 [recte gemäss Appellationsgericht: April 2014] eine gelebte Beziehung mit ihrem Sohn gehabt habe. Bereits im Zeitpunkt des departementalen Entscheides im April 2015 wäre die Beziehung zum Kind genügend eng und lange gewesen, um die Anerkennungsvoraussetzungen zu bejahen; im Laufe des appellationsgerichtlichen Verfahrens habe sich nichts Entscheidendes mehr geändert.
Zutreffend ist, dass das Departement und das Appellationsgericht die Frage, ob die Anerkennbarkeit der malischen Ehe eine (vorfrageweise zu prüfende) Voraussetzung für die Anerkennbarkeit der malischen gemeinschaftlichen Adoption sei, unterschiedlich beantwortet haben. Dies allein vermag aber keine Willkür in Bezug auf die Ansicht des Appellationsgerichtes zu begründen, dass das Departement im damaligen Zeitpunkt richtig entschieden habe, und insbesondere ist die Frage vorliegend nicht materiell zu beantworten. Auch das Appellationsgericht ging nämlich von einer zweckwidrigen Verwendung des in Mali zulässigen Institutes der polygamen Ehe aus, indem die Mutter nie ein Eheleben, sondern einzig die Erlangung der malischen Staatsbürgerschaft angestrebt habe, um die Voraussetzungen für eine auf der Heimatangehörigkeit beruhenden Anerkennung der nach malischem Recht erfolgten Adoption zu schaffen. Mit dieser Erwägung hat das Appellationsgericht nicht anders als das Departement der Mutter ein rechtsmissbräuchliches Vorgehen vorgeworfen und in diesem Zusammenhang die Anerkennbarkeit des malischen Adoptionsentscheides bzw. des dadurch begründeten Eltern-Kind-Verhältnisses in Frage gestellt.
Wie es darum bestellt ist, muss vorliegend nicht abschliessend beantwortet werden: Das Bundesamt für Justiz hat keine Beschwerde erhoben, so dass vorliegend nicht die Anerkennungs-, sondern einzig die Kostenfrage strittig ist, welche das Appellationsgericht mit den erst während des appellationsgerichtlichen Verfahrens eingetretenen Anerkennungsvoraussetzungen und somit einer veränderten Ausgangslage begründet hat. Auf diese Begründung gehen die Beschwerdeführer nicht näher ein bzw. sie lassen es bei der nicht näher ausgeführten Behauptung bewenden, während des appellationsgerichtlichen Verfahrens seien keine Veränderungen mehr eingetreten. Die Beschwerdeführer übergehen - und insofern bleibt ihre Willkürrüge letztlich unsubstanziiert - in diesem Zusammenhang insbesondere, dass sie im Zeitpunkt des departementalen Entscheides ihr Leben gemeinsam im Mali geführt haben, und zwar als malische Staatsangehörige im gleichen Land wie nach malischem Recht der Ehegatte der Mutter und Vater des Kindes. Für diese spezifische Konstellation durfte das Appellationsgericht die Voraussetzungen für eine Anerkennung und Eintragung der Adoption in der Schweiz vor dem Hintergrund des missbräuchlichen Vorgehens der Mutter und der Tatsache, dass bis zu diesem Zeitpunkt nie eine für die Anerkennung einer ausländischen Adoption zentrale Prüfung des Kindeswohles stattgefunden hatte (vgl. Urteil 5A.10/1992 vom 20. Januar 1993 E. 5b betreffend fehlende Abklärung der massgeblichen Verhältnisse durch die ausländische Adoptionsbehörde in einer ähnlichen Konstellation wie der vorliegenden; für weitere Hinweise betreffend Adoptionsmotive sowie Prüfungspflichten der ausländischen Behörde und Anerkennung des Adoptionsentscheides in der Schweiz vgl. <ref-ruling> E. 6.6 S. 344 f.), willkürfrei verneinen. Der Kern der appellationsgerichtlichen Erwägungen ist, dass demgegenüber im heutigen Zeitpunkt angesichts des gemeinsamen Zusammenlebens von Mutter und Kind in der Schweiz diesem eine Rückkehr nach Mali nicht zuzumuten wäre, zumal es noch nie in der dortigen polygamen Familie des Adoptivvaters gelebt habe. Damit ist das Appellationsgericht gleichzeitig davon ausgegangen, dass die Mutter aufgrund ihrer wirtschaftlichen Verwurzelung in der Schweiz als selbständige Anwältin nicht dauerhaft nach Mali ziehen und dort mit dem Kind leben könnte. Ob vor diesem Hintergrund das Appellationsgericht die Adoption anerkennen durfte, ist wie gesagt nicht Gegenstand des vorliegenden Verfahrens. Frage ist einzig, ob damit die Ausgangslage im Zeitpunkt des appellationsgerichtlichen Entscheides eine andere war als im Zeitpunkt des departementalen Entscheides und sich deshalb die getroffene Kostenregelung als willkürfrei erweist.
3.4. Keine Unrichtigkeit des departementalen Entscheides ergibt sich ferner aus dem Vorbringen, das Appellationsgericht habe willkürlich auf eine Umgehungsabsicht und damit auf eine fehlende Anerkennungsmöglichkeit geschlossen. Das Appellationsgericht hat im Zusammenhang mit dem Vorgehen der Mutter keineswegs blosse Annahmen getroffen, sondern sich vielmehr auf verurkundete Aussagen und Dokumente gestützt, welche es im Kontext des zeitlichen Ablaufes gewürdigt hat. Vor diesem Hintergrund lässt sich mit gegenteiligen allgemeinen Behauptungen (die Erkundigung beim Zivilstandsamt Basel im Jahr 2012 sei nur allgemein gewesen und die Heirat in Mali habe damit nichts zu tun; mit der Ehe sei eine verbindliche Gemeinschaft bezweckt gewesen; es sei bei all diesen Handlungen nur um das Kindeswohl gegangen, zumal das Kind Trennungsängste entwickelt habe; es sei keine Rechtsumgehung ersichtlich, da eine ausländische Adoption zulässig und die Anerkennung einer solchen Adoption in der Schweiz auch möglich und gewünscht sei; bei Anwendung des HAÜ wäre ohne Weiteres eine Adoption möglich gewesen, weil aufgrund der vorbestehenden vertrauensvollen Beziehung ein Ausnahmegrund nach Art. 5 Abs. 4 AdoV bestanden hätte; die erhobenen Vorwürfe seien nicht rechtlicher, sondern ausschliesslich moralischer Natur; u.ä.m.) keine willkürliche Sachverhaltsfeststellung dartun (vgl. E. 1).
3.5. Hält die Kernerwägung des Appellationsgerichtes, die Ausgangslage sei im Zeitpunkt des departementalen Entscheides eine andere und dieser deshalb richtig gewesen, vor dem Willkürverbot stand, sind die weiteren appellationsgerichtlichen Erwägungen und die diesbezüglichen Willkürrügen gegenstandslos (Verstoss gegen Mitwirkungspflichten; zivilrechtlich vorwerfbares Verhalten). Darauf braucht folglich nicht weiter eingegangen zu werden.
3.6. Das Appellationsgericht hat aus seiner Feststellung, dass im Zeitpunkt des departementalen Entscheides andere Sachumstände geherrscht hätten, und der Erwägung, dass damals zu Recht nicht von der Anerkennbarkeit der Adoption ausgegangen worden sei, die Folgerung gezogen, dass die teilweise Gutheissung der Begehren um Anerkennung und Eintragung der Adoption kein Obsiegen bedeuten und den Beschwerdeführern deshalb keine Parteientschädigung zustehen könne und überdies an der departementalen Spruchgebühr festzuhalten sei. Die Beschwerdeführer kritisieren diese Auffassung nur durch Bestreitung der Prämisse (dazu E. 3.1 bis 3.4); hingegen zeigen sie nicht mit Willkürrügen auf, dass auf der Grundlage der willkürfrei festgestellten Prämisse die Kostenerwägung willkürlich wäre. Folglich ist darauf mangels einer substanziierten Rüge nicht näher einzugehen.
4.
Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit auf sie eingetreten werden kann. Die Gerichtskosten sind bei diesem Verfahrensausgang den Beschwerdeführern aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 7. Juni 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Möckli