为什么 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 接受一个带有 3 个参数且类型为 a -> (Int -> a) -> Int -> a 的函数吗？特别是因为结果应该与第二个参数具有相同的类型？

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 (Int -> a) 类型的累积函数 (b)！ 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

此 (!!) 实施是报告版本。前奏的报告版本比熟悉的朴素递归实现更有效，由于 foldr.

的优化

为什么 foldr 可以带三个参数的函数？

Why can foldr take a function with three arguments?

haskell

types

arguments

function

fold