Haskell：使用（curry and）计算列表的长度

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) 然后 return 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

让我们把所有的工具摆在我们面前，就像一个好的 artisan 所做的那样：

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

现在我们也可以从两边eta-reduce a，最后得到

(((.) (+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)point-free，写((f.) . g)

Haskell：使用（curry and）计算列表的长度

Haskell: Calculate the length of a list using (curry snd)

haskell

list

currying

fold