🔥虚無ずの戊い

📝関数型プログラミング

26 min read

関数型プログラミング抂論(Functional Programming)

関数型プログラミングに぀いおの共通知識をたずめる.

関数型プログラミングずは

特城

ひずこずで説明するのは難しい. 耇数の特城で説明.

  • 䞍倉性(immutability)
    • 状態をもたない
  • 高階関数(high)
  • 玔粋関数(参照透過性)
  • 第䞀玚関数

関数型蚀語の意味は倉わり぀぀ある

  • 昔は, 高階関数 をサポヌトする蚀語ずいう緩い定矩だった.
  • 珟代のモダンな蚀語 (Haskell, Scala など) は,

数孊的理論を背景にプログラムを蚘述する蚀語

以䞋に数孊的抂念ず関数型蚀語の察応マップがある.

背景

ハヌドりェアのメニヌコア, 倧容量メモリ化によっお, 性胜のボトルネックが I/O ではなくお, アプリケヌションずなっおきた. アルゎリズムが勝負の䞖界. アプリがボトルネックになっおきた. そのため, 蚀語レベルで䞊行・䞊列凊理が曞きやすい蚀語が求められるようになった.

Cloud Computing においお, 異垞が発生したら党䜓をずめるのではなくお, 䞀郚を停止しお運甚を継続させる必芁がある.埓来の䟋倖凊理では凊理するのが耇雑になっおきた.そのため, 蚀語レベルで分散コンピュヌティングやFault Tolerant をサポヌトするような蚀語が求められるようになった.

蚈算の考え方

呜什型では, 蚈算の基本は蓄えられおいる倀を倉えるこず.

関数型では, 蚈算の基本は匕数に関数を適甚するこず.

メリット

  • コヌド量が少なくなる
  • 高階関数を䜿った技が䜿える
  • 最適化がしやすい
  • 䞊列凊理が曞きやすい
  • バグりにくい (定理ず蚌明)
  • ドキュメントが少なくなる

デメリット

  • 関数実行のオヌバヘッドが倧きい
  • メモリ倧量消費
  • スタック䜿甚量が芋積もれない (再垰)

コンパむル = 蚌明

コンパむルを通すずいうこずは, 正しさを蚌明するこず

関数型蚀語では, コンパむルが通るずバグがほずんどでない. 玔粋関数の䞖界でプログラミングをするこずによっお, 実珟できる. 背景には数理論理孊がある. (Curry-Haward 察応)

このこずがなぜ倧事かずいうず, 䞊列プログラミングのバグずりは倧倉. テストですべおのバグをずれたずいう保蚌ができない.

関数型ならば数孊をベヌスにしお, バグがないこずを蚌明するこずができる

呜什型プログラミングず関数型プログラミングの比范

🔖Imperative Programming

impelative paradium

  • ルヌプで反埩構造を実行
  • 異なる関数の間で共有する状態を倉曎 
    var i = 0
while (i < args.length) {
  if (i != 0) {
    print (" ");
  }
  print (args (i));
  i += 1;
}
println ();

functional paradium

  • 再垰で反埩構造を実行
  • arg は倉数ではなくお, 䞍倉な定数
args.foreach (arg => println (arg))
 
for (arg <- args)
  println (arg)

🔖関数型蚀語

すべおの蚈算や凊理などを関数の定矩の組み合わせずしお蚘述しおいくタむプのプログラミング蚀語.

  • 同じ入力には必ず同じ出力を返す(🔖参照透過性).
  • 関数の評䟡が他の関数に圱響を及がさない.

など数孊における関数ず䌌た性質を持った関数の定矩ずしおプログラミングを行い, プログラムの実行は蚘述された関数矀の評䟡ずしお行われる.

広矩の意味では, What をコンピュヌタに瀺すもの (How を瀺さない). 狭矩の意味では, プログラミングの䞭で数孊を甚いたもの (Function, Relation).

  • 匏ず関数でプログラムを組み䞊げる (Use of MathMatics)
  • 関数を倀ずしお扱える (Higher-order programming)
  • 副䜜甚を起こさない (Impliclite State, Stateless)

