質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Haskell

Haskellは高い機能性をもった関数型プログラミング言語で、他の手続き型プログラミング言語では難しいとされている関数でも容易に行うことができます。強い静的型付け、遅延評価などに対応しています。

関数型プログラミング

関数型プログラミングとは、関数を用いて演算子を構築し、算出し、コンピュータプログラムを構成する枠組みです。

Q&A

解決済

1回答

238閲覧

ラムダ計算(Lambda calculus)につきまして

omiteratail

総合スコア19

Haskell

Haskellは高い機能性をもった関数型プログラミング言語で、他の手続き型プログラミング言語では難しいとされている関数でも容易に行うことができます。強い静的型付け、遅延評価などに対応しています。

関数型プログラミング

関数型プログラミングとは、関数を用いて演算子を構築し、算出し、コンピュータプログラムを構成する枠組みです。

0グッド

1クリップ

投稿2018/03/08 06:13

閲覧ありがとうございます。
今回投稿させていただいたのは、ラムダ計算についての理解がなかなかできないためです。

現在、関数型プログラミングを学ぶにあたってコンピュータのパラダイムから理解しようと、関数型プログラミングの第一歩であるラムダ計算に取り組んでいるのですが、早速つまづいてしまっています。

ラムダ計算を解くのにあたって重要な、α-conversion,β-reduction,η-conversionがあるということを学んだのですが(https://wiki.haskell.org/Lambda_calculus)、いくら例題をやってもいまいち使い方がつかめません。
例えば、以下のような問題です。

(λf.λx.f(f x))(λy.y+1)2

これは

β → (λx.(λy.y+1)((λy.y+1) x))) 2
β → (λx.(λy.y+1)(x+1))2
β → (λy.y+1)(2+1)
β → (2+1+1)

となります。これは正しいことはわかるのですが、なぜ、λf.に対して(λy.y+1)2ではなく(λy.y+1)だけをβ-reductionしているのかがわかりません。

そして、もしこの同じ問題をこのように解いたら、(最初に(λy.y+1)2をβ-reductionしたら、)

β → (λf.λx.f(f x))(2+1)
β → (λx.(2+1)((2+1) x))

このように明らかに間違えてしまいます。また、(λf.に対して(λy.y+1)2をβ-redecutionしたら、)

β → (λx.((λy.y+1) 2)(((λy.y+1) 2) x)))
β → (λx.(2+1)((2+1) x))

これも結果としては同じ間違いになっています。
ただ、両方ともどこで間違えているのかが正直全くわかりません。

この単純なところにかなり時間をかけてしまっているので、お手数をおかけしますがぜひよろしくお願いいたします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

なぜ、λf.に対して(λy.y+1)2ではなく(λy.y+1)だけをβ-reductionしているのかがわかりません。

(λf.λx.f(f x))(λy.y+1)2 には引き数が二つあります。一つ目が (λy.y+1) で二つ目が 2 です。

カリー化(currying)という変換ルールがあって、ラムダ式は引数を一つだけとります。λf は一つ目の引数 (λy.y+1) をとりますので、それだけを使ってベータ簡約すると、新しいラムダ式 (λx.(λy.y+1)(x+1)) が得られます。その新しい式では引数 2 を使ってベータ簡約しますので、最終的な式 (2+1+1) となります。

投稿2018/03/08 07:03

tatsuya6502

総合スコア2035

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

omiteratail

2018/03/08 07:27

tatsuya6502さん ご回答ありがとうございます、ずっとあったモヤモヤがかなりなくなったような気がします! (λf.λx.f(f x))が引数を2個取っていること、そして、ラムダ式は一個しか引数を取らない(curry)ということがわかりましたが、ただ、明確にするために一つだけ伺わせていただきたいです。例えば、 (λx.x y)(λa. a b) c 上記の式は一番左(λx.x y)が引数を1つしか取らないので、 β→(λx.x y)(c b) β→(c b) y → c b y または β→((λa. a b) c )y β→ (c b) y → c b y になる。(括弧の位置あっていますかね。。。) つまり、先ほどの質問の例ではそもそも(λf.λx.f(f x))の引数が2個のため右側(引数)の(λy.y+1) 2を先に計算するなんていう愚行(引数同士で計算)はできなかったが、今回は引数が1個なので、右側の(λa. a b)cを先に計算しても順番は関係ない。 ということでしょうか。 よろしくお願いいたします。
tatsuya6502

2018/03/08 07:45

あまり自信がないのですが、引き数が一つの時は、おっしゃる通り、順番は関係なかったと思います。いま見つけたこちらのページの「簡約」の所でも、そういう説明がされていました。 https://tarao.hatenablog.com/entry/20100208/1265605429
kakkun61

2018/03/08 07:48

(λx.x y)(λa. a b) c は ``` (λx.x y)(λa. a b) c = ((λa. a b) y) c = (y b) c = y b c ``` になるように思います。
tatsuya6502

2018/03/08 07:53

ああ、ご指摘ありがとうございます。私、間違えましたね。上で紹介したページでも「適用は左に結合し」と書かれていました。
omiteratail

2018/03/08 10:06

tatsuya6502さん リンクありがとうございます、そちらも一読してより理解を深めたいと思います。 大変助かりました、ありがとうございました!
omiteratail

2018/03/08 10:07

kakkun61さん ご指摘ありがとうございます。 私自身、適用をright-associativeだと勘違いしていたので、なおさら理解できました。 ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問