NG Programmiersprache?

[Mr. N]

volkard schrieb:

Manchmal (besonders wenn man Hochschulprofessor ist) baut man auch mal was rekursiv.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Gute Abstraktion. Jetzt steht das Zeug auch recht hübsch und übersichtlich da.

Aber dann kommt einer, dem ist das doch nicht abstrakt genug, denn man kann ja noch fast den erzeugten Code erahnen, und er baut

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Böse Abstraktion.

Das zweite ist natürlich performanter, wenn man die ganze Liste will.

Wobei ich - bitte nicht glauben, dass ich den Code hübsch fände - da noch eins draufsetzen kann:

fix $ ([0,1] ++) . (zipWith (+) <*> tail)

[SideWinder]

Zeus schrieb:

@SideWinder
Ein kleiner Überblick über Nano:
[...]

Vielen Dank, hast du die Zusammenfassung extra für mich gemacht oder erst gestern ins Repository hochgeladen?

Bin von einigen Dingen begeistert, aber bspw. die Begrenzung auf Rekursion als einzig iteratives Element will ich nicht wahrhaben

MfG SideWinder

[nachfrager]

Mr. N schrieb:

volkard schrieb:

Manchmal (besonders wenn man Hochschulprofessor ist) baut man auch mal was rekursiv.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Gute Abstraktion. Jetzt steht das Zeug auch recht hübsch und übersichtlich da.

Aber dann kommt einer, dem ist das doch nicht abstrakt genug, denn man kann ja noch fast den erzeugten Code erahnen, und er baut

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Böse Abstraktion.

Das zweite ist natürlich performanter, wenn man die ganze Liste will.

Warum soll das performanter sein?

[Zeus]

SideWinder schrieb:

Vielen Dank, hast du die Zusammenfassung extra für mich gemacht oder erst gestern ins Repository hochgeladen?

Ich hab sie auf Anfrage für dich und alle Lauscher gemacht

SideWinder schrieb:

Bin von einigen Dingen begeistert, aber bspw. die Begrenzung auf Rekursion als einzig iteratives Element will ich nicht wahrhaben
MfG SideWinder

Yo mal sehen

[Mr. N]

nachfrager schrieb:

Warum soll das performanter sein?

Weil die Fibonacci-Zahlen nicht immer wieder berechnet werden. Wenn du fib 4 rekursiv berechnest, berechnest du fib 1, fib 2, fib 3 und fib 4 immer auch (bei der naiven Rekursion sogar teilweise mehrfach). Bei der rekursiven Liste von volkard werden die Zahlen nur einmal berechnet und wiederverwendet.

[Zeus]

Wenn ich blos den "Rekursionsschritt"? bei der Version erkennen würde

[volkard]

Also baue ich mir zuerst Schlösser mit 5 Stockwerken der Abstraktion und muß dann doch selber die Abstraktion bis runter auf sagen wir mal C-Niveau auflösen und mir vorstellen, wie er es innendrin macht, damit ich nicht in eine Falle tapse, und eine sehr langsame Funktion baue. Uih, das würde mich aber ein bißchen nerven.

[hehe]

Mr. N schrieb:

nachfrager schrieb:

Warum soll das performanter sein?

Weil die Fibonacci-Zahlen nicht immer wieder berechnet werden. Wenn du fib 4 rekursiv berechnest, berechnest du fib 1, fib 2, fib 3 und fib 4 immer auch (bei der naiven Rekursion sogar teilweise mehrfach). Bei der rekursiven Liste von volkard werden die Zahlen nur einmal berechnet und wiederverwendet.

Da nehme ich dann doch lieber eine for-schleife.

[Mr. N]

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

[Zeus]

Mr. N schrieb:

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Uninstressant, die For-Schleife für Fibonacci steht bei Stackoverflow. Hab ich gemerkt nachdem ich meine implementiert habe *gg*.

[Mr. N]

Zeus schrieb:

Mr. N schrieb:

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Uninstressant, die For-Schleife für Fibonacci steht bei Stackoverflow. Hab ich gemerkt nachdem ich meine implementiert habe *gg*.

Dann könnte man vergleichen, welche Methode komplizierter ist.

[Zeus]

http://stackoverflow.com/questions/1518726/recursive-fibonacci

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

[Mr. N]

Erstmal was ganz anderes: Überleg dir doch, nano-lang auf github zu schieben.

Zeus schrieb:

http://stackoverflow.com/questions/1518726/recursive-fibonacci

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

OK, dann vergleichen wir es mal mit der berühmten idiomatischen Haskell-Version:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Mal davon abgesehen, dass diese Version eine _Liste_ _aller_ Fibonacci-Zahlen erzeugt, also [1,1,2,3,5,8,13,21...]...

