19

私は関数型言語について少し独学しています (現在 Haskell を使用しています)。私は、foldr に関してマップとフィルターを定義する必要がある Haskell ベースの割り当てに出くわしました。私の人生では、これをどのように行うかを完全には理解していません。

たとえば、次のようなマップ関数を定義すると:

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\x xs -> (f x):xs) [] xs

リストの最初の要素が常に無視される理由がわかりません。つまり：

map' (*2) [1,2,3,4]

[2,4,6,8] ではなく [4,6,8] になります。

同様に、私のフィルター関数:

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

次のように実行する場合:

filter' even [2,3,4,5,6]

[2,4,6] ではなく [4,6] になります。

なぜこれが当てはまるのでしょうか？また、期待される結果を得るには、これらの関数をどのように定義する必要がありますか? ラムダ式に何か問題があると思います...

4

8 に答える 8

51

コメントできればいいのですが、残念ながら、カルマが足りません。

他の答えはすべて良いものですが、最大の混乱はxとxsの使用に起因しているように思われます。

あなたがそれを書き直した場合

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\y ys -> (f y):ys) [] xs

xあなたはそれが右側にさえ言及されていないことをはっきりと見るでしょう、それでそれが解決策にあるかもしれない方法はありません。

乾杯

于 2011-04-20T08:24:51.823 に答える
21

最初の質問でfoldrは、空のリストのケースが既にあるため、独自のマップでケースを提供する必要はありません。

map' f = foldr (\x xs -> f x : xs) []

同じことが当てはまりますfilter'

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

ラムダ式に問題はありませんが、 and の定義に問題がありfilter'ますmap'。コンス ケース (x:xs) では、頭 ( ) を食べてxから、尾を に渡しfoldrます。関数は、foldr既に食べた最初の要素を見ることはできません。:)

また、次の点にも注意してください。

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

は次のものと同等 ( η-equivalent ) です。

filter' p xs = foldr (\x xs -> if p x then x : xs else xs) [] xs
于 2011-04-20T07:11:05.237 に答える
5

次のように、foldr と関数構成を使用してマップを定義します。

map :: (a -> b) -> [a] -> [b]
map f = foldr ((:).f) []

そしてフィルターの場合：

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

foldr または foldl を使用してリストに対して関数を定義する場合、リスト自体を渡す必要はないことに注意してください。ソリューションの問題は、リストの先頭を削除してから、リストにマップを適用することです。これが、結果が表示されたときにリストの先頭が欠落している理由です。

于 2012-09-03T17:52:36.790 に答える
3

定義では、 に対してパターン マッチングを行っていますx:xs。つまり、引数が[1,2,3,4]である場合、xは にバインドされ、残りのリスト: にバインドされます。1xs[2,3,4]

やってはいけないことは、単純に部品を捨てることですx:。次に、foldrリスト全体に取り組みます。

したがって、定義は次のようになります。

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f xs       = foldr (\x xs -> (f x):xs) [] xs

と

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p xs        = foldr (\x xs -> if p x then x:xs else xs ) [] xs
于 2011-04-20T07:10:10.197 に答える
3

別の考え方 - 次の再帰パターンが頻繁に使用されるため、foldr が存在します。

-- Example 1: Sum up numbers
summa :: Num a => [a] -> a
summa []     = 0
summa (x:xs) = x + suma xs

数値の積を取得したり、リストを逆にしたりすることは、構造的に前の再帰関数と非常によく似ています。

-- Example 2: Reverse numbers
reverso :: [a] -> [a]
reverso []      = []
reverso (x:xs)  = x `op` reverso xs
  where
    op = (\curr acc -> acc ++ [curr])

上記の例の構造は、最初の値と再帰呼び出しの間の演算子 (summa と reverso の場合) とともに、初期値 (summa と reverso の場合) のみが異なり0ます。したがって、上記の例の関数構造は、一般的に次のように見ることができます。[]+(\q qs -> qs ++ [q])

-- Generic function structure
foo :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
foo op init_val []      = init_val
foo op init_val (x:xs)  = x `op` foo op init_val xs

この「一般的な」foo が機能することを確認するために、foo を使用し、それに演算子、初期値、およびリスト自体を渡すことで、reverso を書き直すことができます。

-- Test: reverso using foo
foo (\curr acc -> acc ++ [curr]) [] [1,2,3,4]

foo により一般的な型シグネチャを与えて、他の問題でも機能するようにしましょう。

foo :: (a -> b -> b) -> b -> [a] -> b

さて、あなたの質問に戻ります - 次のようにフィルタを書くことができます:

-- Example 3: filter
filtero :: (a -> Bool) -> [a] -> [a]
filtero p []     = []
filtero p (x:xs) = x `filterLogic` (filtero p xs)
  where
     filterLogic = (\curr acc -> if (p curr) then curr:acc else acc)

これもsummaやreversoと非常によく似た構造を持っています。したがって、foo を使用して書き換えることができるはずです。リスト [1,2,3,4] から偶数をフィルタリングしたいとしましょう。次に、再び foo に演算子 (この場合はfilterLogic)、初期値、およびリスト自体を渡します。filterLogicこの例ではp、述語と呼ばれる関数を受け取ります。これは、呼び出し用に定義する必要があります。

let p = even in foo (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4]

Haskell の foo はfoldrと呼ばれます。そこで、foldr を使用してフィルターを書き直しました。

let p = even in foldr (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4]

したがって、filterは、これまで見てきたように、 foldrで記述できます。

-- Solution 1: filter using foldr
filtero' :: (a -> Bool) -> [a] -> [a]
filtero' p xs = foldr (\curr acc -> if (p curr) then curr:acc else acc) [] xs

mapに関しては、次のように書くこともできます

-- Example 4: map
mapo :: (a -> b) -> [a] -> [b]
mapo f []   = []
mapo f (x:xs) = x `op` (mapo f xs)
  where
    op = (\curr acc -> (f curr) : acc)

したがって、これはfolderrを使用して書き換えることができます。たとえば、リスト内のすべての数値に 2 を掛けるには、次のようにします。

let f = (* 2) in foldr (\curr acc -> (f curr) : acc) [] [1,2,3,4]

したがって、これまで見てきたようにmapはfolderrで書くことができます:

-- Solution 2: map using foldr
mapo' :: (a -> b) -> [a] -> [b]
mapo' f xs = foldr (\curr acc -> (f curr) : acc) [] xs
于 2016-07-24T17:42:29.473 に答える
1

あなたのソリューションはほとんど機能します。) 問題は、両方の関数 (パターンマッチング内とラムダ式内) に x の 2 つの異なるバインディングがあるため、最初の要素を見失うことです。

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\x xs -> (f x):xs) [] (x:xs)

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

これはトリックにすべきです:)。また、関数を無意味なスタイルで簡単に書くことができます。

于 2011-04-20T07:21:43.413 に答える