---
title: Functional Way
tags:  #関数型プログラミング #python #haskell #clojure  
author: [Kent OHASHI](https://www.docswell.com/user/lagenorhynque)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/4JMZ1ZDNEW.jpg?width=480
description: フィボナッチ数の計算を例に関数型プログラミングの基本的な概念を紹介。 関数型プログラミングを始めよう!
published: September 24, 16
canonical: https://www.docswell.com/s/lagenorhynque/K8G23Y-functional-way
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/4JMZ1ZDNEW.jpg)

Functional Way


# Page. 2

![Page Image](https://bcdn.docswell.com/page/PJR6L64479.jpg)

自己紹介: lagénorhynque


# Page. 3

![Page Image](https://bcdn.docswell.com/page/PEXMWM2Z7X.jpg)

(defprofile lagénorhynque [Kent OHASHI]
:github/twitter @lagenorhynque
:company
:languages
[Clojure Haskell Python Scala Go
English français Deutsch русский]
:interests
[
])
株式会社オプト
プログラミング 語学 数学


# Page. 4

![Page Image](https://bcdn.docswell.com/page/3EKGVGMVJD.jpg)

フィボナッチ数」(Fibonacci number)の計算を例に
関数型プログラミングの基本的な概念を紹介
「
1.
2.
3.
4.
再帰 (recursion)
末尾再帰 (tail recursion)
高階関数 (higher-order function)
遅延評価 (lazy evaluation)


# Page. 5

![Page Image](https://bcdn.docswell.com/page/L73NMN2Q75.jpg)

フィボナッチ数
i
番目のフィボナッチ数 は、以下のように定義される。
Fi
F0 = 0
F1 = 1
Fi = Fi−2 + Fi−1 , i
≥
2
と続き、
直前の2項の和が次の項になっている。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .


# Page. 6

![Page Image](https://bcdn.docswell.com/page/87DW6WZWJG.jpg)

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)


# Page. 7

![Page Image](https://bcdn.docswell.com/page/VJP9Y9DXE8.jpg)

変数やループ構造が目立ち、数学的な定義(プログラムの仕様)との関
係が分かりづらい
登場する変数が多くなったり、処理が複雑になったりすると、状態の
変化をたどるのが困難になりうる


# Page. 8

![Page Image](https://bcdn.docswell.com/page/2EVMGM13EQ.jpg)

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)


# Page. 9

![Page Image](https://bcdn.docswell.com/page/57GG8G2Y7L.jpg)

数学的な再帰的定義をほぼそのまま表現した、シンプルなコード
可変状態がないため状態の変化を管理する必要がなくなり、並列/並
行処理として実行するのも比較的容易
関数呼出しの繰り返しによりスタックオーバーフローが発生する可能
性がある
フィボナッチ数の場合、同一の計算が繰り返されて計算量が指数的に
増大してしまう→メモ化(memoization)を検討


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4EQX9XP67P.jpg)

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)))


# Page. 11

![Page Image](https://bcdn.docswell.com/page/KJ46X6YM71.jpg)

多くの関数型言語では末尾再帰関数が末尾呼出し最適化(tail call
optimization)により命令型のループと同等の処理に変換され、スタ
ックオーバーフローが防止できる
コードの処理内容も命令型ループによく似ている


# Page. 12

![Page Image](https://bcdn.docswell.com/page/LE1VNV6Y7G.jpg)

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)))))


# Page. 13

![Page Image](https://bcdn.docswell.com/page/GEWL4LW172.jpg)

典型的な繰り返し処理は抽象化されたライブラリの高階関数に任せ、
固有のロジックを持った関数の実装に集中することで、効率良くコー
ディングすることができ、コードの可読性も向上する
オブジェクト指向プログラミングのデザインパターンの多くは高階関
数によって同等の目的を果たせる


# Page. 14

![Page Image](https://bcdn.docswell.com/page/47ZM2M5XE3.jpg)

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)))


# Page. 15

![Page Image](https://bcdn.docswell.com/page/YJ6NVN9PJV.jpg)

-- 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)))


# Page. 16

![Page Image](https://bcdn.docswell.com/page/GJ55D5NPJ4.jpg)

では遅延評価がデフォルトの評価戦略
は先行評価が基本だが、遅延評価されるシーケンス(遅延シー
ケンス が利用できる
特に巨大なデータ構造や無限に続くデータ構造を扱う場合に、シンプ
ルな定義と効率を両立させることができる
Haskell
Clojure
)


# Page. 17

![Page Image](https://bcdn.docswell.com/page/LE3NMN26E5.jpg)

Further Reading
Haskell
プログラミングHaskell』
すごいHaskellたのしく学ぼう!』
関数プログラミング実践入門』
『
『
『
プログラミング
Clojure
『
Clojure』
Exploring Clojure with Factorial Computation
Scala
スケーラブルプログラミング』
関数型デザイン&プログラミング』
『Scala
『Scala


# Page. 18

![Page Image](https://bcdn.docswell.com/page/8EDW6WZM7G.jpg)

Erlang
すごいErlangゆかいに学ぼう!』
『
Elixir
プログラミングElixir』
『
OCaml
プログラミングの基礎』
『
cf.
今回の発表の元ネタ: BasicsOfFunctionalProgramming.md