F#で1からnまでの合計を求める関数を様々な形で書いてみる

1からnまでの合計を求めるための関数を色々なパターンでつくってみました。

# 関数型プログラミングらしくない書き方 その1

破壊的代入（再代入）が可能なミュータブル（mutable）な変数を使った方法です。手続き型プログラミングでは一般的なアプローチになります。

F#においてミュータブルな変数を利用する場合には、宣言のタイミングで`mutable`をキーワードをつけます。破壊的な代入を行なうときには`<-`を使います（宣言時に初期値を与えるときは`=`を使います）。

関数型プログラミングでは、できるだけミュータブルな変数を利用せずにコードを書いていくことが求められます。

``` FSharp:code.fs
  let sum0ToN n = 
    let mutable sum = 0
    for i = 0 to n do
      sum <- sum + i
    sum // 関数定義の最後で評価される値が戻値
  printfn "%d" <| sum0ToN 100 
```

最終行の`<|`は後方パイプ演算子といいます。これを利用しない場合は、括弧を明示して`printfn "%d" (sum0ToN 100)` のように記述する必要があります。括弧がないとコンパイラは、`100`を`printfn`の引数として解釈してしまいます（ここでは、`100`は`sum0toN`の引数となってほしい）。

# 関数型らしくない書き方 その2

`ref`キーワードを付けて参照型とすることでイミュータブル的にする方法を使っています。こちらの方法も関数型プログラミングでは推奨されません。

参照型の値の取得には`!`を、参照先の値の変更には`:=`を使います。

``` FSharp:code.fs
  let sum0toN n = 
    let sum = ref 0
    for i = 0 to n do
      sum := !sum + i
    !sum
  printfn "%d" <| sum0toN  100 
```

# 再帰関数による方法

関数型プログラミングにおいて定番の方法になります。再帰関数の定義には'rec'キーワードを付けます。F#において比較には`==`ではなく`=`を使うので注意します。ちなみに、`!=`ではなく`<>`を使用します。

次のコードでは、`sum0toN`関数内で、再帰関数`sub`を定義し、定義後に引数`n`を与えて`sub n`のように呼び出しています（評価しています）。最後にされたものが戻値になるので、関数`sum0toN`の戻値は、`sub n`を評価したものとなります。

``` FSharp:code.fs
  let sum0toN n = 
    let rec sub i =
      if i = 0 then 0 else i + sub (i-1)
    sub n
  printfn "%d" <| sum0toN 100 
```

上記コードで、`sub (i-1)`の括弧を外して`sub i-1`とすると、`(sub i)-1`のように解釈され、`sub i`の無限コールによりスタックオーバーフローが発生します。簡素に記述しようとして括弧を省略すると、この手の罠にはまるので注意です。

先のコードは冗長な部分があり、実際には次のようにも記述できます。

``` FSharp:code.fs
  let rec sum0toN i = // 再帰関数の場合は 要recキーワード
    if i = 0 then 0 else i + sum0toN (i-1)
  printfn "%d" <| sum0toN 100 
```

match式（switch構文のようなもの）を使って、次のようにすっきりと記述できます。アンダーバー`_`は、どんな値にもマッチするパターン（ワイルドカードパターン）を表します。

``` FSharp:code.fs
  let rec sum0toN n =
    match n with 
      | 0 -> 0 // nが0ならば0が戻値
      | _ as i -> i + sum0toN(i-1)
  printfn "%d" <| sum0toN 100
```

さらに、function式を使って、よりシンプルに記述することができます。

関数の定義式から仮引数の`n`が消えている点に注意してください。

``` FSharp:code.fs
  let rec sum0toN = 
    function
    | 0 -> 0
    | _ as i -> i + sum0toN (i-1)
  printfn "%d" <| sum0toN 100
```

# 末尾再帰関数による方法

再帰関数による方法では、引数`n`に次のような大きな値を与えるとスタックがオーバーフローします。

``` FSharp:code.fs
  let rec sum0toN i = 
    if i = 0L then 0L else i + sum0toN (i-1L)
  printfn "%d" <| sum0toN 100000000L
```

これは、末尾再帰関数という方法で回避できるようです。次のコードでは、計算過程の合計値`tmpSum`も引数として再帰関数に与えています。

``` FSharp:code.fs
  let sum0toN n =
    let rec sub tmpSum i =
      match i with 
        | 0L -> tmpSum
        | _ as i -> sub (tmpSum+i) (i-1L)
    sub 0L n
  printfn "%d" <| sum0toN 100000000L
```

# リストを使う方法

簡潔に記述できます。

``` FSharp:code.fs
  let sum0toN n = List.sum [1 .. n]
  printfn "%d" <| sum0toN 100 
```

前方パイプライン演算子`|>`というものを使って、次のように記述することもできます。

``` FSharp:code.fs
  let sum0toN n = [1 .. n] |> List.sum 
  printfn "%d" <| sum0toN 100
```

ただし、リストを使うとメモリに1からNまでの領域を確保するため、大きな数値を与えるとメモリ消費が大きくなります。

``` FSharp:code.fs
  let sum0toN n:int64 = List.sum [1L .. n]
  printfn "%d" <| sum0toN 100000000L
```

![2019-02-03_11h33_33.png](https://qiita-image-store.s3.amazonaws.com/0/152805/010dd949-95b1-6e63-ec76-151cb73f3304.png)

# シーケンスを使う方法

リストとは違って逐次的に値を生成するので、大きな値をあたえてもメモリを圧迫しません。

``` FSharp:code.fs
  let sum0toN n = Seq.sum {1 .. n}
  printfn "%d" <| sum0toN 100
```

パイプライン演算子を使って`let sum0toN n = {1 .. n} |> Seq.sum`とも記述できます。

使用されるメモリはリストによる場合と比較して桁違いに少ないです。

``` FSharp:code.fs
  let sum0toN n:int64 = Seq.sum {1L .. n}
  printfn "%d" <| sum0toN 100000000L
```

# リストとパターンマッチを使う方法

``` FSharp:code.fs
  let sum0toN n = 
    let rec sub l = 
      match l with 
      | head::tail -> head + sub tail
      | [] -> 0
    sub [1..n]
  printfn "%d" <| sum0toN 100
```


# 番外編

等差数列の和の公式を使ったもの

``` FSharp:code.fs
  let sum0toN n = (n+1)*n/2
  printfn "%d" <| sum0toN 100
```

# 参考資料
- [手軽なスクリプト言語としてのF# その２１「再帰とループ」@かずきのBlog](https://blog.okazuki.jp/entry/20110201/1296531420)
- 実践F# 関数型プログラミング入門 (技術評論社)