Haskell の難しさを分割し、理解していく

最近 Haskellを学び始めたばかりだが、Haskell の難しさについて、思いつくままに dump した。
学び始めて２週間程度の初心者なので間違い多数あるかも。随時修正しよう。
自分用の書き散らし。
他人が理解できるように書くというのは優先度として低く、自分の理解メモを dump しといて隙間時間に iPhone で見ておさらいするのが主目的。
自分がちゃんと理解しきったら整理して綺麗にしては行きたいけども。。。

Divide and conquer strategy for learning Haskell

Haskell を理解することの難しさには色々な難しさが混合している。
Haskell は他の多くの主流言語(C, Java, JavaScript, Python..)と違うところが沢山。
違いは、用語や、概念(concept)、シンタックス、必要となる背景知識等、多岐に渡る。
これらの違いが膨大すぎて、圧倒され(overwhelmed)、返り討ちに合い、諦めるというのが良くあるパターン。
訳の分からん点があまりに多いから圧倒され、息ができなくて窒息する訳だが、理解できる部分を少しずつ
増やしていけば、当然ながら圧倒される部分は少なくなり、息ができるようになり、最終的には楽しんで読み書きできるようになるはずだ。

例えば第一級関数(first-class function)とか、高階関数(higher-order-function)とか、Haskell じゃなくても、Lisp や JavaScript でも出てくる。
こういう概念、技は最初に出会った時は訳わからんし、色々と引っかかるもんだが、一度理解してしまうと、別のプログラミング言語で higher-order-function とか言われても理解できるもんだ。
高階関数を理解していないと、Haskell をその分難しく感じるが、それは "Haskell 自体"の難しさではないとも言える。
フィボナッチ数列とかもそうで、例として知らん用語、数列が出てくると難しいと感じ敬遠してしまうが、これは Haskell の難しさとは直接関係なく、そもそもフィボナッチ数列を知っているか？知っていないかというだけの事だったりする。
Haskell の難しさは、プログラミングテクニック、データ構造、用語・概念の難しさ等、諸々の難しさの総合だ。
分からない点を細かく分割・分類し、分割した狭い範囲で、ほわほわな輪郭を明確化していくしか無い。

用語の難しさ(terminologies.. It involve translation difficulties)

• 数学の特定分野の用語、概念の難しさ(圏論(category theory)とか。) → 無視するべし。忘れるべし。
• モナド、副作用、作用、純粋関数、

プログラミングパラダイム(何を主軸に据えているか)の難しさ。

• 関数型(functional programming), 命令形(imperative programming), オブジェクト指向(Object oriented)
• Functional programming: (主軸) = 値を作り出す(=計算する), calculate value by function.
• Imperative programming: (主軸) = order then execute without no delay. 指示を与えて、次々やっていく。指示を与える → 今やれ！

遅延評価の難しさ

• 評価戦略というものがある。どのタイミングで evaluate されるか？評価戦略には２種類ある
  • 正格評価戦略 vs 遅延評価戦略(strict evaluation strategy vs lazy evaluation strategy)
• order of evaluation
• purity is mandatory to achieve lazy evaluation
• pattern match drives evaluation: パターンマッチが値評価を要請する。ただし必要な量のみ。
• thunk とは？(評価前のexpression。expression 自体). thunk が evaluate されて value になる。

純粋関数(Pure function)とは？

• 副作用とは？: 外界とのコミュニケーション全て。外部は汚れているから外界とやり取りすると、同じ引数与えても、実行結果が同じになるとは保証できない？→非純粋

日本語への翻訳の難しさ

evaluation strategy, side effects, type class, reduce etc...,
Haskellに限らないが、ドンピシャの対訳がない場合も多いので、日本語にした場合に原語(英語)のニュアンスが少なからず消し去られる。重要な用語(terminology)は英語のママで理解しようと努め、理解にたどり着くための足がかりとして、母国語である日本語の助けを借りる、という姿勢が良い。
なので、type class 一つとっても、class を一つの用語に翻訳して満足するのではなく、class という用語が持つ様々なイメージを通して type class という言語を消化した方が広がりが出る気がする。
reduce は"減らす", "まとめる", "還元"とかの意味があるが、どれか一つのみ pick すると他のニュアンスが消える、薄まる。もったいない。

慣れの問題

• map, reduce, fold 自体に他の言語で慣れているか？？

再帰の難しさ

for ループよりは、recursive function で表現する傾向。
Recursive function は stop 条件が肝(=必須)。empty list([]) で stop が定番。

