Summieren der ersten n ungeraden Zahlen in Haskell

Question

Ich bin neu in Haskell -und funktionale Programmierung insgesamt- und ich wollte wissen, wie würden Sie eine solche Funktion in Haskell schreiben. Ich bin an imperative Sprachen gewöhnt, aber die Rekursion in Haskell ist für mich momentan schwer fassbar. Beachten Sie, dass ich weiß, dass die Summe der ungeraden Zahlen mit n^2 (d. H. Summe der 3 ersten ungeraden Zahlen 1 + 3 + 5 = 9 = 3^2) getan werden könnte, aber die Idee ist, Rekursion mit funktionalen Programmierung zu lernen.

Auch ich mache das als Teil eines Algebra-Workshops und wir haben noch nicht viel gesehen. Ich brauche einen Weg, um es nur mit Rekursion zu lösen.

Irgendwelche Hinweise? Vielen Dank!

Answer 1

Zunächst müssen Sie Ihre Funktion beschreiben.

sumFirstOdds :: Int -> Int 

Wenn Sie darüber nachdenken, Rekursion, Sie gehen einen Haltepunkt zu müssen. In diesem Fall ist ein guter Haltepunkt die Summe der ersten ungeraden Zahlen Null, die Null ist.

sumFirstOdds 0 = 0 

Es ist gut zu bekommen in die Gewohnheit, erklärt den Haltepunkt zuerst, wenn Sie eine rekursive Funktion gerade schreiben: Sie können Ihre Basisfall wie folgt definieren. Ansonsten kann es leicht zu Endlosschleifen kommen.

Jetzt müssen wir definieren, was passiert, wenn wir die Summe der ersten n ungeraden Zahlen finden möchten, wenn n > 0.

Sie müssen zuerst einen Weg finden, um den Wert der n-ten ungeraden Nummer zu erhalten: (n * 2) - 1.

Jetzt für den rekursiven Teil. Es kann Ihnen helfen, über das Problem nachzudenken, indem Sie ein paar einfache Beispiele durchgehen. Wenn wir die Summe der ersten drei ungeraden Zahlen erhalten wollten, würden wir diese Formel wie folgt verwenden:

((3 * 2) - 1) + ((2 * 2) - 1) + ((1 * 2) - 1) + 0 
^   ^   ^   ^
    |    |    |    | 
n == 3   n == 2   n == 1  n == 0 (base case) 

Der gleiche Algorithmus verwendet wird, um die angeforderte Anzahl von 3 beginnt und es auf das Ergebnis der Zugabe Derselbe Algorithmus läuft gegen 2, macht dann dasselbe für 1 und wieder für 0, wo wir unseren Basisfall treffen und stoppen.

setzen in Haskell Code, könnte man dies schreiben als:

sumFirstOdds n = ((n * 2) - 1) + (sumFirstOdds (n-1)) 

Die Berechnung wird gegen den aktuellen n Wert durchgeführt wird, und dieser Wert wird auf das Ergebnis der gleichen Funktion gegen diesen n-1 Wert verwendet hinzugefügt .

Um es zu wiederholen, was die endgültige Funktion aussieht, es ist dies:

sumFirstOdds :: Int -> Int 
sumFirstOdds 0 = 0 
sumFirstOdds n = ((n * 2) - 1) + (sumFirstOdds (n-1)) 

Hinweis: diese nicht behandelt negativen Eingang gut, aber ich habe die aus Gründen der Einfachheit weggelassen

Answer 2

-- the odd numbers (all of them!) 
[ 1,3.. ] 

-- the first N odd numbers: 
take n [1,3..] 

-- the sum of the first N odd numbers 
sum (take n [1,3..]) 

es in einer Funktion Put:

sumOddNumbers n = sum (take n [1,3..]) 

Answer 3

Da Sie immer die ungeraden Zahlen von quadriert summieren sollte, denke ich, es würde Spaß machen dass durch Rekursion zu tun. Da es dumm ist, es so für Int oder Integer zu tun, sollten Sie stattdessen auf der Typenebene arbeiten. Das ist eigentlich nur so langsam, wie sie die naive Art summieren, aber es macht mehr Spaß!

{-# LANGUAGE DataKinds, KindSignatures, TypeFamilies, TypeOperators, GADTs, UndecidableInstances #-} 

data Nat = Z | S Nat 

infixr 6 :+ 
type family (:+) (x :: Nat) (y :: Nat) :: Nat where 
    'Z :+ n = n 
    'S m :+ n = 'S (m :+ n) 

infixr 7 :* 
type family (:*) (x :: Nat) (y :: Nat) :: Nat where 
    'Z :* n = 'Z 
    'S m :* n = n :+ m :* n 

Jetzt, um dies nutzbar zu machen, können Sie es mit Singletons auf die Laufzeit-Ebene bringen.

data Natty :: Nat -> * where 
    Zy :: Natty 'Z 
    Sy :: Natty n -> Natty ('S n) 

plus :: Natty m -> Natty n -> Natty (m :+ n) 
plus Zy n = n 
plus (Sy m) n = Sy (plus m n) 

times :: Natty m -> Natty n -> Natty (m :* n) 
times Zy _ = Zy 
times (Sy m) n = n `plus` (m `times` n) 

square :: Natty n -> Natty (n :* n) 
square n = times n n 

Answer 4

Hier wird es nicht benötigt, aber im Allgemeinen können Sie einen Akkumulator für rekursive Berechnungen in einer Hilfsfunktion verwenden.

sumodds n = go n 0 
    where go 0 a = a 
     go k a = go (k-1) (a + 2*k-1) 

> map sumodds [0..9] 
[0,1,4,9,16,25,36,49,64,81]