编写高阶函数来捕获常见模式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技术上仍然是相同形式的情况.

Answer 2

看起来您可以使用foldr来表示所有这些.

foldr (*) 1 [1,2,3]  --f1

foldr (\_ a-> 1 + a) 0 [1,2,3]  --f2

foldr (+) 0 [1,2,3]  --f3

foldr (++) [] ["a","b","c"]  --f4

它们都需要列表,初始值和运算符.它们都从右到左应用运算符:例如f1 [1,2,3] = 1*2*(3*1) ,您可以使用foldr参数化运算符和init值.