Haskell： foldrの使用について

質問

例えば、filterの定義として、

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

というのがありますが、foldrを使用すると、

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x xs -> if p x then x : xs else xs) []

として、引数を一個減らして書いた定義ではありますが、
２つとも同じ意味です。

ここで、ふと思ったのですが、ふたつめのfoldrを使用した場合での定義
として、xsとxはどこで、「xsとxはこの部分である」と指定されているでしょうか。例えば、

filter (+) [1,2,3]

とすれば、xは1で、xsは[2,3]というのは人間から見てわかりますが、
コンピュータとしてはどう理解しているのでしょうか。

説明がわかりにくいかもしれませんが、
よろしくお願いします。

回答No.2

qoopty · ベストアンサー

No1の続きです。

何が問題で何を勘違いしているのかの方向性が分ったのできちんと回答します。

まず前提として
一番目に
質問のxとxsの間には":"が付いていないので、
xがリストの先頭要素xsが先頭要素を取り除いたリストではありません。
今回は、無名関数の第一引数と第二引数の意味しかありません。
ただし、型推論で推論された型を考えるとxsはリストでxはリストの要素という型になります。
二番目に
foldr関数について自分で使えるぐらい十分に知っておいてください。

filter (>2) [1,2,3]
を例にすると

filter (>2) [1,2,3]
⇒foldr (\x xs -> if (>2) x then x : xs else xs) [] [1,2,3]
無名関数(\x xs -> if (>2) x then x : xs else xs)は長いのでとりあえずfとします。
f :: a -> [a] -> [a]
なので
fは二つ引数を持ち、一番目が任意の型で二番目が一番目の型のリスト
fの戻り値の型は二番目の型と同じということが分ります。
ここ重要です。
fの一番目の引数が質問のxで二番目の引数がxsです。
No1にもあげたとおりこれが質問の回答です。
それ以上でもそれ以下でもないんですがさらに具体的にしないと分からないと思うので、
さらに計算を続けて、

foldr (\x xs -> if (>2) x then x : xs else xs) [] [1,2,3]
⇒foldr f [] [1,2,3]
foldrの定義にしてがって
⇒1 `f` (2 `f` (3 `f` []))
`f`の意味を知らないかもしれないので、`を使わない形に変換する
⇒f 1 (f 2 (f 3 []))

便宜上外側のfからf1 f2 f3する。

質問のx とxsに当てはめると
f1の場合
x は1
xs は(f 2 (f 3 []))

f2の場合
x は2
xs は(f 3 [])

f3の場合
x は3
xs は[]
となります。

お礼

foldrの定義自体は知っていました。ただ、xが値、xsをリストであることを
どうやってコンピュータは理解していたのであろうと考えていました。
型推論なんですね。

無名関数の、
if (>2) x then x : xs else xs
によって、推論されていたということだとわかりました。
ありがとうございました。

回答No.1

qoopty

例に挙げていたこれ
>filter (+) [1,2,3]
はコンパイルが通らないのでなんかのミスと思います。
filter (>2) [1,2,3]
とかの間違いかな。

また、コンピュータの理解の意味が分らないので勝手に質問を解釈すると

質問の意図は
>filter p = foldr (\x xs -> if p x then x : xs else xs) []
の
x とxs って何のことか教えてくださいということでいいでしょうか？

結論だけ答えると、
foldr の第一引数の一番目の引数と２番目の引数を示しています。

これ以上書くと質問の意図とずれた時が無駄なので、今回はここでやめておきます。

補足

＞filter (>2) [1,2,3]
すみません、関数の勘違いで、上記の場合と考えていただけたら良いです。

x,xsはそれぞれリストの先頭要素、xsは先頭要素を取り除いたリストであること
は理解しています。
ただ、xやxsはコンピュータ的に見ると、適当に名前をつけた仮のものですよね。
xはリストでなくひとつの数でないといけないことや
xsは数でなくリストでないといけないことはどうしてわかるのでしょうか。