haskell - 编写一个高阶函数来捕获常见模式haskell

Question

f1 [] = 1
f1 (x:xs) = x * f1 xs

f2 [] = 0
f2 (x:xs) = 1 + f2 xs

f3 [] = 0
f3 (x:xs) = x + f3 xs

f4 [] = []
f4 (x:xs) = x ++ f4 xs

这些都有一个共同的行为，我怎样才能准确地识别模式并编写一个高阶函数来捕获它？

Answer 1

所有*您的函数具有以下形式:

fn [] = P_0
fn (x:xs) = P_1 x (fn xs)

在哪里 P_0和 P_1是一些常数。我会调用 P_0 zero , 和 P_1 combine ，并将它们添加到函数中:

-- P_0  P_1     list   = result
fn zero _       []     = zero
fn zero combine (x:xs) = combine x (fn zero combine xs)

我们去吧。现在我们有 f1 = fn 1 (*) , f3 = fn 0 (+) , 和 f4 = fn [] (++) . f2有点奇怪，但你可以解决: f2 = fn 0 (\_ b -> b+1) .

向 GHCi 询问类型会给我们 fn :: b -> (a -> b -> b) -> [a] -> b , 和 Hoogling向我们展示了这个函数 fn实际上是函数 foldr :

foldr :: (a -> b -> b) -> b -> [a] -> b
--       ^combine         ^zero

所以你去:折叠，或者特别是正确的折叠( r 中的 foldr 表示正确)是您正在寻找的一般模式。

顺便说一句，也有左折叠。我会让你试着弄清楚那些可能是什么。 Hoogle 也可以在这里为您提供帮助。

您可以在这里看到另一种模式，称为 Monoids，但我也将把它留给您，因为它似乎超出了这个问题的范围。

* 这对于 f2 (x:xs) = 1 + f2 xs 来说可能看起来很奇怪，因为没有 x参与结果，但这只是 P_1 a b = 1 + b 的情况，这在技术上仍然是相同的形式。