为什么foldr可以使用三个参数？

Question

我正在查看一些列表操作并遇到!!：

(!!)                    :: [a] -> Int -> a
xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

函数(\x r k -> ...)的类型为a -> (Int -> a) -> Int -> a，但foldr采用的函数只能接受两个参数：

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

有人可以向我解释为什么foldr接受一个带有以下类型a -> (Int -> a) -> Int -> a的3个参数的函数吗？特别是因为结果应该与第二个参数具有相同的类型？

Answer 1

->是正确联想的。所以a -> b -> c是a -> (b -> c)。因此，你的类型

a -> (Int -> a) ->  Int -> a

是相同的

a -> (Int -> a) -> (Int -> a)

我们可以看到它非常适合foldr的类型。

Answer 2

（对他人的更多解释;）

(!!)                    :: [a] -> Int -> a
xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

foldr            :: (a -> b -> b) -> b -> [a] -> b
--                                   ^1          ^2

foldr通常会产生累积（？）值。在这种情况下，foldr生成b类型的累积函数（(Int -> a)）！ foldr ... tooLarge xs被评估为累积函数，并且这个累积函数（^2）采用n参数。 ^1是tooLarge的功能。有趣的是，这种累积函数的积累取决于自由变量n（即k）的值。

例如，['a', 'b', 'c'] !! 2的评估如下： \x r k = \'a' r 2 -> r (2-1)（r尚未知晓，并推动进一步评估。） \x r k = \'b' r 1 -> r (1-1) \x r k = \'c' r 0 -> 'c'

['a', 'b', 'c'] !! 3是这样的： \x r k = \'a' r 3 -> r (3-1) \x r k = \'b' r 2 -> r (2-1) \x r k = \'c' r 1 -> r (1-1)（r原来是tooLarge。）= tooLarge (1-1)（错误！）

您可以检查调试跟踪：

module Main where

import Debug.Trace

tooLarge _ = errorWithoutStackTrace "!!!: index too large"
negIndex = errorWithoutStackTrace "!!!: negative index"

(!!!)                    :: Show a => [a] -> Int -> a
xs !!! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> trace ("x: " ++ show x ++ ", k: " ++ show k) $
                                 case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

main = do
  print $ ['a', 'b', 'c'] !!! 2
  print $ ['a', 'b', 'c'] !!! 3

-- x: 'a', k: 2
-- x: 'b', k: 1
-- x: 'c', k: 0
-- 'c'
-- x: 'a', k: 3
-- x: 'b', k: 2
-- x: 'c', k: 1
-- sample: !!!: index too large

---

This (!!) implementation is a report version. The report version of the prelude is more efficient than a familiar naive recursive implementation, due to optimizations of foldr.