プログラミング Haskell 第6章 再帰関数

プログラミングHaskell

先週は1日しか読めませんでした。天候不順は朝の読書会の大敵です。
さて第6章はループは再帰、でおなじみの再帰関数についてです。

• 基底部(再帰のないパターン)と再帰部(あるパターン)でできるのが一般的(そうしないと止まらない)
  • 数学的帰納法みたいですね
• リストに対する再帰
  • リストパターンを用いて先頭(car)と残り(cdr)を取り出すのが定石
  • 空リストのパターンが基底部になるのが定石
• 複数の引数をとる再帰関数
  • zip の例では基底部が2つ必要(いずれかのリストが空)
• 多重再帰
  • 再帰部で自分自身を複数回再帰的に利用する(ex. fibonacci, qsort)
• 相互再帰
  • 1つの関数が直接自分を利用するのではなく複数の関数が相互に参照しあって循環しているもの
• 再帰の秘訣 5ステップ
  1. 型を定義する
  2. 場合分けをする
  3. 簡単な方(たいてい定義部)を定義する
  4. 複雑なほうを定義する
  5. 一般化し(型)、単純にする(実装)
     • foldl を使って見た目は再帰じゃなくなってしまった
     • 「再帰を極めるとあまり再帰を(明示的に)使わなくなる(意訳)」

最後の実例が参考になりました。