狠狠撸

怖くないよ
怖くないよ

たのしい関数型
ー関数型言语入门

目的
本勉強会の趣旨

本セッションは関数型入門です
たのしく関数型を学ぶことを目的
としております。

目的
本勉強会の趣旨 -ATENDより

本セッションは関数型入門です
たのしく関数型を学ぶことを目的
としております。

大事なことなので
２回いいました

注意事项

Monad
圏論
?????解析がどうとか

α-変換、β-簡約がどうとか

関数型には難しい概念もありますが??

注意事项

Monad
圏論
?????解析がどうとか

α-変換、β-簡約がどうとか

当セッションの範囲外です

注意事项

関数型には怖い人がいるらしいですが??特に東方

注意事项

会場を間違えていませんか？

注意事项

THIS IS スパルタ！！

たのしく
学びましょう～

Status
所属 : SIer
Java : 195
Scala : 30
小酒信一 Hakell : 35
システムアーキテクト
協調性 : 2
せいべつ：おとこ
レベル： 0x24 さいだいHP : 24
Twitter ： s_kozake さいだいMP : 1
ステータス : 緊張
E GATEWAY ノートPC
E 結婚指輪 GOLD : 0

関数型とは？
副作用を持たない関数を中心にして
プログラムを組み立てる手法

関数型とは？

副作用を持たない関数とは？
同じ関数をなんど呼び出しても。
同じ引数についていつも同じ結果
「今回」f(x) = a　なら、「次回」もf(x)=a

関数型とは？

副作用を持たない関数とは？
同じ関数をなんど呼び出しても。
同じ引数についていつも同じ結果
「今回」f(x) = a　なら、「次回」もf(x)=a
=

等式推論

具体例
JavaでListを扱うコード

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

System.out.println(list.get(0)); // 1

list.set(0, 4);

具体例
JavaでListを扱うコード

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);


list.set(0, 4); 副作用
副作用

Listの内部状態を変更している

具体例
ScalaでListを扱うコード

val list = List(1, 2, 3)

println(list(0)) // 1

val list2 = list.updated(0, 4)
println(list(0)) // 1
println(list2(0)) // 4

具体例
ScalaでListを扱うコード

val list = List(1, 2, 3)

println(list.apply(0)) // 1

val list2 = list.updated(0, 4)
println(list.apply(0)) // 1
println(list2.apply(0)) // 4

新しいListを作成している

具体例
JavaのStringクラス

final String str = "abc";

System.out.println(str); // "abc"
final String str2 = str.substring(1);

System.out.println(str); // "abc"
System.out.println(str2); // "bc"

JavaのStringクラスは不変

なぜ関数型？
CPUのマルチコア化
?10年後には、コア1000!?
?今まで以上に平行プログラミングが重要
?副作用のない関数型は並行処理と相性がいい

なぜ関数型？
CPUのマルチコア化
?10年後には、コア1000!?
?今まで以上に平行プログラミングが重要
?副作用のない関数型は並行処理と相性がいい

Java8にラムダが導入されるのも、
CPUコア数増加に対応し、並行処理を
効率よく扱うため

なぜ関数型？
高階関数
?関数がファーストクラスオブジェクト
?コードパターンを再利用しやすい
?リストのライブラリが使いやすい
?map
?fiter
?foldl / foldr
?find
?etc..

なぜ関数型？
内部DSL
?Domain Specific Language、領域特化言語
?高階関数や遅延評価をもつ関数型は
　内部DSLを作成しやすい。
　「ホスト言語」として有力候補

なぜ関数型？
?「HOW」から「WHAT」へ
ハードウェア性能の向上
関数型
オブジェクトオブジェクト
指向型指向型

手続き型手続き型手続き型

?クイックソートのコード例
qsort [] = []
qsort(x:xs) = qsort l ++ [x] ++ qsort r
where l = [a | a <- xs, a < x]
r = [a | a <- xs, a >= x]

なぜ関数型？
ハッカーになれる！？

LISP は、それをモノにしたときのすばらしい
悟り体験のために勉強しましょう。
この体験は、その後の人生でよりよい
プログラマーとなる手助けとなるはずです。
たとえ、実際には LISP そのものをあまり
使わなくても。
～ハッカーになろう～より抜粋
http://cruel.org/freeware/hacker.html

リストとは？
?同じ型の要素の並び
　関数型言語として最も代表的なデータ構造

?神は言われた。「リストあれ」
　リストを処理するのが関数型言語の
　プログラミングというほど、関連が深い

?単一方向の線型リスト
head tail head tail []

1 2

リストとは？
コード例（HaskellのREPLでの例）

リストとは？
コード例（HaskellのREPLでの例）

zs

0 ys

xs []

1 2 3

リストとは？
文字列もリストとして扱われる

タプルとは？
?有限個の要素の組。
　各要素の型は異なってもいい

?要するに、構造体