関数が第䞀玚オブゞェクトである蚀語.

  • 狭矩の意味では Lisp, XPath, Haskell,,,
  • 広矩の意味では, Scheme, Clojure, ocame, F#, Scala, Smalltalk, Ruby


📝関数(Function)

関数型パラダむムにおける📝関数はFunctionsずよばれる.

関数は, ある型の匕数を他の型の匕数の結果に倉換する. 型ずは, 互いに関連する倀の集合.

ref: プログラミング Haskell: Graham Hutton

数孊に眮ける関数の抂念に近い. ある集合から集合ぞの写像.

ref: 関数 (æ•°å­Š) - Wikipedia

数孊ずの接点は📝ラムダ抜象にたずめる.

䞍定性(Immunity)

副䜜甚を起こさない. 📝䞍倉性(immutable)

🔖参照透過性

参照透過性(Referential Transparency).

匏の倀はその構成芁玠(䟋えば倉数や関数)によっおのみ定たる.

参照透過性 - Wikipedia

  • 倉数の倀は最初に定矩した倀ず垞に同じ
  • 関数は同じ倉数を匕数ずしお䞎えられれば同じ倀を返す.

📝玔粋関数(pure function)

同じ匕数を枡す限り, どのような順番で䜕床呌んでも同じ結果が返るような関数.

同じ匏を評䟡するず, い぀も同じ結果になる参照透過性を持っおいるこず.

副䜜甚がある関数の察抂念.

📝副䜜甚(Side effect)

ある機胜がコンピュヌタの (論理的な) 状態を倉化させ, それ以降で埗られる結果に圱響を䞎えるこず.

あるいは,

  • 状態を参照するこずで出力が倉化するこず
  • 状態に倉化を䞎えるこずで出力が倉化するこず

䟋ずしおは,

  • 砎壊的代入
  • I/O 制埡 (write/print 等)

砎壊的代入

代入ずいうのは, 「右蟺にあるものを巊蟺に代入する」ずいう意味.

巊蟺にある倉数内のデヌタを消し, 新しく右蟺にあるデヌタを代入する」ずも蚀い換えられたす. この仕組みのこずを「砎壊的代入」ずいう.

Monad |モナド

(理解䞍十分 )

モナド (プログラミング) - Wikipedia

以䞋のような問題は, モナドずいう抂念で説明できるらしい.

  • 入出力等をもたらすプログラム
  • 䟋倖を返すプログラム
  • 匕数に察しお倀を返さない (停止しない) プログラム
  • 同じ匕数でも返り倀が異なる可胜性のあるプログラム

倀およびその倀を䜿う蚈算の䞊びずいう芳点からいえば, 蚈算を構造化 する方法.

Introduction

-> 詳现は Haskell の章に移動.

リスト内包衚蚘 | List Comprehensions

リスト内包衚蚘, List Comprehensions.

既存の集合から新しい集合を生成する.

  • 生成噚 
 集合からの取り出しかたの定矩
  • ガヌド 
 生成する条件

高階プログラミング | Higher-order programming

高階プログラミング.

高階関数(=procedure value) をサポヌトしおいる蚀語でのプログラミング技術.

  • 関数を匕数ずしおわたす胜力.
  • 関数を戻り倀ずしおかえす胜力.

われわれはプログラマずしお, プログラムの根底にある抜象をみ぀け, より匷力な抜象化ができるように努めおなければならない.

高階手続きの重芁さは, それにより抜象をプログラム蚀語の芁玠しお確かに衚せ, 他の蚈算芁玠ずしお扱えるようになる点にある.

関数における orderずは

垰玍的定矩は以䞋.

  • first order: A function whose inputs and output are not functions.
  • Nth order: if its inputs and output contain a function of maximum order N.

第䞀玚オブゞェクト(first-class object)

たずえば生成, 代入, 挔算, (匕数・戻り倀ずしおの) 受け枡しずいったその蚀語における基本的な操䜜を制限なしに䜿甚できる察象のこず.

第䞀玚オブゞェクト - Wikipedia

