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

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

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

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

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

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

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

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

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を評価したものとなります。

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の無限コールによりスタックオーバーフローが発生します。簡素に記述しようとして括弧を省略すると、この手の罠にはまるので注意です。

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

code.fs

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

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

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が消えている点に注意してください。

code.fs

  let rec sum0toN = 
    function
    | 0 -> 0
    | _ as i -> i + sum0toN (i-1)
  printfn "%d" <| sum0toN 100

末尾再帰関数による方法

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

code.fs

  let rec sum0toN i = 
    if i = 0L then 0L else i + sum0toN (i-1L)
  printfn "%d" <| sum0toN 100000000L

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

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

リストを使う方法

簡潔に記述できます。

code.fs

  let sum0toN n = List.sum [1 .. n]
  printfn "%d" <| sum0toN 100 

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

code.fs

  let sum0toN n = [1 .. n] |> List.sum 
  printfn "%d" <| sum0toN 100

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

code.fs

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

シーケンスを使う方法

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

code.fs

  let sum0toN n = Seq.sum {1 .. n}
  printfn "%d" <| sum0toN 100

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

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

code.fs

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

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

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

番外編

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

code.fs

  let sum0toN n = (n+1)*n/2
  printfn "%d" <| sum0toN 100

参考資料

• 手軽なスクリプト言語としてのF# その２１「再帰とループ」@かずきのBlog
• 実践F# 関数型プログラミング入門 (技術評論社)