在 Elm/Haskell 中使用 foldr

Question

我在使用foldr解决这个问题时遇到了麻烦。我理解foldr用于简单问题（如foldr (+) 5 [1,2,3,4]），但这个问题更加复杂：

问题：q2的值是多少？

findSubsequence next highest = case next == highest + 1 of
  True -> next
  False -> highest

q2 = (foldr findSubsequence 0 [5,6,8,4,7,3,2,1,0,2,3,1,0]
     ,foldr findSubsequence 0 [0,1,3,2,0,1,2,3,7,4,8,6,5]
     ,foldr findSubsequence 0 [1,2,3,4,3,2,1]
     ,foldr findSubsequence 0 [4,3,2,1,2,3,4]
     )

使用foldr对每个列表进行操作，可以得到结果值，并将产生的列表组合起来，结果为[5,3,4,4]，但我不知道解决这个问题的过程。希望能够得到帮助 :)

- Chloe

---

我会从扩展 foldr 的定义开始。 - melpomene

Answer 1

foldr 中的 r 表示它是一个右折叠函数。 如果您不熟悉这个术语，结合操作符的结合性是指告诉我们如何解释由操作符的连续应用组成的模棱两可的表达式而不使用括号。通过指定运算符的结合性，我们通过指定应从哪一端评估表达式来解决歧义（因此使用右和左）。 例如，我们应如何解释以下表达式？

1 / 2 / 3 / 4

答案取决于运算符 / 的结合性。如果这个运算符是左结合的，答案是：

((1 / 2) / 3) / 4

另一方面，右结合的/会被计算为：

1 / (2 / (3 / 4)))

折叠(fold)实质上是一种通过在序列元素之间插入操作符的方式来形成这些表达式的方法。然而，由于结合性(associativity)，显然有两种同样有意义的方法来完成这个过程，分别被称为foldr和foldl。

将此应用于元组的最后一个元素(为了简洁起见，将findSubsequence重命名为f)，结果如下:

foldr f 0 [4,3,2,1,2,3,4] = f 4 (f 3 (f 2 (f 1 (f 2 (f 3 (f 4 0))))))
                          = f 4 (f 3 (f 2 (f 1 (f 2 (f 3 0)))))
                          = f 4 (f 3 (f 2 (f 1 (f 2 0))))
                          = f 4 (f 3 (f 2 (f 1 0)))
                          = f 4 (f 3 (f 2 1))
                          = f 4 (f 3 2)
                          = f 4 3
                          = 4

- dkasak

Answer 2

免责声明：这是在Haskell中，我不知道a `f` b语法在Elm中是否有效，但它不会改变结果，你只需要在发现它时使用f a b代替a `f` b

---

取q2的一个组件（我会取最后一个，因为它是它们中最短的）：

foldr findSubsequences 0 [4,3,2,1,2,3,4]
{ with fSs = findSubsequences - note that [] is replaced with the 0 of the first arg }
= 4 `fSs` (3 `fSs` (2 `fSs` (1 `fSs`(2 `fSs` (3 `fSs` (4 `fSs` 0))))))
{ 4 is not 0+1 so 4 `fSs` 0 = 0 }
= 4 `fSs` (3 `fSs` (2 `fSs` (1 `fSs`(2 `fSs` (3 `fSs` 0)))))
{ 3 is not 0+1  so 3 `fSs` 0 = 0 }
= 4 `fSs` (3 `fSs` (2 `fSs` (1 `fSs`(2 `fSs` 0))))
{ 2 is not 0+1  so 2 `fSs` 0 = 0 }
= 4 `fSs` (3 `fSs` (2 `fSs` (1 `fSs`0)))
{ 1 IS 0+1  so 1 `fSs` 0 = 1 }
= 4 `fSs` (3 `fSs` (2 `fSs` 1))
{ 2 IS 1+1 so 2 `fSs` 1 = 2 }
= 4 `fSs` (3 `fSs` 2)
{ 3 IS 2+1 so 3 `fSs` 2 = 3 }
= 4 `fSs` 3
{ 4 IS 3+1 so 4 `fSs` 3 = 4 }
= 4

在这里，每一步都是通过使用你的定义来实现的

我希望你也能为其他情况做同样的事情:D

---

请注意，我使用了一个简单的技巧来替换：

• :替换成findSubsequences
• []替换成0（即`findSubsequences`的第一个参数）

其中，你将你的输入列表表示为a:b:c:...:[]

- Random Dev

---

在Elm中，a \f` b 是有效的语法，它使用::作为列表的构造器，而不是Haskell中的:`。 - mgold