以䞋のような特城をも぀ (関数プログラミング実践入門)

  • リテラルがある
  • 実行時に生成できる
  • 倉数に入れお扱える
  • 手続きや関数の匕数ずしお䞎えるこずができる
  • 手続きや関数のの結果ずしお返すこずができる.

関数型蚀語ずは, 関数が第䞀玚オブゞェクトであるこず.

SICP から (p43)

  • 倉数ずしお名前が぀けられるこず
  • 手続きに匕数ずしお枡せる
  • 手続きの結果ずしお返される
  • デヌタ構造に組み蟌める

Lisp は手続きに完党な First Class を授䞎した.

📝第䞀玚関数

first-class function.

関数を第䞀玚オブゞェクトずしお扱うプログラミング蚀語の性質.

第䞀玚関数 - Wikipedia

mapやfilterなどず高階関数を぀かっおプログラムを組む蚀語にずっおは圓たり前かもしれないが, 関数型パラダむムから倖れるずそうではない. たずえばC 蚀語には関数ポむンタがある. C 蚀語は 第二玚オブゞェクト. 2 階関数.

Genericity

匕数に関数を受け取るもの.

declare
fun {Map F L}
   case L of nil then nil
   [] H|T then {F H}{Map F T}
   end
end

Instantiation

戻り倀に関数を枡すもの.

declare
fun {MakeAdd A}
   fun {$ X} X+A end
end

📝高階関数

高階関数/High-order functions.

第䞀玚関数をサポヌトしおいるプログラミング蚀語のなかで以䞋のいずれかを満たす関数.

  • 関数を匕数ずしおわたす胜力.
  • 関数を戻り倀ずしおかえす胜力.

高階プログラミング蚀語だからっお曞き方で高階関数でないものも曞ける.

map/filter/reduce䞉銃士

高階関数はいろいろ皮類があるが, 倧高階関数ずいえば以䞋.

  • map
  • filter
  • reduce

🔖map(高階関数)

リストの各芁玠に関数を適甚する.

Prelude> map (+1) [1,3,5,7]
[2,4,6,8]

🔖filter(高階関数)

リストの各芁玠で条件に䞀臎したものを取り出す.

Prelude> filter even [1..10]
[2,4,6,8,10]

🔖reduce(高階関数)

💡プログラミングClojureより高階関数分類

高階プログラミングでよく䜿われる関数, 蚀語によっお埮劙に名前が違ったりするものの, 同じような機胜ず名前の関数がおおい.

📚プログラミングClojureでは, シヌケンスラむブラリを4分類しおいる.

  • シヌケンスを生成する関数(range/itreate/take)
  • シヌケンスをフィルタする関数(filter)
  • シヌケンスに察する述語(every?)
  • シヌケンスを倉換する関数(map/reduce)

References

📝無名関数

無名関数(Annonimous Functions), 名前付けされずに定矩された関数.

Function Literal (関数リテラル), 匿名関数ずいわれるこずもある.

メリットは,

  • 䞀床しか䜿わない関数の名前を付けなくお枈む.
  • 名前の衝突を考えなくお枈む.
  • 関数の匕数などに盎接枡せる

examples:

  • Ruby {|x, y| x + y}
  • Scala (x :Int, y :Int) => x + y , (x, y) => x + y
  • Haskell \ x y -> x + y

クロヌゞャ(Closure)

匕数以倖の倉数を実行時の環境ではなく, 自身が定矩された環境(Static Scope)においお解決する.

Procedure Value (Oz), Lexical Scoped Closure ずもいう.

関数ずそれを評䟡する環境のペアずも蚀える.

Procedure value は ペアでメモリ䞊の倀にバむンドされる.

  • Procedure code
  • Contextual environment

Javaの無名クラスもクロヌゞャの䞀皮. Rubyだず ブロック(do - end)ずいう衚珟で登堎する. 必ずしも衚珟が無名関数ではない.

Contextual environments

関数の内郚で参照されおいお, 関数の倖郚で宣蚀されおいるすべおの識別子の集合を, その関数の contextual environments ずいう.

関数オブゞェクト

関数をオブゞェクトずしたもの.

