再帰で
Listモジュールを
再実装
自己紹介
twitter: @nakamura_to
F#歴: 2年半くらい
F#で書いたプロダクトたち
再帰呼び出しって?
recキーワードで
let rec sumList xs =
match xs with
| [] -> 0
| y::ys -> y + sumList ys
末尾再帰を最適化する仕組みあり
let rec sumListTailRecHelper accumulator xs =
match xs with
| [] -> accumulator
| y::ys -> sumListTailRecHelper (accumulator+y) ys
let sumListTailRec xs = sumListTailRecHelper 0 xs
再帰にまつわる誤解
F#を使うには再帰の知識は必須?
ノー。
ListとかSeqのモジュールで済むことが多い。
再帰の使いどころ
判別共用体などの入れ子構造をトラバースするときに活躍。
type Expr =
| Num of int
| Add of Expr * Expr
let rec eval exp = match exp with
| Num n -> n
| Add (x,y) -> eval x + eval y
eval (Add(Num 1, (Add(Num 2, Num 3))))
|> printfn "%A" // 6
再帰への興味
「Scheme手習い」という本を読んだら面白かった。
再帰だらけで継続とかでてくる。
F#でもいろいろ書いてみたくなった。
じゃあ、Listモジュールを再実装してみよう。
なぜListモジュール?
関数型言語を学ぶには標準ライブラリのListモジュールを
自前で書くのが勉強になると聞いたことがある。
Listモジュールの関数はよく使う。つまり、大部分の
関数の仕様を理解しているので取り組みやすい。
答え合わせは、FsCheckを使ってできる。
標準ライブラリのソースコードには最適化処理が
入っているので、コードベースでは答え合わせしにくい。
実装にあったっての前提
-
標準のListモジュールの関数には依存しない
- 破壊的代入は使わない
- forループは使わない
-
パフォーマンスは気にしない
- 例外の型は標準のListモジュールに合わせていない
- zip3とかunzip3とか実装していないものも若干あり(zipやunzipの実装と大差ないので)
-
テストはNUnitとFsCheckで
- ものによってはFsCheck使っていないのもあり
実装コード
- XListというモジュール名
- 実装コードとテストコードは1ファイルに混在
- 実装コード間の依存はあり
- foldを使ってreduceを実装とか
再帰の分類
実装してみると同じようなコードがでてくることに気づく
コードの類似性でいくつかのパターンに分類できる
- 探索(見つかったら探索打ち切り)
- アキュムレータで前から集積
- 継続渡し形式で後から収集
関数によっては、2と3どちらでも実装できるものあり
再帰の分類:共通
だいたいどれもこんな感じのコードになる
let 関数名 list =
// 関数内部に再帰関数
//(必要に応じて追加のパラメータをもつ)
let rec loop xs =
// リストをパターンマッチング
match xs with
// リストが空のとき
| [] -> ...
// リストがあるとき (必要に応じて再帰する)
| h :: t -> ...
// 再帰関数の呼び出し
loop list
再帰の分類:探索
exists, find, nthとか
探索じゃないけどiterもこのパターン
(* ('T -> bool) -> 'T list -> bool *)
let exists predicate list =
let rec loop xs =
match xs with
| [] -> false
| h :: t -> if predicate h then true else loop t
loop list
- リストが空のとき、デフォルト値を返すか例外を投げる
- 見つかったらその値を返す。見つからなかったら再帰。
再帰の分類: 前から集積
fold, collectとか
(* ('T -> 'U list) -> 'T list -> 'U list *)
let collect mapping list =
let rec loop xs acc =
match xs with
| [] -> acc
| h :: t ->
let x = mapping h
loop t (match x with
| [] -> acc | ys -> append acc ys)
loop list []
- loopの引数にアキュムレータ
- リストの終端でアキュムレータを返す
再帰の分類:後から収集
foldBack, choose, filterなど
(* ('T -> bool) -> 'T list -> 'T list *)
let filter predicate list =
let rec loop xs cont =
match xs with
| [] -> cont []
| h :: t ->
let x = predicate h
loop t (fun acc ->
cont (if x then (h :: acc) else acc))
loop list id
- loopの引数にコールバック関数
- リストの終端でコールバック関数を実行
- 引数にはアキュムレータを渡す
継続渡し形式
このコードを前頁の実装で分解してみると
filter (fun x -> x % 2 = 1) [1;2;3] // [1; 3]
関数のチェインになる
let cont = id
let cont = fun acc -> cont (if true then (1 :: acc) else acc)
let cont = fun acc -> cont (if false then (2 :: acc) else acc)
let cont = fun acc -> cont (if true then (3 :: acc) else acc)
cont [] // [1; 3]
再帰を学ぶ利点
-
破壊的代入なしでループできることを理解できる
- しかもコンパクトなコードで
- 関数を引数で渡すことに慣れる
- 恒等関数が便利なことに気づける
-
他のプログラミング言語を学びやすくなる
つまり、考えの幅が広がる
まとめ
-
F#の利用に再帰の知識は必須ではない
- ただし、知れば考えの幅は広がる
-
再帰の学習にListモジュールの再実装はお奨め
-
Listの再帰の実装パターンは3つに分けられる
- 探索
- 前から集積
- 後から収集
再帰でListモジュールを再実装
By nakamura_to
再帰でListモジュールを再実装
- 2,141