4

タスクによって、foldlbyfoldrを実装する必要がありました。関数のシグネチャとfoldlの実装の両方を比較することで、次の解決策が得られました。

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl _ acc [] = acc
myFoldl fn acc (x:xs) = foldr fn' (fn' x acc) xs
    where
    fn' = flip fn

関数の引数を反転するだけで、foldrの期待される型を満たし、渡された関数を再帰的に適用することでfoldlの定義を模倣します。私の先生がこの答えをゼロ点で評価したので、それは驚きでした。

この定義が標準のfoldlと同じ方法で中間結果をスタックすることも確認しました。

 > myFoldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10])
 > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"
 > foldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10])
 > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"

正解は次の定義でした。

myFoldl :: (a -> b -> a) -> a -> [b] -> a    
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

以前の定義が間違っている理由を尋ねるだけですか？

4

1 に答える 1

10

基本的に、フォールドの順序が間違っています。foldl出力を正しくコピーしなかったと思います。私は次のようになります：

*Main> myFoldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10])
"((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"
*Main> foldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10])
"((((((((((+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)"

つまり、実装は最初の要素（基本ケース）を正しく取得しますが、残りはfoldrを使用するため、他のすべてが逆方向に処理されます。

Haskell wikiには、折り目が機能するさまざまな順序の素敵な写真がいくつかあります。

フォルダーの視覚化

foldlの視覚化

foldr (:) []これは、リストのIDがどのようになり、リストfoldl (flip (:)) []を逆にするかを示しています。あなたの場合、それが行うのは最初の要素を最後に置くことだけですが、他のすべては同じ順序のままにします。これがまさに私が意味することです：

*Main> foldl (flip (:)) [] [1..10]
[10,9,8,7,6,5,4,3,2,1]
*Main> myFoldl (flip (:)) [] [1..10]
[2,3,4,5,6,7,8,9,10,1]

これにより、Haskellでも、型が並んでいるからといってコードが機能するわけではないという理由で、より深く、はるかに重要なポイントに到達します。Haskell型システムは全能ではなく、多くの場合、任意の型を満たす関数が多数（無限の数でさえ）存在します。myFoldl退化した例として、タイプチェックの次の定義でさえ：

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl _ acc _ = acc

したがって、型が一致していても、関数が何をしているのかを正確に考える必要があります。折り目のようなことを考えるとしばらく混乱するかもしれませんが、あなたはそれに慣れるでしょう。

于 2012-09-01T17:53:40.397 に答える