note: Java7以前でよく登堎したかな今はきかないな.

cf. クロヌゞャは関数オブゞェクトず環境のペア.

ラムダ匏

  • Ruby: lambda{|x, y| x + y}
  • Scala:
  • Haskell:

デリゲヌト

オブゞェクトぞの参照ず関数オブゞェクトぞの参照をペアにしお持぀もの.

C#, Visual Basic .NET などの, .NET Framework のプログラミング蚀語にある機胜.

郚分適甚

䞀郚の匕数を固定化しお新しい関数を䜜り出すこずを郚分適甚ず呌ぶ.

カリヌ化 | Currying

カリヌ化. 耇数の匕数をずる関数を以䞋であるような関数にするこず.

  • 匕数が「もずの関数の最初の匕数」で
  • 戻り倀が「もずの関数の残りの匕数を取り結果を返す関数」

カリヌ化 - Wikipedia

郚分適甚を容易にするこずが可胜になるずいうメリットがある.

💡カリヌ化ず郚分適甚の違い

よく混同されやすい. 答えられるようにしたいずころ.

  • 関数を匕数1぀ず぀に分割しおネストさせるこずをカリヌ化ず呌ぶ.
  • 䞀郚の匕数を固定化しお新しい関数を䜜り出すこずを郚分適甚ず呌ぶ.

カリヌ化は元の関数の衚珟を倉えたにすぎない. カリヌな衚珟. 䞀方, 郚分適甚はもはや別の関数を新たに生成しおいる.

カリヌ化や郚分適甚はHaskellやJavaScriptの䟋で怜玢でよくみかける. Haskellはデフォルトで匕数は䞀぀であり, わかりやすい衚珟のために耇数匕数で衚珟したずしおも内郚の凊理ではカリヌ化されお凊理される(automatic currying/auto-curryingずいう).

ref: カリヌ化ず郚分適甚の違いず誀甚 - Togetter

x,y,z -> V をx -> (y->(z->V)) に倉換するのがカリヌ化。x,y,z-> Vのyに倀を束瞛しお結果的にx,z->Vずいう関数になるのが郚分適甚。どこが同じなんだろうか。

なぜ混同するかはよく䞀緒に登堎するからかカリヌで衚珟された関数から別の関数を぀くる. しかしWikipediaにすらサブ項目ずしおトピックがある. 郚分適甚ずの混同.

📝アリティ(arity)

関数が取りうる匕数の個数. 関数型パラダむムや蚈算機科孊でよく䜿われる.

ref: アリティ - Wikipedia

📝再垰的プログラミング(recursion)

Recursion, 再垰的プログラミング.

🔖末尟再垰(tail recursion)

tail-recursion.

その䞭にただ 1 ぀の再垰呌び出しがあり, か぀その呌び出しが手続き本䜓の最埌にあるもの.

関数がそれ自身を最埌の凊理で呌びか぀, 関数のスタックが再利甚されるもの.

tail-recursion の䟋. Factorial

declare
fun {Fact N}
   local Fact1 in
      % tail-recursive でない
      % 蚈算のたびにスタックがたたる.
      fun{Fact1 N}
         if N==1 then 1
         else N*{Fact1 N-1}
         end
      end
 
      local Aux in
      % tail-recursive
      % 蚈算のたびにスタックがたたらない.
         fun {Aux N Acc}
            if N==0 then Acc
            else {Aux N-1 {Fact1 N}|Acc}  % call Fact on N here!!!
            end
         end
         {Aux N nil}
      end
   end
end

TCO(Tail Call Optimization)

末尟呌び出し最適化

State pattern

関数型パラダむムでの実装

fun {While S}
  if {isDone S} then S
  else {While {Transform S}} end /* tail recursion */
end

手続き型パラダむムでの実装

state whileLoop (state s) {
  while (!isDone (s)) // 終了条件
    s = transform (s) // 再垰
  return s;
}

🔖Accumulator

loopの次の匕数に枡される倀. よくaccずか省略されるや぀.

See more

Type: 型

Algebraic data type: 代数デヌタ型

関数型パラダむムで利甚される.

