Functional Way
142 Views
September 24, 16
スライド概要
フィボナッチ数の計算を例に関数型プログラミングの基本的な概念を紹介。
関数型プログラミングを始めよう!
「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬
関連スライド
各ページのテキスト
Functional Way
自己紹介: lagénorhynque
(defprofile lagénorhynque [Kent OHASHI] :github/twitter @lagenorhynque :company :languages [Clojure Haskell Python Scala Go English français Deutsch русский] :interests [ ]) 株式会社オプト プログラミング 語学 数学
フィボナッチ数」(Fibonacci number)の計算を例に 関数型プログラミングの基本的な概念を紹介 「 1. 2. 3. 4. 再帰 (recursion) 末尾再帰 (tail recursion) 高階関数 (higher-order function) 遅延評価 (lazy evaluation)
フィボナッチ数 i 番目のフィボナッチ数 は、以下のように定義される。 Fi F0 = 0 F1 = 1 Fi = Fi−2 + Fi−1 , i ≥ 2 と続き、 直前の2項の和が次の項になっている。 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
0. ループ 手続き型(procedural)言語の基本パターン # Python def fibonacci(i): a, b = 0, 1 for n in range(i): a, b = b, a + b return a 副作用(side e ect) 命令型(imperative)
変数やループ構造が目立ち、数学的な定義(プログラムの仕様)との関 係が分かりづらい 登場する変数が多くなったり、処理が複雑になったりすると、状態の 変化をたどるのが困難になりうる
1. 再帰 (recursion) 関数型(functional)言語の基本パターン -- Haskell fibonacci1 :: Int -> Integer fibonacci1 0 = 0 fibonacci1 1 = 1 fibonacci1 i = fibonacci1 (i - 2) + fibonacci1 (i - 1) ;; Clojure (defn fibonacci1 [i] (cond (= i 0) 0N (= i 1) 1N :else (+ (fibonacci1 (- i 2)) (fibonacci1 (- i 1))))) パターンマッチング(pattern matching) 宣言型(declarative) 参照透過性(referential transparency)
数学的な再帰的定義をほぼそのまま表現した、シンプルなコード 可変状態がないため状態の変化を管理する必要がなくなり、並列/並 行処理として実行するのも比較的容易 関数呼出しの繰り返しによりスタックオーバーフローが発生する可能 性がある フィボナッチ数の場合、同一の計算が繰り返されて計算量が指数的に 増大してしまう→メモ化(memoization)を検討
2. 末尾再帰 (tail recursion) 関数内部で最後に実行される処理が再帰呼出しになっている再帰 -- Haskell fibonacci2 :: Int -> Integer fibonacci2 i = fib i 0 1 where fib 0 a _ = a fib n a b = fib (n - 1) b (a + b) ;; Clojure (defn fibonacci2 [i] (letfn [(fib [n a b] (if (zero? n) a (recur (dec n) b (+ a b))))] (fib i 0N 1N)))
多くの関数型言語では末尾再帰関数が末尾呼出し最適化(tail call optimization)により命令型のループと同等の処理に変換され、スタ ックオーバーフローが防止できる コードの処理内容も命令型ループによく似ている
3.
高階関数 (higher-order function)
引数として関数を受け取る、または戻り値として関数を返す関数
-- Haskell
fibonacci3 :: Int -> Integer
fibonacci3 i = fst $ foldl' fib (0, 1) [1..i]
where
fib (a, b) _ = (b, a + b)
;; Clojure
(defn fibonacci3 [i]
(letfn [(fib [[a b] _]
[b (+ a b)])]
(first (reduce fib [0N 1N] (range 0 i)))))
典型的な繰り返し処理は抽象化されたライブラリの高階関数に任せ、 固有のロジックを持った関数の実装に集中することで、効率良くコー ディングすることができ、コードの可読性も向上する オブジェクト指向プログラミングのデザインパターンの多くは高階関 数によって同等の目的を果たせる
4.
遅延評価 (lazy evaluation)
式の評価を計算で必要になるまで遅らせる評価戦略
cf. 先行評価(eager evaluation)
-- Haskell
fibonacci4 :: Int -> Integer
fibonacci4 i = fibs !! i
where
fibs = map fst $ iterate (\(a, b) -> (b, a + b)) (0, 1)
;; Clojure
(defn fibonacci4 [i]
(let [fibs (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N]))]
(nth fibs i)))
-- Haskell fibonacci5 :: Int -> Integer fibonacci5 i = fibs !! i where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) ;; Clojure (defn fibonacci5 [i] (letfn [(fibs [a b] (cons a (lazy-seq (fibs b (+ a b)))))] (nth (fibs 0N 1N) i)))
では遅延評価がデフォルトの評価戦略 は先行評価が基本だが、遅延評価されるシーケンス(遅延シー ケンス が利用できる 特に巨大なデータ構造や無限に続くデータ構造を扱う場合に、シンプ ルな定義と効率を両立させることができる Haskell Clojure )
Further Reading Haskell プログラミングHaskell』 すごいHaskellたのしく学ぼう!』 関数プログラミング実践入門』 『 『 『 プログラミング Clojure 『 Clojure』 Exploring Clojure with Factorial Computation Scala スケーラブルプログラミング』 関数型デザイン&プログラミング』 『Scala 『Scala
- https://estore.ohmsha.co.jp/titles/978427406781P
- https://estore.ohmsha.co.jp/titles/978427406885P
- http://gihyo.jp/book/2014/978-4-7741-6926-2
- https://estore.ohmsha.co.jp/titles/978427406913P
- http://noahlz.github.io/factorials/factorials.core.html
- http://book.impress.co.jp/books/1116101021
- http://book.impress.co.jp/books/1114101091
Erlang すごいErlangゆかいに学ぼう!』 『 Elixir プログラミングElixir』 『 OCaml プログラミングの基礎』 『 cf. 今回の発表の元ネタ: BasicsOfFunctionalProgramming.md