Quicksort in Perl - doing it the functional way!
Da es gestern in der Warpzone einen netten Vortrag über Erlang gab und dabei wieder mal der Quicksort-Algorithmus als besonders klar lesbares Beispiel (unser Beispiel an der Tafel gestern hatte mehr Zeilenumbrüche, hier schwächelt die Wikipedia-Version etwas...) die Vorteile der Notation funktionaler Programmiersprachen demonstrierte, muss ich hier mal den entsprechenden Perl-Code einfügen:
Klar, das kann man unter Perl auch genauso kompliziert und undurchschaubar wie unter C oder ähnlichem schreiben. Perl lässt einem aber wie üblich die Wahl - zwar ist die Syntax nicht so durchgängig wie funktionalen Sprachen auf „mathematische Notation“ ausgelegt, aber wie man erkennt, kann man sich auch durchaus in die Richtung bewegen.
Funktionieren tut’s und an dem Beispiel kann man, wie unter Erlang oder Scala auch, den Pudels Kern, sprich: den Gedanken, der hinter Quicksort steckt, sichtbar machen, ohne sich in der Implementierung zu verlaufen.
Als netter Nebeneffekt ist das sogar alles immutable, bei jeder Rekursion wird der Array geklont. Was vermutlich definitiv nicht so effizient abläuft, wie in darauf getrimmten Sprachen...
Raichoo hat noch Quicksort in Scala - das hatte ich allerdings etwas übersichtlicher in Erinnerung. Bei der Notation liegt Erlang insgesamt ganz klar vorne. Und ich bilde mir ein, dass sogar die Perl-Variante etwas übersichtlicher als Scala ist - auch wenn ich den doofen Funktionsprototypen vorher deklarieren muss :-)
- #!/usr/bin/perl
- use warnings;
- use strict;
- sub quicksort(@);
- sub quicksort(@) {
- my ($pivot, @rest) = (@_);
- return () unless defined $pivot;
- return ( quicksort( grep { $_ < $pivot } @rest),
- $pivot,
- quicksort( grep { $_ >= $pivot } @rest) );
- }
- print join (', ', quicksort(1, 7, 5, 3, 2, 18, 33, 7, 4, 12, 1)) . "\n";
Klar, das kann man unter Perl auch genauso kompliziert und undurchschaubar wie unter C oder ähnlichem schreiben. Perl lässt einem aber wie üblich die Wahl - zwar ist die Syntax nicht so durchgängig wie funktionalen Sprachen auf „mathematische Notation“ ausgelegt, aber wie man erkennt, kann man sich auch durchaus in die Richtung bewegen.
Funktionieren tut’s und an dem Beispiel kann man, wie unter Erlang oder Scala auch, den Pudels Kern, sprich: den Gedanken, der hinter Quicksort steckt, sichtbar machen, ohne sich in der Implementierung zu verlaufen.
Als netter Nebeneffekt ist das sogar alles immutable, bei jeder Rekursion wird der Array geklont. Was vermutlich definitiv nicht so effizient abläuft, wie in darauf getrimmten Sprachen...
Raichoo hat noch Quicksort in Scala - das hatte ich allerdings etwas übersichtlicher in Erinnerung. Bei der Notation liegt Erlang insgesamt ganz klar vorne. Und ich bilde mir ein, dass sogar die Perl-Variante etwas übersichtlicher als Scala ist - auch wenn ich den doofen Funktionsprototypen vorher deklarieren muss :-)
Geschrieben von 
mitch
mitch
Mitch’s Manga Blog am : Ich lerne Lisp