型の難しさ

• dynamic language vs typed language

• type inference(型類推)

• 型は邪魔者か？→言語による→型類推があると型を書くのをサボれる。→メリット大きい →コンパイラが助けてくれる。

• null がある？→ 無い気がする。。どうなんだろう

• Maybe 型について: 値が返ってくるかも知れないし、こないかもしれない。Maybe は型として値がない場合もある(=Nothing)可能性を表明する。Maybe を受け取る関数は Just と Nothing を handling する事を強制される(??? exhaustiveness check in haskell?). だから予想外に null や undefined が返ってきて runtime error に成ることがない。なぜなら 予想の範囲 だからだガハハハハ。

• パターンマッチ: in function definition, case, guard with pipe(|).

  • fib 0 = 0 は "fib 0(の場合)は0に等しい(=値0に置き換えられる)"と言っている。
  • fib 1 = 1 は "fib 1(の場合)は1に等しい(=値1に置き換えられる)"と言っている。
  • fib n = fib (n-1) + fib (n-2): fib nは fib (n-1)の計算結果とfib (n-2)の計算結果を足し合わせたもの、と言っている。定義は fib 自体を含むので再帰呼び出しになる(fib n は再帰を定義、再帰を使って表現(=express)されている)。n は減っていくので、最終的に fib 0 or fib 1にぶち当たりstopするので安心してください。止まりますよ。

• 型コンストラクタ
  → 型を作る関数。data Foo = FooConstructor Int と Foo 型を定義した時の FooConstructor は Foo 型をつくる(construct)関数(FooConstructor :: Int -> Foo)。Int を渡すと、Foo 型が返ってくる。

• 型クラス(type class): → class は種、グループ →型種 → Int, Float は Num Type class のメンバ。Type class のメンバには制約が課せられる。Num は (+) 関数実装しろ、とか。set of types which share some characteristics. 型の集合、グループ。同じ Type class に属する type は共通の特徴、制約を持つ。

型シグニチャ(type signature)の難しさ

Currying 理解するとしっくり来る。

カリー化の難しさ(currying, partial application)

• Haskell の全ての関数は引数を一つ取る関数. 複数引数を渡している様に見えるが、"引数渡す → 関数返る →引数渡す → 関数返る → 引数渡す → 値返る"
• 無名関数(anonymous function)
• 複数引数とる(ように見える)関数定義は、syntax sugar のおかげ
  • \s1 s2 s3 -> s1 ++ s2 ++ s3 is
  • \s1 -> (\s2 -> (\s3 -> s1 ++ s2 + s3)): using closure to bind passed args to env one by one?

ポイントフリー(Point free) 関数？？？

• f1 x = f2 x は f1 = f2と書けるよね？
• f1 x = f2 y x も、そう書くより f1 = f2 yと書いたほうが coolじゃない？→これが成り立つのは関数が全てcurryingされているから。f2にyのみ渡して返ってきた関数を f1にbind している。flip とか駆使すれば引数の渡す順番変えられるから、頑張れば色んな関数を pointfree に出来るよ → やりすぎるな。

関数合成(function composition)の難しさ

• (.) は逆パイプ(|). 左から右ではなく、右から左へ。

なぜ代入(assign)と言わずに、束縛(=bind) と言うのか？(Why bind instead of assign?)

値は変更不可(=immutable) だから。箱に値を入れる、箱の中身の入れ替えるアナロジーは不適切。変数という用語も変化しないので不適切？"名前に値を紐付ける"意図でbindと言う。
x = 1 という expression における、= は代入ではなく、"未来永劫 x は 1 です" という宣言、表明である。

セットアップの難しさ(stack, haskell-platform)

情報の少なさの難しさ

• Jsと比べてるだけ？Webプログラミングが少ない？向いてない？英語だと有用リソースいっぱいある気がする。
• どのライブラリを使えば良い？jump, haskell is easy

得意分野の向き不向きの難しさ

• XXX つくるのに向いている？ State of the Haskell ecosystem

データ構造の理解の難しさ

• Tree, Binary Tree(二分木), Linked リスト, 再帰データ構造(Recursive data structure)

アルゴリズムの難しさ

• quick-sort の例。quick-sort 理解してるか？

結合性(Associativity), 結合強度(Priority)の難しさ

• 左結合(left-associate):
  • function application は left-associate. f a b c is ((f a) b) c
