Clojure(1.3-1.4)のリスト/ベクタ(シーケンス)操作関数一覧

　何回使っても、気づいたら、忘れてしまうリスト/ベクタ系関数について調べたメモ。
Clojureでは、プログラムの大半はシーケンス操作になる可能性が高い為か、Clojureのシーケンス操作関数は、かなり充実していますが、たくさんありすぎて、使いこなせているか不安になります。オフィシャルのリファレンスに関数一覧が乗っていますが、リストとベクタの操作に限定してまとめました。
　ちなみに、リスト, ベクタ ⊆ シーケンスです。
zip(木構造), hashmap等は扱いません。

以下の9種類に大別。62個について調べました(まだあるかもしれません)。

1. 生成系(7)
2. cons系(3)
3. getter系(21)
4. observer系(8)
5. map系(6)
6. reduce系(2)
7. filter系(3)
8. リスト再構築(8)
9. リスト並び替え(4)

生成系

　遅延シーケンスを生成する。

list

　引数列のリストを返す。

(list 1 2 3) => (1 2 3)

(list "a" 2 [72 71] 'u) => ("a" 2 [72 71] u)

range

 自然数列のリストを生成する。

(range) => (0 1 2 3 ...　無限に続く。

(range 1 10) => (0 1 2 3 4 5 6 7 8 9 10)

repeat

　引数に与えられた要素を繰り返したリストを返す。

(repeat "val") => ("val" "val" "val" "val" ... ... 無限に続く。

(repeat 4 "val") => ("val" "val" "val" "val")

repeatedly

　引数に与えられた関数の実行結果を要素とするリストです。repeatが動詞でrepeatedlyが副詞なのは、それぞれ名詞と動詞を引数に持つからですか。

(repeatedly #(rand-int 10)) => (4 5 8 8 6 2 0 7 7 2 ... ... 無限に続く。

cycle

　引数に与えられたリストの要素を繰り返したリストを返す。

(repeat [1 2 3]) => (1 2 3 1 2 3 ... ... 無限に続く。

iterate

　n番目の要素が、xに対してn回fを適用したものであるリストを返す。x, f(x), f(f(x)) ... のリストを返す。

(iterate dec 0) => (0 -1 -2 -3 -4 -5 -6 ... ... 無限に続く。

for

　リスト内包表記(List Comprehension)です。:letは、内包表記内での変数定義、:whenはフィルターです。表記内で与えられたリストから別のリストを生成します。PythonやHaskellのList Comprehensionとくらべて、理解しづらいです。

(for [x [1 2 3] y '(a b c)] [x y]) => ([1 a] [1 b] [1 c] [2 a] [2 b] [2 c] [3 a] [3 b] [3 c])

(for [x [1 2 3] :let [y (* x x)]] y) => (1 4 9)

(for [x [1 2 3 4 5] :when (even? x)] x) => (2 4)

seq

　一部のデータ型をリストへキャストする。キャストできないものはエラー。seqは、遅延シーケンスではなく、通常のシーケンスを生成する。

(seq '()) => nil

(seq "abc") => (\a \b \c)

cons系

　リストを構築する。

cons

　先頭に与えられた要素を加えたリストを返す。

(cons 'a '(b c d)) => (a b c d)

(cons 1 [2 3 4]) => (1 2 3 4)

(cons [1] [2 3]) => ([1] 2 3)

conj

　シーケンスに、要素を加えたものを返す。consとの違いは、consが必ずリストの先頭に加えられるのに対して、conjは、リストやベクタによって新たな要素が加えられる位置が変わってくるという点。一番追加しやすい場所に追加されるようです。要素の順番に依存しないシーケンスを扱う時に使います。

(conj 1 [2 3 4]) => [2 3 4 1]

(conj 1 '(2 3 4)) => (1 2 3 4)

concat

　複数のシーケンスをすべて結合する。

(concat [1 2 3] [2 2 3]) => [1 2 3 2 2 3]

(concat [1] [2] [3]) => (1 2 3)

getter系

　シーケンスから要素を取り出す。

first/ffirst

 シーケンスの先頭の要素を取り出す。古いLisp系言語のcarに相当します。/シーケンスの先頭の先頭の要素を取り出す。古いLisp系言語のcaarに相当します。

(first [3 2 1]) => 3
(ffirst [[1 2 3] [2 2 3]]) => 1

second

　シーケンスの二番目の要素を取り出す。古いLisp系言語のcadrに相当します。

(second [1 2 3]) => 2
(second [1]) => nil

nth

　シーケンスのn番目の要素を取り出す。インデックスは0から始まります。

(nth [1 2 3] 2) => 3
(nth [1 2 3] 0) => 1

rand-nth

　リストからランダムに要素を選んで取り出す。

(rand-nth [:a :b :c]) => :a
(rand-nth [:a :b :c]) => :b

rest/ntresth

　リストの先頭の要素を除いた残りの要素を取り出す。古いLisp系言語のcdrに相当します。/リストのn番目の要素?

(rest [1 2 3]) => [2 3]
(rest []) => []

next/nthnext

　リストの先頭の要素を除いた残りの要素を取り出す。restとの違いは、リストの末尾に到達した時に、[]を返すのがrest、nilを返すのがnext。/リストのn番目までの要素を除いた残りの要素を取り出す。
(next [1 2 3 4]) => (2 3 4)
(next [1]) => nil
(nthnext [[1 2] [3 4 5] [6 7 8]] 2) => ([6 7 8])

fnext/nnext

　先頭を除いたリストの先頭の要素を取り出す。(fnext x) = (first (next x))/リストの先頭2つの要素を除いた残りの要素を取り出す。(nnext x) = (next (next x))
(fnext [[1 2] [3 4 5]]) => [3 4 5]
(nnext [[1 2] [3 4 5] [6 7 8]]) => ([6 7 8])

take/take-while/take-last

　先頭からn個要素を取り出す。/先頭から与えられた条件を満たさない要素になるまで取り出す。/末尾からn個要素を取り出す。

(take 3 (range 1 10)) => (1 2 3)
(take-while odd? [1 3 5 6 7 8]) => (1 3 5)
(take-last 3 (range 1 10)) => (7 8 9)

drop/drop-while/drop-last

　先頭からn個要素を省く。/先頭から与えられた条件を満たさない要素になるまで省く。/末尾からn個要素を省く。

(drop 3 (range 1 10)) => (4 5 6 7 8 9)
(drop-while odd? [1 3 5 6 7 8]) => (6 7 8)
(drop-last 3 (range 1 10)) => (1 2 3 4 5 6)

last/butlast

　最後の値を取り出す。/最後の値を取り除いたリストを返す。

(last [1 2 3 4 5]) => 5
(butlast [1 2 3 4 5]) => (1 2 3 4)

when-first

　リストの先頭の値をバインドする。
(when-first [a [1 2 3]] (* a 5)) => 5

observer系

リストから情報を取り出す。

count

　リストの要素を数える。lengthではなく、countとなっていて、「長さを計算する」という処理であることを明示的に表している点が良いですね。
(count [1 2 3]) => 3
(count '()) => 0

empty?

　リスト/ベクタが空かどうかを判定する。空でtrue。そうでなければfalse。Schemeにnull?という空リストの判定をする関数があって、Clojureにもnil?という似たような関数がありますが、nil?ではカラリストの判定はできない場合があるので注意。
(empty? []) => true
(empty? (range 1 10)) => false

empty/not-empty

　空のシーケンスを空にして返す。/リストがからであればnilを返す。それ以外の場合は、そのリスト自身を返す。
(empty [1 2 3]) => []
(not-empty [1 2 3]) => [1 2 3]
(not-empty []) => nil

some/not-any?

　与えられた要素を満たす要素が存在するか判定する。/与えられた条件を満たさない要素が存在しないか判定する。　
(some even? [1 1 2 3]) => true
(not-any? even? [1 1 2 3]) => false

every?/not-every?

　すべての要素が条件を満たすか判定する。/条件を満たさない要素が存在するか判定する。
(every? odd? [1 1 1 3]) => true
(not-every? odd? [1 1 2 3]) => true

map系

　mapは、[a, b, c, d, .......]に対して、[f(a), f(b), f(c), f(d), ......]を求めるような関数。

map

　与えられたリストに対して、それぞれの要素に与えられた関数を適用したリストを返す。
(map inc (range 1 10)) => (2 3 4 5 6 7 8 9 10)
(map even? (range 1 10)) => (false true false true false true false true false)

pmap

　 mapの処理を並列(parallel)に実行する。上手に使わないと逆に遅くなることもあります。
user=> (defn fibo[n] (if (< n 2) 1 (+ (fibo (- n 1)) (fibo (- n 2)))))
#'user/fibo
user=> (time (take 10 (doall (map fibo (range 1 30)))))
"Elapsed time: 363.431486 msecs"
(1 2 3 5 8 13 21 34 55 89)
user=> (time (take 10 (doall (pmap fibo (range 1 30)))))
"Elapsed time: 257.508792 msecs"
(1 2 3 5 8 13 21 34 55 89)
user=> (time (take 10 (doall (map inc (range 1 30)))))
"Elapsed time: 0.120742 msecs"
(2 3 4 5 6 7 8 9 10 11)
user=> (time (take 10 (doall (pmap inc (range 1 30)))))
"Elapsed time: 53.420469 msecs"
(2 3 4 5 6 7 8 9 10 11)

mapcat

　引数のリストをconcatしたものに対してmapした結果を返す。

(mapcat sort [[4 5 1 6] [7 8 3 2] [10 9]]) => (1 4 5 6 2 3 7 8 9 10)
(mapcat reverse [[1 2 3] [7 8 9] [4 5 6]]) => (3 2 1 9 8 7 6 5 4)

map-indexed

　mapした要素にインデックスを付ける。

(map-indexed list (range 1 10)) => ((0 1) (1 2) (2 3) (3 4) (4 5) (5 6) (6 7) (7 8) (8 9))

(map-indexed + (reverse (range 1 10))) => (9 9 9 9 9 9 9 9 9)

keep

　mapとほぼ同じ関数ですが、mapが返すリスト列は、nilを含むのに対して、keepは、nilを含まないリストを返します。つまり、 keep .... = (filter not-nil (map ....)のような感じでnil要素をフィルタリングします。
(keep next [[1] [] [2 3] [4 5 6] [] [7 8]]) => ((3) (5 6) (8))

keep-indexed

　keepした要素にインデックスを付ける。
(keep-indexed #(nnext (concat [%1] %2)) [[] [3 4] [] [] [5 6 7]]) => ((4) (6 7))

reduce系

畳み込み処理をします。

reduce

　二項演算をする関数とリストを引数にとり、畳み込み処理をします。
(reduce + (range 1 11)) => 55
(reduce * (range 1 10)) => 362880

reductions

　n回目の畳み込み処理の結果からなるリストを返す。

(reductions + (range 1 11)) => (1 3 6 10 15 21 28 36 45 55)
(reductions * (range 1 11)) => (1 2 6 24 120 720 5040 40320 362880 3628800)

filter系

リストから特定の要素を取り除きます。

filter

　与えられた関数がtrueを返すもののみからなるリストを返す。関数でフィルターします。
(filter even? (range 1 10)) => (2 4 6 8)
(filter next [[2 3] [] [2] [3 4]]) => ([2 3] [3 4])

remove

　与えられた関数がtrueを返すものを取り除く。filterの反対です。
(remove even? (range 1 10)) => (1 3 5 7 9)

(remove next [[2 3] [] [2] [3 4]]) => ([] [2])

distinct

　重複する要素を取り除く。
(distinct [1 2 3 2 3 4 4 5]) => (1 2 3 4 5)
(distinct (take 100 (cycle [1 2 3]))) => (1 2 3)

再構築

シーケンスの要素を分割したり結合したりする。

flatten

　ネストしたシーケンスを平な線形のリストにする。複雑にネストしていても、再帰的に取り出します。
(flatten [[1 2 3] [4 5 6]]) => (1 2 3 4 5 6)
(flatten [[1 2 [3 [4 5 [6]] 7] 8] 9]) => (1 2 3 4 5 6 7 8 9)

partition

　リストをn個づつ分割する。割り切れずに、余った要素は切り捨てる。
(partition 4 (range 15)) => ((0 1 2 3) (4 5 6 7) (8 9 10 11))
(partition 4 3 (range 15)) => ((0 1 2 3) (3 4 5 6) (6 7 8 9) (9 10 11 12))
(partition 4 3 ["pad" "pad"] (range 15)) => ((0 1 2 3) (3 4 5 6) (6 7 8 9) (9 10 11 12) (12 13 14 "pad"))

partition-all/partition-by

　すべて分割する。余った要素は最後に付加する。/条件がtrueとfalseが変わる瞬間で分割する。

(partition-all 4 (range 1 10)) => ((1 2 3 4) (5 6 7 8) (9))
(partition-by odd? [1 1 2 4 5 3 4 4 2]) => ((1 1) (2 4) (5 3) (4 4 2))

split-at/split-with

　n番目で分割する。/条件がfalseになったところで分割する。
(split-at 3 (range 1 10)) =>[(1 2 3) (4 5 6 7 8 9)]
(split-with #(< % 4) (range 1 10)) => [(1 2 3) (4 5 6 7 8 9)]

interleave/interpose

　2つのリストを折り込む。/リストのそれぞれの要素の間に要素を与える。

(interleave (range 1 10) (range 21 30)) => (1 21 2 22 3 23 4 24 5 25 6 26 7 27 8 28 9 29)
(interpose 0 (range 10)) => (0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9)

並び替え系

　シーケンスの要素を並び替える。

reverse

　シーケンスの順序を反転する。

(reverse (range 1 10)) => (9 8 7 6 5 4 3 2 1)
(reverse [1 3 2 4 6 5 7 9 8]) => (8 9 7 5 6 4 2 3 1)

shuffle

　シーケンスをシャッフルする。

(shuffle (range 15)) => [6 7 13 11 5 12 3 1 8 4 10 9 2 14 0]

sort

　シーケンスを並び替える。要素を評価する関数を指定できる。
(sort (shuffle (range 1 10))) => (1 2 3 4 5 6 7 8 9)
(sort > (shuffle (range 1 10))) => (9 8 7 6 5 4 3 2 1)

sort-by

　シーケンスを並び替える。要素の並び替えにつかう値を指定できる。
(sort-by first (map list (shuffle (range 1 10)) (shuffle (range 1 10))))
=> ((1 3) (2 4) (3 9) (4 7) (5 1) (6 2) (7 6) (8 8) (9 5))
(sort-by second (map list (shuffle (range 1 10)) (shuffle (range 1 10))))
=> ((1 1) (5 2) (3 3) (4 4) (9 5) (2 6) (8 7) (7 8) (6 9))

　一通り調べてみた結果、多くを使いこなしてないことが判明しました。orz ...

　(使ってなかったけど)これから使いそうなものから、どのように使うかよくわからないものまで、たくさんあります。maxやminのような引数の中から最大値、最小値を求めるような関数もリスト操作関数に近いですが、厳密にはリストを扱っているわけではないので、今回は省きました。全部網羅できると、スッキリします。

HaskellのパーサコンビネータParsecを使ってみた

※注意: この記事は古い記事です。import周り等、最新versionのparsecライブラリにし追随ていません。一応、2013年(7月10日)当時はこうだったという形で記録として残してあります。(追記: 2017/7/17)

Haskellの勉強がてらParsecを使ってみました。

　コードを眺めただけだと、再帰的下向き構文解析を手で書いているのとあまり変わらないように見えますが、実際に書いてみると非常に簡単ですね。モナド使ってるっていうのが、気に入りませんが。構文解析のコードしか書いてないのに、字句解析器もやってくれます。

　次の文法をS式に書き直すパーサを書いてみました。中置記法を前置記法に変換します。LLパーサなので、左再帰しないように気を使います。
Infix  → Exp
Exp    → Term "+" Exp | Term "-" Exp | Term
Term   → Factor "*" Term | Factor "/" Term | Factor
Factor → ident | number | "(" Exp ")"

さらに、これを変換して、
Infix  → Exp
Exp    → Term Exp*
Exp*   → "+" Term Exp* | "-" Term Exp* | ε
Term   → Factor Term*
Term*  → "*" Factor Term* | "/" Factor Term* | ε
Factor → ident | number | "(" Exp ")"

を構文解析させます。変換したのは、演算子の適用順序を正しくするためです。εは、空を表します。

以下が、コードと実行結果。実行環境はghci 7.4.2。

　Parsecは、ひたすら読めるまで読み続けて、パターンにマッチしない文字列が来たら、エラーを出さずに、マッチした部分の文字列の実行結果を返して、終了するようです。文字列を最後まで読み込み、エラーを出す為には、文法にEOF記号を混ぜる必要がありそうですね。Infix → Exp '$'、みたいな書き方にすればよかったってことでしょうか。

参考文献

• Parsec練習問題 : http://guppy.eng.kagawa-u.ac.jp/Seminar/Haskell/parsec.html
• tinyCの文法をParsecを使って書くというお話。大変勉強になりました。
• [Haskell]Parsecというパーサーライブラリで電卓を作る簡単な方法 : http://bugrammer.g.hatena.ne.jp/nisemono_san/20111117/1321555610
• parsec-3.0.1: Monadic parser combinators ,Text.Parsec : http://hackage.haskell.org/packages/archive/parsec/3.0.1/doc/html/Text-Parsec.html
• オフィシャルのドキュメント

Clojureで、Yahoo!の形態素解析APIを使う

・「日本の全エンジニアに捧ぐ！現在公開されているAPI一覧【2013年版】」

という記事を見つけたら、
Yahoo!の形態素解析APIを使ってたのを思い出したので、そのメモ。

Clojureから、Yahoo!のこのAPIを使って、任意の文字列を形態素解析できるようにします。

日本語の形態素解析
・Yahoo!日本語形態素解析API

テキストデータと言えば、青空文庫
・「青空文庫/夏目漱石/それから」

Clojure側ではとりあえず、

1. httpのリクエストを送リ、データを受け取る。
2. データをClojureの内部形式(ハッシュマップ、そして、リスト)に戻す。

という2つの処理が出来ればOK。簡単です。

リクエストは、Clojureのhttp-agentというラッパーを使います。

参考 : 逆引きClojure : 特定のURLからドキュメントを抽出する

　Yahoo!日本語形態素解析APIは、XML形式でデータを返してくれます。

　今回は、そのデータを一旦、ローカルに保存して、ClojureのXMLパーサを使って、データをハッシュマップにマッピングします。そこから、必要なデータだけ抜き出して、単語列にします。

以下が実行結果とコード。

user=> (load-file "use-yjma-api.clj")
#'user/tokenizer
user=> (tokenizer kana "誰か慌ただしく門前を馳けて行く足音がした時、代助の頭の中には、大きな俎下駄が空から、ぶら下つてゐた。けれども、その俎下駄は、足音の遠退くに従つて、すうと頭から抜して消えて仕舞つた。さうして眼が覚めた。")
("だれ" "か" "あわただしく" "もんぜん" "を" "はせ" "け" "て" "いく" "あしおと" "が" "し" "た" "とき" "、" "しろ" "たすけ" "の" "あたま" "の" "なか" "に" "は" "、" "おおきな" "まないた" "げた" "が" "そら" "から" "、" "ぶらさがり" "つて" "ゐ" "た" "。" "けれども" "、" "その" "まないた" "げた" "は" "、" "あしおと" "の" "とおのく" "に" "じゅう" "つて" "、" "すう" "と" "あたま" "から" "ぬき" "し" "て" "きえ" "て" "しまい" "つた" "。" "さ" "う" "し" "て" "め" "が" "さめ" "た" "。")
user=> (tokenizer kanji "誰か慌ただしく門前を馳けて行く足音がした時、代助の頭の中には、大きな俎下駄が空から、ぶら下つてゐた。けれども、その俎下駄は、足音の遠退くに従つて、すうと頭から抜して消えて仕舞つた。さうして眼が覚めた。")
("誰" "か" "慌ただしく" "門前" "を" "馳" "け" "て" "行く" "足音" "が" "し" "た" "時" "、" "代" "助" "の" "頭" "の" "中" "に" "は" "、" "大きな" "俎" "下駄" "が" "空" "から" "、" "ぶら下" "つて" "ゐ" "た" "。" "けれども" "、" "その" "俎" "下駄" "は" "、" "足音" "の" "遠退く" "に" "従" "つて" "、" "すう" "と" "頭" "から" "抜" "し" "て" "消え" "て" "仕舞" "つた" "。" "さ" "う" "し" "て" "眼" "が" "覚め" "た" "。")

• app-idには、yahooから与えられたアプリケーションIDを記述します。
• (平)仮名と漢字を選べます。(XMLデータには、両方の結果があります)
• リクエストの日本語のエンコードには、java.net.URLEncoder/encode
• take-tokensは、ネストしたハッシュマップから、単語の列を生成する。

こんな感じで、テキストデータが単語単位に分割できました。

trampolineでバックトラックパーサを作る

shift/resetと、(fnで囲った)closure/trampolineは、なんとなく似てます。

trampoline

trampolineは、末尾再帰をエミュレートする為の関数です。

clojureは、末尾再帰ができないので、loop-recur特殊形式で
ループを記述するのですが、これは、ほとんどJavaやCのwhile文か、
それ以下の表現力しかありません。
なので、相互再帰とか、複雑な末尾再帰は表現できません。

その代替手段としてtrampolineという関数があります。
以下のように使います。

1. まず、普通に末尾呼出形式で関数型言語風のプログラムを書きます。
2. 次に、その末尾呼出を全部無名関数で囲ってクロージャにします。
3. トランポリン関数の上で、相互再帰の関数を呼び出します。

トランポリンは、与えられた関数とその引数を起動して、関数を実行します。
関数の実行結果として、

1. クロージャが戻ってきたら、(それは、末尾呼出なので)そのクロージャを再び実行。
2. それ以外の値が戻ってきたら、終了。

これで、スタックを消費せずに、末尾再帰が、特に相互再帰のような
複雑な末尾再帰も実現できるという事で、非常にめでたいのですが。

この末尾呼出で戻ってきたクロージャってもしかして、
trampolineが終了するまでの残りの計算　 ... .... (限定)継続!?

というわけで、概念的に、というか理論的にどうなのかはわかりませんが、
直感的には、かなり似たものだという印象です。

trampolineがresetに対応していて、
「shiftが呼ぶ限定継続」が、「末尾再帰で送り出されるレキシカルクロージャ」に対応している、
と、考えます。

その証拠というか、例として、shift/resetの得意なバックトラックを
trampolineを使って簡単に書くことができます。
その例として、パーサ(構文解析器)を書きました。

バックトラックパーサ

バックトラックとは、その名の通り(?)後戻りをする機構のことです。構文解析とは、結局のところ、文法法則を(終端)記号列に対してうまく当てはまるかどうかを試すアルゴリズムに過ぎません。なので、当てはまりそうだったら、適当に当てはめてみて、ダメだったら、元に戻すというやり方でもOKなのです。(もちろん、それ相応の計算量がかかりますが。)
なので、適当にパターンマッチを繰り返して、辻褄があわなくなったらその時点まで戻るようなパーサを書くことができます。それがバックトラックパーサです。
で、今回のこの末尾呼出のクロージャを限定継続に見立てて、パターンマッチに失敗したら、この限定継続もどきを呼び出すことでバックトラックを実現します。

次の文法をParseするプログラムにしました。

E → T '+' E
T → F '*' T
E → T
T → F
F → num

backtracparser.clj


実行結果と利用例は、こんな感じ。
ちゃんと構文解析しています。
parse-with-stack-traceで、バックトラックしていることも確認出来ます。

user=> (load-file "backtrackparser.clj")
#'user/parse-with-stack-trace
user=> (parse [[:num] [:+] [:num] [:*] [:num] [:$]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]
user=> (parse-with-stack-trace [[:num] [:+] [:num] [:*] [:num] [:$]])
[]
([:num])
([:F [:num]])
... ...
([:$] [:E [:T [:F [:num]]]] [:*] [:F [:num]] [:+] [:T [:F [:num]]])
back track !!
([:T :* [:T [:F [:num]]] [:F [:num]]] [:+] [:T [:F [:num]]])
([:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:+] [:T [:F [:num]]])
([:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
([:$] [:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]

うーん、gistとブログの色合いが微妙......

ラムダ計算のYの使い方と不動点コンビネータの違い

1.YCombinatorの使い方

ハスケルのYコンビネータ
Y　≡　(λg. (λx. g(x x)) (λx. g(x x)))

は以下のように簡約されていき、

β→  (λg. (λx. g(x x)) (λx. g(x x))) f

β→  (λx. f(x x)) (λx. f(x x)))

β→  f((λx. f(x x)) (λx. f(x x))))

β→  f(f((λx. f(x x)) (λx. f(x x)))))

で、
Y' ≡(λx. f(x x)) (λx. f(x x))
とすると、
Yf ≡ fY' ≡ ffY' ≡ fffY'
みたいな感じに増えていきます。

引数として与える関数fは、
f = λhy. if condition? then <終了時の処理など> else <再帰呼び出しなど>
のようにして書きます。

・この時、f = h(つまり、再帰呼び出し的な自分自身)だと考える。
・上のラムダ抽象の変数yは、ラムダ抽象が表す関数の引数だと考える。

再帰呼出風に書くとちゃんとループになるというわけです。

Yコンビネータは、Yf ≡ fY' ≡ ffY' ≡ fffY'みたいに増えてい来ます。
しかし、fが表すラムダ抽象は、引数をあたえられた時のβ簡約において、
hを展開させないようにすることで、fffY'のY'を切り捨てます。
結果、ループが止まります。

2.他の不動点コンビネータ

ちなみに、
A ≡(λxy. x y x) (λyx. y (x y x))

このコンビネータは、

β→  (λxy. x y x) (λyx. y (x y x)) f
β→  (λy. (λyx. y (x y x)) y (λyx. y (x y x))) f

β→  (λyx. y (x y x)) f (λyx. y (x y x))

β→  (λx. f (x f x)) (λyx. y (x y x))
β→  f ((λyx. y (x y x)) f (λyx. y (x y x)))
β→  f ((λx. f (x f x)) (λyx. y (x y x)))

β→  f (f ((λyx. y (x y x)) f (λyx. y (x y x))))

でやっぱり、

A' ≡(λyx. y (x y x)) f (λyx. y (x y x))
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

Θ ≡ (λxy. y(x x y)) (λxy. y(x x y))
これは、「チューリングの不動点コンビネータ」と呼ぶようです。

β→  (λxy. y(x x y)) (λxy. y(x x y)) f

β→  (λy. y((λxy. y(x x y)) (λxy. y(x x y)) y)) f
β→  f ((λxy. y(x x y)) (λxy. y(x x y)) f)
β→  f ((λy. y((λxy. y(x x y) (λxy. y(x x y) y)) f)

β→  f ( f((λxy. y(x x y) (λxy. y(x x y) f)

でやっぱり、

A' ≡((λxy. y(x x y)) (λxy. y(x x y)) f)
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

違いというか、簡約された結果だけ見ると、全部同じですね。
与えられたラムダ式fを内包して増加増幅していきます。