Haskell Binominalkoeffizienten

[Ook!]

Hallo, die jungen Damen!

Ich habe mir die Produktformel der Binominalkoeffizienten angeschaut und wollte diese dann in Haskell implementieren.
Soweit so gut, bis auf das Problem mit der Berechnung und den Rekursionsfehler, den ich bekomme.

So schaut der Code bisher aus:

binominal :: (Int,Int) -> Int
binominal (n,k) = foldl (*) 1 [ "Formel hier" | i <- [1..k] ]

Und die Rekursive Variante:

-- Stack space overflow: current size 8388608 bytes.
-- Use `+RTS -Ksize' to increase it.

binominal :: (Int,Int) -> Int -> Int -> Int 
binominal (n,k) i r
	| i == k = r
	| otherwise = binominal (n,k) r (i+1)
	where
		r = r * (n + 1 - i) `div` i

Kann mir jemand erklären, wie ich die Formel "r = r * (n + 1 - i) `div` i" in den Platzhalter "Formel hier" eintragen kann?
Ich muss ja irgendwie r "zwischenspeichern", damit mit dem ergebnis weitergerechnet werden kann.

Außerdem würde ich gerne den Stack overflow beheben, kann mir da jemand weiterhelfen? Google wollte mir nichts passendes ausspucken.

Gruß
Felix

 

[Lesco]

Bei der Variante mit foldl kann man einfach den Term im Argument der Produktformel übernehmen:

binomial (n,k) = foldl (*) 1 [ (n+1-i) / i | i <- [1..k]]
-- oder schoener:
binomial (n,k) = foldl1 (*) [ (n+1-i) / i | i <- [1..k]] -- das zusätzliche Zeichen ist eine eins, kein L
-- oder noch schoener ;) :
binomial (n,k) = product [ (n+1-i) / i | i <- [1..k]]

Das "Zwischenspeichern" übernimmt hier foldl, da das Ergebnis der Berechnung jeweils weitergegeben wird.
Deine rekursive Definition ist irgendwie zu umständlich. Ich würde das so realisieren:

binom2 n 1 = n
binom2 n k = ((n + 1 - k) / k) * binom2 n (k-1)

Den eventuell entstehenden Stack-Overflow(bei sehr großen k) kann man umgehen, indem man die Funktion durch einen dritten Parameter tail-recursive macht(muss man aber dennoch mit -O2 kompilieren, damit die Rekursion wegoptimiert wird):

binom2' n 1 acc = n*acc
binom2' n k acc = binom2' n (k-1) (acc * ((n + 1 - k) / k))

Um das bei der Variante mit foldl zu machen, kann man foldl' nehmen, das intern ähnlich funktioniert(Bei product immer der Fall). Interessant hierbei:
http://haskell.org/haskellwiki/Stack_overflow

Edit: Fehler beseitigt, siehe nächster Beitrag.

 

[Ook!]

Sehr schön, danke Daniel!

Allerdings funktioniert deine Variante für das erste Problem auch nicht, das Ergebnis lautet bei jeder deiner varianten auch80 bei n=10 k=4, es sollte jedoch 210 sein.
Ähnlich hatte ich es auch schon... Hast du vielleichte eine weitere Idee?

 

[Lesco]

Das liegt daran, dass ich von der irrigen Annahme ausging, die Einzelterme bei der Multiplikation seien ganze Zahlen, obwohl das Unsinn ist. Statt der Ganzzahl-Division "quot" muss man also / verwenden. Ist im voherigen Beitrag nun korrigiert.

 

[Ook!]

Funktioniert immer noch nicht, da gibts nur einen fetten Error, bei dem Goggle auch nicht wirklich helfen mag:

No instance for (Fractional Int)
arising from use of `/` 
in the explession r = r * (n + 1 - i) / i

... habe es nun jedoch auch mal in Python versucht, dort gibt es auch das falsche Ergebnis.

Ich habe es mit Zettel und Stift versucht und bin nun der Meinung, dass es in etwa so aussehen muss:

for i from 1 to k:
     r = r * (n + 1 - i) / i

so wird immer mit r (dem "aktuelle Ergebnis") weitergerechnet werden, dann kommt im Fall von n=10 k=4 auch 210 als Ergebnis raus.
Außerdem scheint `div` oder `quot` auch zu passen, das / muss also nicht sein.

Wie könnte man das in Haskell implementieren? Da es ja nur Rekursion für "Schleifen" gibt

 

[Lesco]

Hier sind jetzt 3 Varianten die für mich funktionieren(Um deinen Fehler zu vermeiden, muss man entweder die Typsignatur anpassen, sodass das ganze mit Kommazahlen arbeitet, oder in der Funktion die Integer-Parameter extra umwandeln, z.B. mit realToFrac):

binomial :: (Fractional t, Enum t) => (t, t) -> t
binomial (n,k) = product [ (n+1-i) / i | i <- [1..k]]

binom2 :: (Fractional a) => a -> a -> a
binom2 n 1 = n
binom2 n k = ((n + 1 - k) / k) * binom2 n (k-1)
-- Alternative:
-- wenn man als Typ gerne Integer -> Integer -> a hätte, könnte das so aussehen(Das Typsystem nimmt sowas sehr genau und macht keine impliziten Typumwandlungen):
binom2 n 1 = realToFrac n
binom2 n k = (realToFrac (n + 1 - k) / realToFrac k) * binom2 n (k-1)

binom2' :: (Fractional a) => a -> a -> a -> a
binom2' n 1 acc = n*acc
binom2' n k acc = binom2' n (k-1) (acc * ((n + 1 - k) / k))

 

[Ook!]

Danke, Daniel...
So funktioniert es, offensichtlich muss ich mich noch mehr über die unterschiedlichen Typen informieren!

Gruß
Felix