list - Haskell:使用(柯里和)计算列表的长度

Question

我被分配使用 foldr Haskell 函数计算列表的长度，所以我做了这两个例子

flength :: [a] -> Int
flength = foldr (\ _ n -> n+1) 0

flength' :: [a] -> Int
flength' l = foldr aux 0 l
    where
        aux _ n = n+1

然后，作为个人挑战，教授要求我们使用 snd 函数，昨天我想出了这个:

flength'' :: [a] -> Int
flength'' = foldr ((+1).(curry snd)) 0

我想要发生的是，这个函数会将列表头 h 和累加器 0 转换为对 (h,0) 然后返回 0 ，然后将其应用于函数 (+1)

我希望这是递归完成的，有效地在最后给出列表的长度。

相反，我收到此错误消息:

    [1 of 1] Compiling Main             ( f1.hs, interpreted )

f1.hs:54:24: error:
    * No instance for (Num (Int -> Int))
        arising from an operator section
        (maybe you haven't applied a function to enough arguments?)
    * In the first argument of `(.)', namely `(+ 1)'
      In the first argument of `foldr', namely `((+ 1) . (curry snd))'
      In the expression: foldr ((+ 1) . (curry snd)) 0 xs
Failed, modules loaded: none.

为什么会发生这种情况以及如何使该代码正常工作？

Answer 1

让我们把所有的工具放在我们面前，就像一个优秀的工匠一样:

foldr :: (a -> b -> b) -> b -> [a] -> b
snd   :: (a, b) -> b

首先，我们注意到 snd 和 foldr 不太适合。因此，让我们像您一样使用 curry，并将 curry snd 添加到我们的小工具库中:

foldr     :: (a -> b -> b) -> b -> [a] -> b
curry snd ::  a -> b -> b

这看起来非常有希望。现在我们需要将 1 添加到 curry snd 的结果中，否则我们只是编写 flip const。让我们从 lambda 开始:

\a b -> 1 + curry snd a b
= \a b -> ((+1) . curry snd a) b

我们现在可以插入 b 并最终得到

\a -> (+1) . curry snd a
= \a -> (.) (+1) (curry snd a)
= \a -> ((.) (+1)) (curry snd a)
= \a -> (((.) (+1)) . curry snd) a

现在我们也可以从两侧对 a 进行 eta-reduce，最终得到

(((.) (+1)) . curry snd) = ((+1) . ) . curry snd

因此，你的第三个变体是

flength'' = foldr (((+1) . ) . curry snd) 0

现在，您为什么收到错误消息？您与 (+1) 很接近。 curry snd，但类型不起作用:

(+1)      :: Int -> Int
--            v                    v
(.)       :: (b ->  c)    -> (a -> b       ) -> a -> c
curry snd ::                  t -> (x -> x)
              ^                     ^

但就您而言，(.) 签名中的 b 不匹配。其中一个是 Int，另一个是函数。

TL;DR:如果要无点地编写 f (g x y)，请编写 ((f.) . g)