?要素数0のタプルはユニットと呼ばれる
　要素数2のタプルは組、3は三つ組

タプルとは？
人間関係で考えると

組二股三つ組

リスト内包表记とは？

?数学の内包表記は、既存の集合から
　新しい集合を生成する。
2
{ X | X ∈ {1..5}} = {1, 4, 9, 16, 25}

?既存のリストから新しいリストを生成する
　のがリスト内包表記

2
[ X | X ← [1..5]]
生成器

複数の生成器も列挙できる。

[ X×Y | X ← [1..3],Y←[1..3]]

生成器生成器

Javaで書くと、こんなイメージ
List<Integer> xs = new ArrayList<Integer>();
xs.add(1); xs.add(2); xs.add(3);

List<Integer> ys = new ArrayList<Integer>();
ys.add(1); ys.add(2); ys.add(3);

List<Integer> ret = new ArrayList<Integer>();

for (int x : xs) {
for (int y : ys) {
ret.add(x * y);
}
}

System.out.println(ret);

ガードと呼ばれる論理式も使用できる

[ X | X ← [1..10], X `mod` 2 =0]

生成器ガード

複数の生成器とガードの組み合わせ
[ X×Y | X ← [1..4], even X, Y←[1..4], oddY]

生成器ガード生成器ガード

[(0×1), (0×3),(2×1), (2×3),(4×1), (4×3)]

Javaで書くと、こんなイメージ

for (int x : xs) {
if (x % 2 == 0) {
for (int y : ys) {
if (y % 2 == 1) {
ret.add(x * y);
}
}
}
}

System.out.println(ret);

Scalaでは、for式をリスト内包表記として
使える

scala> for (x <- 0 to 4 if x % 2 == 0;
y <- 0 to 4 if y % 2 == 1) yield x * y
res3: scala.collection.immutable.IndexedSeq[Int] =
Vector(0, 0, 2, 6, 4, 12)

関数zip
2つのリストをとり、対応する要素を組として
1つのリストをつくる関数

zip [1,2,3] [4,5]

短いリストにあわせられる
短いリストにあわせられる

zipを人間関係で考えると

ListW

ListM

余りは切り捨てられます
余りは切り捨てられます

再帰関数とは？
?関数自身を使って定義された関数のこと

?関数型言語では、ループを実現する仕組み
　として再帰が使われる。

?クイックソートのコード例
qsort [] = []
qsort(x:xs) = qsort l ++ [x] ++ qsort r
where l = [a | a <- xs, a < x]
r = [a | a <- xs, a >= x]

Nまで階乗を求める関数 func

0 × 1 × 2 ×... N
副作用を伴うループを使ったケースと
副作用を伴わない再帰を使ったケースで
書いてみる。

副作用を伴うループを使ったケース

def fact(n :Int):BigInt = {
var ret = BigInt(1)
for (i <- 1 to n) {
ret = ret * i
}
ret
}

副作用を伴わない再帰を使ったケース

if (n == 0) {
1
} else {
n * fact(n - 1)
}
}

副作用を伴わない再帰を使ったケース

if (n == 0) {
1
} else {
n * fact(n - 1)
}
}

0の階乗は1 <=基底部
nの階乗は n + (n-1)の階乗 <=再帰部

再帰関数の考え方

1. 型を定義する
factはInt型のnを受け取り、BigInt型を返す
def fact(n:Int):BigInt

2. 場合分けをする
3. 簡単な方を定義する
4. 複雑な方を定義する


nが0の場合
nが0以外の場合



0の階乗は1



nの階乗は n × (n-1)の階乗

再帰の問題点
> scala Fact1 10000
284625968091705451890641321211986889...
>
> scala Fact2 10000
java.lang.StackOverflowError
:

再帰の問題点
> scala Fact1 10000
284625968091705451890641321211986889...
>
> scala Fact2 10000
java.lang.StackOverflowError
:

fact(3)
= 3 × fact(2)
スタックの使いすぎ
= 3 × 2 × fact(1)
= 3 × 2 × 1 × fact(0)
=3×2×1×0

StackOverflowErrorが発生しないfact定義
def fact(n: Int):BigInt = {
def factorial(n: Int, acc: BigInt):BigInt = {
if (n == 0) {
acc
} else {
factorial(n - 1, n * acc)
}
}
factorial(n, 1)
}

if (n == 0) {
acc
} else {
}
}
factorial(n, 1)
}

fact(3) = factorial(3, 1) スタックを
= factorial(3 - 1, 3 * 1) 消費しない
= factorial(2 - 1, 2 * 3)
= factorial(1 - 1, 3 * 6)
= 24

if (n == 0) {
acc
} else {
}
}
factorial(n, 1)
}

fact(3) = factorial(3, 1) スタックを
= factorial(3 - 1, 3 * 1) 消費しない
= factorial(2 - 1, 2 * 3)
= factorial(1 - 1, 1 * 6)
=6

