haskell - 折叠函数中的字符串连接顺序

Question

我试图理解以下问题:我定义了一个列表，并在此列表上使用 fold 函数来连接这些字符串。

使用 foldr

food = ["Pizza", "Apple", "Banana"]
let f = (\a b -> take 3 a ++ b)
foldr f "" food
-- result
"PizAppBan"

同时使用 foldl

food = ["Pizza", "Apple", "Banana"]
    let f = (\a b -> take 3 a ++ b)
    foldr f "" food
    -- result
    "BanAppPiz"

所以我知道顺序会改变，因为尽管我们正在做一些交换操作，但顺序并不重要......对于字符串连接来说才是。所以问题是如何在 fold left 中评估字符串连接以及我如何从概念上可视化操作顺序？因为如果我逐步执行以下操作，过程将始终相同......

附言。我已经看到只有一些问题，但他们似乎不太清楚这个过程是如何工作的。

Answer 1

折叠函数的参数顺序被“翻转”。事实上，如果我们查看 foldl 和 foldr 的定义，我们会看到:

<a href="https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:foldl" rel="noreferrer noopener nofollow">foldl :: Foldable t => (<b>b -> a -> b</b>) -> b -> t a -> b</a>
<a href="https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:foldr" rel="noreferrer noopener nofollow">foldr :: Foldable t => (<b>a -> b -> b</b>) -> b -> t a -> b</a>

在这两个定义中，“累加器”的类型都是 b。但是正如您所见，在 foldl 函数中，fold 函数的类型为 b -> a -> b，因此第一个参数是累加器，第二个是元素，它返回累加器的新值。这说明折叠是从左到右进行的。

对于 foldr 函数，fold 函数的类型为 a -> b -> b，因此首先它获取一个元素，然后获取累加器的值折叠列表的其余部分，您应该返回累加器的新值。因此它从右向左折叠。

如果你想让它为 foldl 工作，你可以使用 \b a -> … 和 b 累加器。在这种情况下，您返回 b++ take a 3，因此我们将 a 的前三个字符附加到累加器的右端:

Prelude> foldr (\a b -> take 3 a ++ b) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"
Prelude> foldl (\b a -> b ++ take 3 a) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"

因此翻转参数是不够的。在 foldl 的情况下，评估是从左到右进行的，而在 foldr 的情况下，评估是从右到左进行的，因此这意味着您还需要交换您的方式连接。

foldl 变体在这里效率较低，因为 (++) :: [a] -> [a] -> [a] function花费的时间与第一个操作数的长度成线性关系。

函数 \a b -> take 3 a++ b 不是可交换的，也不是结合的。实际上，可交换意味着对于每个 x 和 y，f x y 都等于 f y x。但是，如果我们调用 f "foobar""qux"，我们会检索:

Prelude> f "foobar" "qux"
"fooqux"
Prelude> f "qux" "foobar"
"quxfoobar"

concat 操作 (++) 也不是可交换的。

此外，由于 take 3 部分，操作也不是关联。实际上，关联运算意味着 f x (f y z) 等于 f (f x y) z 对于每个 x、y 和 z。但我们看到:

Prelude> f (f "foo" "bar") "qux"
"fooqux"
Prelude> f "foo" (f "bar" "qux")
"foobarqux"

但是，如果您先执行 map 以获取每个字符串的前三个字符，那么顺序确实无关紧要:

Prelude> foldl (++) "" (map (take 3) food)
"PizAppBan"
Prelude> foldr (++) "" (map (take 3) food)
"PizAppBan"

take 3 部分因此使函数非关联，因此您不能在 foldl 和 中都使用它foldr 没有适本地调整它。