在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],但我不知道解决此问题的过程.帮助将不胜感激:)

Answer 1

该r中foldr表示,这是一个右结合倍.

如果你不熟悉这个术语,关联性是运算符的一个属性,它告诉我们如何解释由运算符的顺序应用程序组成的不带括号的模糊表达式.通过指定运算符的关联性,我们通过指定应该从中计算表达式的结束来解决歧义(因此使用右和左).

作为一个例子,我们应该如何解释以下表达式？

1 / 2 / 3 / 4

答案取决于操作员的相关性/.如果运算符是左关联的,答案是:

((1 / 2) / 3) / 4

另一方面,右关联/将评估为:

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

实质上,折叠是通过在序列的元素之间散布运算符来形成这种表达式的方式.然而,由于相关性,显然有两种同样有意义的方法,导致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