索引文件夹如何运作？

Question

我无法理解定义：

ifoldr :: Foldable f => (Int -> a -> b -> b) -> b -> f a -> b
ifoldr f z xs = foldr (\ x g i -> i `seq` f i x (g (i+1))) (const z) xs 0

特别是，它似乎通过避免 zip [1..] 来避免 space 泄漏，同时它似乎派生了一个新的折叠 "step function"，它在前面给出了额外的参数，但这个论点最后在 \ x g i!

中传递

对于保留非严格属性的某些定义 f' = _unknown_ f，这是否等同于 f' x (foldr f' z xs)？

Answer 1

简而言之：foldr 生成一个函数（不是值列表），然后该函数将生成该列表。

让我们先暂时忽略foldr，专注于foldr中使用的函数，让我们调用这个函数eval:

eval x g i = seq i (f i x (g (i+1))))

我们将在这里忽略 seq：是的，它有一些语义：评估（弱头部范式）i 并检查是否 i 是底部，但让我们假设这不会引入底部。所以 eval 或多或少相当于：

eval x g i = f i x (g (i+1))

现在我们可以重新考虑 foldr 上下文：

ifoldr f = foldr eval (const z) xs 0
    where eval x g i = f i x (g (i+1))

现在 foldr 被定义（对于列表，但让我们在这里保持简单），如：

foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

对于包含三个元素的列表 [x1, x2, x3]，这意味着：

foldr eval (const z) [x1, x2, x3]

看起来像：

-- foldr eval (const z) [x1, x2, x3] is equivalent to
eval x1 (eval x2 (eval x3 (const z)))

由于 eval 的定义如上，这意味着我们可以将其专门化为：

\i1 -> f i1 x1 ((\i2 -> f i2 x2 (\i3 -> f i3 x3 (const z)) (i2 + 1)) (i1 + 1))

或者以一种使结构更清晰的方式：

\i1 -> (
    f i1 x1
    \i2 -> (
        f i2 x2
        \i3 -> (
            f i3 x3
            (const z) (i3+1)
        ) (i2+1)
    ) (i1+1)
)

因此，正如您所见，外部函数接受一个参数（此处为 i1），并使用 i1（索引）调用 f，x1（第一项），作为最后一项，调用的结果是剩余列表的 "fold"。因此，我们使用 i2 作为参数进行调用，但是 i2 与 i1+1.

绑定

因此，如果我们执行替换（将 i3 替换为 i2 + 1），这就是 lambda 演算的工作原理，我们将获得：

\i1 -> (
    f i1 x1
    \i2 -> (
        f i2 x2
        (
            f (i2+1) x3
            (const z) (i2+1+1)
        )
    ) (i1+1)
)

此外，我们可以用 i1+1:

替换 i2

\i1 -> (
    f i1 x1
    (
        f (i1+1) x2
        (
            f (i2+1) x3
            (const z) (i1+1+1+1)
        )
)

由于(const z)映射到z，不管参数是什么，我们都可以用z代替(const z) (i1+1+1+1)，所以：

\i1 -> (
    f i1 x1
    (
        f (i1+1) x2
        (
            f (i1+1+1) x3
            z
        )
)

所以现在我们知道 foldr eval (const z) [x1, x2, x3] 映射到什么，但是还有一个最终的功能应用程序：最后的 0。

所以这意味着我们用 0 调用上面定义的 lambda 表达式，所以这会折叠为：

\i1 -> (
    f i1 x1
    (
        f (i1+1) x2
        (
            f (i1+1+1) x3
            z
        )
) 0

因此：

(
    f 0 x1
    (
        f (0+1) x2
        (
            f (0+1+1) x3
            z
        )
)

或紧凑形式：

(f 0 x1 (f 1 x2 (f 2 x3 z)))

所以我们设法在我们的解决方案中注入索引。

现在seq当然有一个功能：它会阻止为索引创建巨大的（左递归）表达式树，而不是((((1+1)+1)+1)+1)+1，它会确保每次我们递增它，它立即被评估，所以我们永远不会获得 1+1+1，但总是 2+1，并立即将其解析为 3.

Answer 2

如果^{（确实如此）}

foldr c n (x:xs) = c x (foldr c n xs)  :: t

c x r = ...    -- r: mnemonic: recursive result

c x r :: t , r :: t , n :: t          -- same t

然后 surely ^{（通过 eta 展开）}

foldr c n (x:xs) i = c x (foldr c n xs) i  :: t

c x r i = ...   -- c = (\ x r i -> ... )

c x r i :: t , r i :: t , n i :: t        -- same t

所以我们可以

ifoldr f n (x:xs) = foldr c n (x:xs) i = c x (foldr c n xs) i    :: t
                                       = f i x (foldr c n xs i')  :: t

c x r i = f i x (r i') 

c x r i :: t , r i :: t , n i :: t , f i x :: t -> t

这正是您得到的结果。

索引文件夹如何运作？

How does indexed foldr work operationally?

haskell

fold