• 右結合(right-associate)
  • 関数の型定義はright-associate. add:: Int -> Int -> Int -> Int is add:: Int -> (Int -> (Int -> Int))
• 強度(priority, strength)

------------------------- ここから下は雑多メモ(整理前)

関数定義におけるシンタックスシュガー

Haskell の 全て の関数は引数を一つしか取らない。
複数引数を取るように見える関数は、一つの引数を取り、関数を返す関数として表現される。(その関数は次の引数を受け取り、関数を返す)

以下は全て同じ関数。複数引数を受け取る関数の定義は単にシンタックスシュガーに過ぎない。

以下は全て同じ関数

• f = \x -> (\y -> (\z -> BODY)): 最もプリミティブな表現
• f = \x y z -> BODY: syntax sugar
• f x y z = BODY: syntax sugar =の右側の引数部分(x, y, z)を=の左側へ移動

-- f = \x -> (\y -> (\z -> BODY))
f1 = \x -> (\y -> (\z -> x ++ y ++ z))
-- f = \x y z -> BODY
f2 = \x y z -> x ++ y ++ z
-- f x y z = BODY
f3 x y z = x ++ y ++ z
main = do
  print ("f1 " ++ (f1 "a" "b" "c")) -- => "f1 abc"
  print ("f2 " ++ (f2 "a" "b" "c")) -- => "f2 abc"
  print ("f3 " ++ (f3 "a" "b" "c")) -- => "f3 abc"

上述の通り、全ての関数は１つのみの引数をとるが、tuple を使って、複数引き数の関数をエミュレートすることは可能

Parametric polymorphism

パラメタリック・ポリモーフィズム
パラメタ多相
→ 型はパラメタによって特定される(決まる)
→ 型がパラメタ化されている(型をパラメタ(引き数)によって与える)

Type class constrains(型クラスに対する制約)

instance (Listable a, Listable b) => Listable (a,b) where
  toList (x,y) = toList x ++ toList y

色々な言い方をしてみる。

• a が Listable かつ、b が Listable である限りにおいて、type (a, b) は Listable
• if Listable a and Listable b then (a, b) is Listable else (a, b) isnot Listable
• Listable (a, b) を満たすには、Listable a, Listable b を同時に満たさなければならない。

遅延評価戦略の関数型プログラミングを実現するために、関数の参照透明性が必要だった。

cis194 spring 13 chapter6 laziness の抜粋

As we have seen, lazy evaluation makes it hard to reason about when things will be evaluated; hence including side effects in a lazy language would be extremely unintuitive. Historically, this is the reason Haskell is pure: initially, the designers of Haskell wanted to make a lazy functional language, and quickly realized it would be impossible unless it also disallowed side effects.

[翻訳]
これまで見てきたように、遅延評価は、"いつ評価が行われるのか？"を特定するのを難しくさせる。遅延評価のプログラミング言語に、副作用を混ぜ込むと、とてつもなく分かり難くなる。歴史的には、これが Haskell が純粋な理由なのだ。まず、Haskell のデザイナー(言語設計者)は遅延評価戦略の、関数型プログラミング言語を作りたかった。そしてすぐ気づいた。副作用を禁じない限り、不可能だということに。

雑感

なぜだろう？？？それはこの引用部の上の部分で実例がある。
関数 f が f (release_monkeys(), increment_counter())の様に呼ばれるとする。
正格評価戦略の言語では、release_monkeys() が評価された後、increment_counter() が評価される。increment_counter は release_monkeys がもたらす副作用に依存しているかもしれないから、この順序が逆になったり、場合によっては呼ばれなかったりすると非常にまずい事になる。
一方、遅延評価戦略の言語では、f に渡された引き数は、未評価の式(unevaluated expression)として保持され、値が必要になった時に初めて評価される。
例えば以下の関数では引き数 y は無視されるので、f 1 (2^111) の様に呼び出した時、2^111 は評価されず単に捨てられる。

f x y = x

Haskell の関数が pure ではなく、副作用をもたらすものだったらどうだろうか？
引き数が評価されたりされなかったり、何時評価されるかのタイミングも予想できない(unpredictable) のに、各関数が副作用をもつとしたら、、、頭がおかしくなっちゃうかもしれん。どんな動きになるのか誰も説明、推測、特定できない(cannot reason about computational consequence)。誰もそんな言語使いたくないよね？？

だから、遅延評価を実現するには、関数が純粋(=副作用を持たない。参照透明)である事が必要だった。遅延評価と関数の純粋性はセット。