Die iterative Version von dir besitzt durchaus eine beachtliche Komplexität. Man muss schon nachdenken, was das macht. Genauso wie bei der Version mit zipWith. Natürlich ist für dich die iterative Version einfacher, weil du es seit Jahren übst, auf iterative Algorithmen zu starren, und sie zu entziffern. Bei den funktionalen Pendants fehlt dir da einfach die Übung.

Aber das ist nichts angeborenes. Beide Algorithmen sind für einen sehr unerfahrenen Programmierer undurchdringlich.

Ich habe mir mal die Mühe gemacht, den iterativen Algorithmus so umzubauen, dass er auch eine unendliche Liste von Fibonacci-Zahlen (modulo 2⁶⁴) erzeugt:

boost::uint64_t a = 1, b = 1;
cout << "1 1 ";
for (int i = 3; ; i++) {
    boost::uint64_t c = a + b;
    a = b;
    b = c;
    cout << b << ' ';
}

[Antoras]

Also ich finde, dass rekursive Algos oft deutlich einfacher zu lesen sind als die iterativen. Auch weil sie viel kürzer sind. Weiterer Vorteil der rekursiven Variante: man hat unveränderliche Objekte.

[Zeus]

@Mr.N
Nur weil ich für hehe antworte, heisst es nicht, dass ich es leichter finde. Ich find die Version, die Volkard gepostet habe, am leichtesten

[volkard]

Naja, die hier gewählte Sprache ist auch irgendwie nicht passend zum Problem.

Vielleicht würde Paarzuweisung was retten.

int fib(int n)
{
    alt,neu = 1,1;
    for i=3 to n
      alt,neu = neu,alt+neu
    return neu
}

Oder yield? Nee, eher nicht.

Vielleicht mit swap.

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++)
       swap(a+=b,b);
    return b;
}

Nein, eher auch nicht.

[volkard]

Mr. N schrieb:

Ich habe mir mal die Mühe gemacht, den iterativen Algorithmus so umzubauen, dass er auch eine unendliche Liste von Fibonacci-Zahlen (modulo 2⁶⁴) erzeugt:

boost::uint64_t a = 1, b = 1;
cout << "1 1 ";
for (int i = 3; ; i++) {
    boost::uint64_t c = a + b;
    a = b;
    b = c;
    cout << b << ' ';
}

Ja.
Oder

10 a=1:b=1
20 a=a+b:print a
30 b=b+a:print b
40 goto 20

[back to basic _leak_]

volkard schrieb:

10 a=1:b=1
20 a=a+b:print a
30 b=b+a:print b
40 goto 20

back to basic

[Nexus]

Mr. N schrieb:

Die iterative Version von dir besitzt durchaus eine beachtliche Komplexität. Man muss schon nachdenken, was das macht. Genauso wie bei der Version mit zipWith. Natürlich ist für dich die iterative Version einfacher, weil du es seit Jahren übst, auf iterative Algorithmen zu starren, und sie zu entziffern. Bei den funktionalen Pendants fehlt dir da einfach die Übung.

Dass man mit funktionalen Programmiersprachen gewisse Anweisungen sehr elegant und kompakt ausdrücken kann, bestreite ich gar nicht. Das ist ja auch etwas, was mir an Haskell so gefällt. Allerdings erfordert dieser Weg einige Abstraktion, zum Beispiel viel mehr als eine Schleife. Oder zumindest eine andere Art von Abstraktion, von der ich behaupte, dass sie am Anfang weniger naheliegend und intuitiv ist.

Nimm zum Beispiel Pseudocode: Er dient dazu, unabhängig von der Programmiersprache Abläufe und Algorithmen zu beschreiben. Und er besitzt oft die Form eines iterativen Rezepts wie bei der Schleife hier, je nach Problem auch einer einfachen Rekursionsvorschrift. Aber sowas Ähnliches wie zipWith findet man nirgends, weil High-Order-Functions eher schwierig zu verstehen sind. Hingegen ist ein

f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1

auch für Leute verständlich, die gar nicht programmieren können.

Ironisch ist doch, dass sowohl C++ als auch Haskell die Fibonacci-Berechnung so formulieren könnten. Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

[volkard]

Nexus schrieb:

Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

Man staunt, was sich die Haskell-Leute so basteln, um auf O(n) Zeit zu kommen.

fib 0 = 0
fib 1 = 1
fib n | even n         = f1 * (f1 + 2 * f2)
      | n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2
      | otherwise      = (2 * f1 + f2) * (2 * f1 - f2) - 2
   where k = n `div` 2
         f1 = fib k
         f2 = fib (k-1)

oder

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs

oder

fibs = fix (scanl (+) 0 . (1:))
fibs = fix ((0:) . scanl (+) 1)

oder

fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

oder

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

oder

import Control.Monad.State
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
  forM (xrange n) $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a 

xrange n = [0..(n-1)]

Da läuft doch was schief! Wobei ich nicht behaupten will, bei C++ liefe nicht auch was schief.