ハスケルで最初のn個の奇数を合計する

Question

私はハスケルと関数型プログラミングにはまったく新しく、ハスケルでこのような関数を書く方法を知りたかったのです。私は命令型言語に慣れていますが、今のところhaskellでの再帰処理はわかりません。奇数の和はn^2（すなわち、3つの第1の奇数1 + 3 + 5 = 9 = 3^2の和）で行うことができることを知っているが、この考え方は関数プログラミングによる再帰を学習することである。

また、これは代数ワークショップの一部として行われており、まだ多くは見ていません。私は再帰でのみそれを解決する方法が必要です。

ヒントありがとう！

Answer 1

まず、機能を説明する必要があります。

sumFirstOdds :: Int -> Int 

あなたは再帰について考えるとき、あなたは停止点が必要になるだろう。この場合、良好な停止点は、ゼロである最初のゼロの奇数の和である。あなたはこのようなあなたのベースケースを定義することができます。

sumFirstOdds 0 = 0 

それはあなたが再帰関数を書いている最初の停止点を宣言するのが習慣に取得するには良いことです。さもなければ、無限ループで簡単に終わることができます。

n > 0の場合、最初のnの奇数の合計を求めたいときに何が起こるかを定義する必要があります。

まず、n番目の奇数の値を取得する方法を見つける必要があります：(n * 2) - 1。

ここでは再帰部分について説明します。いくつかの簡単な例を見ていくことで、この問題について考えることができます。我々は最初の3つの奇数の合計を取得したい場合は、我々はこのように、式を使用します。

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

同じアルゴリズムが3の要求された数から始まる、との結果に追加する使用されています同じアルゴリズムを2に対して実行し、同じことを1に対して実行し、0について再度実行します。これは、基本ケースに当たって停止します。

Haskellのコードの中に入れて、あなたはこれを書き出すことができます：

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

計算は、現在のn値に対して実行され、その値がそのn-1値に対して使用したのと同じ関数の結果に追加されます。

は、それがこれです、最後の関数がどのように見えるかをあらためて表明するには、次の

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

注：これはうまく負の入力を処理しませんが、私は簡単のためにそのを残してきた

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..]) 

機能でそれを入れてください：

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

Answer 3

あなたはいつも乗で奇数を合計する必要がありますので、私は再帰によってことを行うには楽しいだろうと思います。 IntまたはIntegerの場合はそのようにするのは愚かなので、代わりにタイプレベルで作業する必要があります。これは実際には素朴な方法でそれらを合計すると同じくらい遅いですが、それはより楽しいです！

{-# 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 

これを使用できるようにするには、シングルトンで用語レベルにすることができます。

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

ここではこれは必要ではありませんが、通常はヘルパー関数で再帰的計算にアキュムレータを使用できます。

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]