末尾再帰とは

一番最後に自分自身を再帰的
に呼び出している関数

末尾再帰関数の結果値を持ち運ぶ
引数accはアキュムレータと呼ばれる

ちなみに、Java8よりJavaにも
末尾再帰が導入されるらしい

ラムダとは？
だっちゃ

ラムダとは？
引数のパターン、および
引数から結果を計算する本体
からなる、関数名を含まない式。

ラムダとは？
要は無名関数

ラムダとは？
要は無名関数

こんな感じ＝＞
λx.x+x
引数のパターン結果を計算する本体

ラムダとは？
こんな感じに使える

>(λx.x+x) 2
4

ラムダとは？
例えば、add関数

add x y = x+y
このようにも表現できる

add = λxy.x+y

ラムダとは？
JavaScriptと比較すると分かりやすい。
（厳密にはちがいますが。。）

add = λxy.x+y

varadd = function(x,y){ return x+y; }

ラムダとは？
Haskell
> let f = n -> n * n
> :type f
f :: Integer -> Integer
> f(10)
100

Scala
scala> val f = (n:Int) => n * n
f: Int => Int = <function1>

scala> f(10)
res0: Int = 100

ラムダとは？
Java8
public static interface Func<T, R> {
public R eval(T p);
}

public static void main(String[] args) {
Func<Integer, Integer> f = (Integer n) -> n * n;
System.out.println(f.eval(10));
}

> java Lambda
100

ラムダとは？
SAM(Single Abstract Method) type
SAM(Single Abstract Method) type
Java8
public static interface Func<T, R> {
public R eval(T p);
}

Func<Integer, Integer> f = (Integer n) -> n * n;
System.out.println(f.eval(10));
}

インターフェース実装の
インターフェース実装の
> java Lambda シンタックスシュガー
シンタックスシュガー
100

高阶関数とは？高
い
意
　そ識
　れで
　が書
高俺く
階の
関
数
だ

高阶関数とは？
引数として関数を取ったり、
返り値として関数を返したりする関数

高階関数を利用したライブラリ関数が
超便利！
?map
?fiter
?foldl / foldr
?find
?etc..

好きな関数：if

そうだ！if式を作ろう

(　???)o彡°

Haskell
myIf :: Bool -> a -> a -> a
myIf cond t f = case cond of
True -> t
False -> f

実行結果
> let a = myIf (1==1) (n -> n+n) (n -> n*n)
> :type a
a :: Integer -> Integer
> a 10
20

Scala
def myIf[T] (cond: Boolean, t: => T, f: => T):T =
cond match {
case true => t
case false => f
}

val a = myIf(1 == 1, (n:Int) => n + n, (n:Int) => n * n)
println(a(10))

実行結果
> scala MyIf
20

Java8
public static <T, R> Func<T, R> myIf(boolean cond,
Func<T, R> t, Func<T, R> f) {
return cond ? t : f;
}
Func<Integer, Integer> a =
myIf(1==1,(Integer n) -> n + n, (Integer n) -> n * n);
System.out.println(a.eval(10));
}

実行結果
> java MyIf
20

クロージャーとは？
Scala 実行結果
object Closure extends App { >scala Closure
def inc(n:Int): () => Int = { 2
var m = n 3
() => { m = m + 1; m } 11
} 12

val f1 = inc(1)
val f2 = inc(10)

println( f1() );
println( f1() );

println( f2() );
println( f2() );
}

クロージャーとは？
クロージャーとは関数の一種

引数以外の変数を、自身が定義された環境
において解決する仕組み

関数とメモリ空間のセット
関数にメモリ空間がくっついているイメージ

カリー化とは？
カリー
　カリー

カレーじゃないよ。
論理学者 Haskell Curry さんの名前から
つけられた。
関数は関数を返り値として返せる性質を
活かし、二つ以上の引数を持つ関数を、
一度に一つの引数を取る関数として定義する
ことをカリー化と表現する。

x と y の和を求めるadd関数

a -> (a ->a)
add は1つの数値をとり、
数値をとって数値を返す関数
を返す

x と y の和を求めるadd関数

部分適用という

Scala
scala> def add(x:Int)(y:Int) = x + y
add: (x: Int)(y: Int)Int

scala> val addOne = add(1)_
addOne: Int => Int = <function1>

scala> addOne(10)
res0: Int = 11

How to Study？
おすすめ本（Haskell）
プログラミングHaskell ふつうのHaskellプログラミング

How to Study？
おすすめ本（Scala）
Scala 第2版（コップ本） Scala実践プログラミングの3章

ご清聴ありがとうございました！

狠狠撸

たのしい関数型

Recommended

More Related Content

What's hot (20)

Viewers also liked (16)

Similar to たのしい関数型 (20)

More from Shinichi Kozake (19)

Recently uploaded (8)

たのしい関数型