スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門第28回(再帰(2))

今回のお題は「再帰(2)」です。
 
まずは宿題の答えから
 
宿題
 
フィボナッチ数列(隣り合う2項の和が次の項になる数列)
1,1,2,3,5,8,13,..
の第n項を求める関数fibo n を書いてください。
 
まずよく見かける解答が
 
let rec fibo1 n =
    if (n <= 2) then
        1
    else
        (fibo1 (n - 1)) + (fibo1 (n - 2))
 
ですが、これは、非常に非効率です。
例えばfibo1 20を求めるのにこの関数がはたして何回ぐらい呼び出されるか、予想してみてください。
実は13529回なのです。fibo1 から始めてfibo1 20まで、関数が呼び出される回数を書きだすと次のようになります。
1,1,3,5,9,15,25,41,67,109,177,287,465,753,1219,1973,3193,5167,8361,13529
隣りあう2項の和+1が次の項になる数列になっています。
これは考えれば当たり前の話で、例えばfibo1 5を計算するには、fibo1 4とfibo1 3を求めてこれを足すのですから、(fibo1 4 を求めるためのこの関数の呼び出し回数)+ (fibo1 3 を求めるためのこの関数の呼び出し回数)+ 1 (最初の呼び出し) が必要となるわけです。
 
よって、この形を使うときは、計算した値については、メモしておいてそれを参照するという手法がよくとられます。
疑似コードはつぎのようになります。
 
fibo 1は1、fibo 2 は1とメモしておく
 
let rec fibo n =
    if (fibo n がメモにある) then
        メモの値を返す
    else
        let result = fibo (n - 1) + fibo (n - 2)
        「fibo n はresult」 とメモする
        resultを返す
 
実際にメモをどうするかは、後日紹介したいと思います。
 
さて、次の解答例に移ります。
末尾再帰、およびカウントアップの手法で考えてみます。
答えにつながる種として、二つの連続した項と、その右側が何項目にあたるかを引数にして渡して行きたいと思います。
例えば引数が(3,5) 5なら、第4項が3,第5項が5ということを表します。
ということで、引数が(x,y) n なら、次は(y,y + x) (n + 1)として渡します。
ということでまとめてみると
 
let fibo2 n =
 
    let rec subfib (x,y) k =
        if  k = n then
            y
        else
            subfib (y,x+y) (k + 1)
 
    if n <= 1 then
        1
    else
        subfib (1,1) 2
        
変化するものが引数部分にまとめられているので、へたなforループより、分かりやすいのではないでしょうか?
 
宿題の解答が長くなってしまいましたが、ここからが、今回の内容です。
今回はリストに対する再帰関数を取り上げます。
 
数字に対しての処理では、引数を減らした(カウントダウン)ものや増やしたもの(カウントアップ)したものに、再帰的に関数を適用していました。
リストに対しては、要素をいくつか(一つの場合が多い)取り出したものに、再帰的に関数を適用していきます。終了条件としては、「リストが空になった」を使います。
それでは、よく見かける、リストの長さを調べる関数です。
リストの長さ = (一個取り出した残りのリスト)の長さ + 1
で、あることより、次のような定義になります。
 
let rec myListLength1 lst =
    match lst with
    | [] -> 0
    | hd :: tl -> 1 + myListLength1 tl
 
リストが空になるまで、再帰的に関数を適用していき、空になったときの0という返り値に対して、ひとつもとの呼び出し先に戻るたびに1を加えていってます。(「帰り」順の処理です。)
 
それでは、「行き」順の方を紹介します。「答えの種」としての、引数の名前をaccumとします。(今までは種で、seedを使ってましたが、累積するという意味の英単語accumlateの先頭部分で、accumです。「育てる」という意味合いが強いですね。)
 
let rec subMyLL accum lst =
    match lst with
    | [] -> accum
    | hd :: tl -> subMyLL (accum + 1) tl
 
subMyLL 0 lstで,lstの要素数が返ります。一回一回0をつけるのも面倒なので、次のように、関数内で定義してしまいます。
 
let myListLength2 lst =
 
    let rec subMyLL accum lst2 =
        match lst2 with
        | [] -> accum
        | hd :: tl -> subMyLL (accum + 1) tl
 
    subMyLL 0 lst
//上のlst2はlstとしても同じ
 
実行例
 
> myListLength2 [3;2;5];;
val it : int = 3
 
つぎに、List.mapを自分で実装してみたいと思います。
答えの種として最初に[]を渡し、これを育て上げたいと思います。
 
let rec myListMap1 accum f lst =
    match lst with
    | [] -> accum
    | hd :: tl -> myListMap1 (accum @ [(f hd)] ) f tl
 
行き順に、取り出した要素にfを適用してそれを、リスト化し、accumの後ろに付け足してaccumを育てていっています。
 
実行例
 
> myListMap1 [] (fun x -> 2*x) [1;2;3];;
val it : int list = [2; 4; 6]
 
ただ、要素連結の@はとてもコストが高いので、このかわりに::を使います。そうしておいて最後にひっくり返したものを返すことにします。改良したコードは次のようになります。
 
let myListMap2 f lst =
 
    let rec subMyLL accum lst2 =
        match lst2 with
        | [] -> accum
        | hd :: tl -> subMyLL ((f hd) :: accum) tl
 
    List.rev (subMyLL [] lst)
 
 
実行例
 
> myListMap2 (fun x -> 2*x) [1;2;3];;
val it : int list = [2; 4; 6]
 
 
それでは宿題です。List.foldと同じ働きをする関数myListFoldを定義してみてください。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。