Kann der gesamte Code als eine Reihe von Map / Filter / Reduce-Operationen dargestellt werden?

16

Ich habe kürzlich große Codestücke überarbeitet und durch Linq-Abfragen ersetzt.

Entfernen der sprachlichen Verzerrung - Linq besteht im Wesentlichen aus einer Reihe von Map / Filter- und Reduce-Operationen, die mit einer Datensequenz ausgeführt werden.

Das brachte mich zum Nachdenken, wie weit ich das theoretisch bringen könnte. Wäre es mir möglich, die gesamte Codebasis in eine Reihe (oder sogar eine einzige) von Map / Filter- und Reduce-Operationen umzuschreiben?

Leider werde ich dafür bezahlt, nützliche Dinge zu tun, so dass ich nicht viel weiter experimentieren konnte, aber ich kann mir keine Codestruktur vorstellen, die nicht als solche neu strukturiert werden könnte. Nebeneffekt-Code kann über Monaden behandelt werden. Auch die Ausgabe besteht im Wesentlichen darin, Speicheradressen auf Bildschirmadressen abzubilden.

Gibt es etwas, das (theoretisch) nicht als Linq-Abfrage umgeschrieben werden kann?

computer-science Mongus Pong
quelle
Für Bäume sehen hier: stackoverflow.com/questions/250377/...
blueberryfields
Ich habe immer gedacht, dass "Reduzieren" ausreicht, um die Turing-Fertigstellung zu gewährleisten (Map und Filter können als Reduktionsoperationen implementiert werden, oder?) - zumindest das funktionale Sprachäquivalent von Reduzieren. Ich weiß nicht genug über Linq, um sicherzugehen, wie genau die Implementierung dort der funktionalen folgt.
blueberryfields
1
Ich weiß es nicht, aber eine grobe Faustregel ist, dass alles, was irgendjemand in Betracht ziehen würde, seinen gesamten Code einzuschreiben, sich als vollständig herausstellen wird. Aber die Konsequenz daraus ist, dass es nicht sehr aufregend ist, Turing vollständig zu sein.
bA
1
Ich stimme mit PSR überein. Ich denke, eine gültige Antwort auf diese Frage muss die Vollständigkeit von Turing betreffen. Ein Proof könnte versuchen, eine Turing-Maschine nur mit diesen Operationen zu implementieren.
Rob
Fauler Gedanke: Auch wenn wir Unsinn mögen my_list.map(_ignored => a copy of my_list), scheint der Platzbedarf eines solchen Programms durch ein Polynom begrenzt zu sein (abhängig von der Programmlänge). Dann könnte eine solche Sprache sicherlich keine Probleme berechnen, die nicht in PSPACE sind. Da jedoch viele Probleme in PSPACE als unlösbar angesehen werden, ganz zu schweigen von größeren Klassen, ist dies möglicherweise keine sehr schwerwiegende Einschränkung.

Antworten:

1

Es heißt funktionale Programmierung und wird von vielen als grundlegendes Konzept angesehen. Hier ist ein gutes Intro über Joel On Software . Die technischere Antwort lautet "Nein". Derzeit ist keine Methode bekannt, mit der Sie (genau definierte) Fragen an Ihren Computer stellen können, die nicht über die SKI-Berechnung beantwortet werden können.

JP Mcgrady
quelle
1
Es gibt weit mehr zu funktionaler Programmierung als die Funktionen map, filterund reduce(dies geht dreimal , wenn wir Turing Vollständigkeit und nutzen praktische FP Sprachen ignorieren). Tatsächlich sind sie eher allgemein gehalten und daher allgemein nützlich, aber tatsächlich sind sie sehr einfache Anwendungen der funktionalen Programmierung. Bare Minimum Lambda Calculus kann diese Funktionen unter vielen anderen definieren, nicht umgekehrt.
"Hier ist ein gutes Intro über Joel On Software" - das es schafft, Fortran mit Basic zu verwechseln, sodass ich anderen Fakten nicht viel zutrauen würde.
quant_dev