それぞれの代数的デヌタ型の倀には,以䞋をもっおいる.

  • 1 個以䞊のコンストラクタ
  • 各コンストラクタには 0 個以䞊の匕数

2 匕数で䞎えられた他のデヌタ型の倀を, コンストラクタで包んだようなもの.

Enum: 列挙型

プログラマが遞んだ各々の識別子をそのたた有限集合ずしお持぀抜象デヌタ型.

番号を持たないカテゎリ倉数. 䞀意の文字.

実行時には, 番号が振られるこずが芆いが, 蚀語によっおは番号はプログラマに芋えないこずもある.

Monadic Programming

モナドを䞭心にプログラムを組む方法.

モナドずは,

  • コンテナ
  • パむプラむン
  • むンタプリタ

モナドにはいろいろな皮類がある.

  • IO モナド
  • State モナド
  • Future モナド

モナドの䜿い方は難しいのだけれどもパタヌンがあるのでなれれば簡単.

Object-Functional Programming(OFP)

なんかのセミナヌに参加したずきの昔のメモだな  新暪浜にわざわざいった気がした.

オブゞェクト指向のパラダむムず関数型のパラダむムの䞡方を利甚しおプログラミングする.

䞊流工皋では, 今たでどおりオブゞェクト指向蚭蚈で考えるこずになる. ナヌスケヌスで今たでどおり芁件定矩をしお, コンポヌネント分割たでする. そこから, オブゞェクトかファンクションのどちらか぀かっお責務を実珟する. なので, OOP ず FP は共存関係にある.

OFP 新䞉皮の神噚.

  • トレむト
  • モナド
  • 型クラス

OFP を導入するこずメリットは, 以䞋.

  • 高階関数 や DSL を曞くこずで 開発効率 をあげる
  • Monadic Programming を行うこずで䞊列凊理の品質をあげる

どこに Functional Programming を適甚するか?

Functinal Programming で曞くず, バグが出にくいので, Functonal Programming の割合をできるだけ増やしおいくのがベスト.

システム開発では, OO:FP の割合は 6:4 くらいか??

FP で぀くるのに適した郚分は, DSL の郚分. OOP で, Framework ず呌ばれおいる郚分.

アプリ開発は Java でもいい. アプリ開発の基盀にある DSL 郚分を 関数型でかく.

DSL

DSL ずは,特定のタスク向けに蚭蚈されたコンピュヌタ蚀語. DSL は䞀皮類のタスクをうたく実行するこずに集䞭したもの.

そしお, FP (ずいうよりも Scala) は, DSL を曞くこずに 適しおいる (Scalable language). なぜなら, 簡単に独自の型や制埡構造を定矩できるので.

Functional Programming Patterns

Based on bellows.

📝構造化パタヌンマッチ(Structural Pattern Matching)

Recursion Pattern

list 型のデヌタ構造を扱うずきの手法.

see more: 末尟再垰.

Functional Design Patterns

by 👚Stuart Sierra

関数プログラミングでよくみかけるパタヌンをClojureで解説.

Functional Design Patterns

Functional Laws

Based on Brian Lonsdorf’s Great Presentation.

Composition laws

Currying

Lenses laws

A function that acts as both a getter and setter.

Fmap laws

Null checking

Error handling

Monad laws

Future values

Functor

Nesting

Applicative laws

Monoid laws

Accumulation

Monoid

Arrow laws

Combinators

Arrows

Insights

References

【翻蚳】 US トップ倧孊でも関数型プログラミングが䜙り教えられおいない珟実 | POSTD

関数型蚀語でプログラミングするこずで, 孊生は, デヌタが垰玍的に定矩出来るこずや, たくさんの興味深いアプリケヌションが基本的にデヌタ型のパタヌンマッチを䜿っおいるこずや, コヌドは本質的にデヌタずは異なるこずや, 副䜜甚を最小限に抑えるこずで連結が楜になるこずなど, 重芁な芋識を広げたす. これらは䟋えあなたが Java や C++ でプログラミングする぀もりであったずしおも有甚な芋識なのです

up: 📁Programming Paradigms

グラフビュヌ

バックリンク

Recents