haskell - 在标准 ML 中根据 foldr 定义 foldl

Question

定义的代码是

fun foldl f e l = let
    fun g(x, f'') = fn y => f''(f(x, y)) 
    in foldr g (fn x => x) l e end

我不明白这是如何工作的； g(x, f'')的目的是什么？ ?

我也在 Haskell 中找到了一个类似的例子，
定义很短

myFoldl f z xs = foldr step id xs z
    where
        step x g a = g (f a x)

Answer 1

让我们来剖析 myFoldl 的 Haskell 实现然后看一下ocaml SML代码。首先，我们将看一些类型签名:

foldr :: (a -> b -> b) -- the step function
      -> b             -- the initial value of the accumulator
      -> [a]           -- the list to fold
      -> b             -- the result

需要注意的是，虽然 foldr函数只接受三个参数，我们正在应用它两个四个参数:

foldr step id xs z

但是，正如您所看到的 foldr 的第二个参数(即累加器的初始值)是 id这是 x -> x 类型的函数.因此，结果也是 x -> x 类型的.因此，它接受四个参数。

同样，阶跃函数现在的类型是 a -> (x -> x) -> x -> x .因此，它接受三个参数而不是两个参数。累加器是 endofunction (即域和共域相同的函数)。

Endofunctions 有一个特殊的性质，它们是从左到右而不是从右到左组成的。例如，让我们组成一堆 Int -> Int职能:

inc :: Int -> Int
inc n = n + 1

dbl :: Int -> Int
dbl n = n * 2

组合这些函数的正常方法是使用函数组合运算符，如下所示:

incDbl :: Int -> Int
incDbl = inc . dbl

incDbl函数首先将数字加倍，然后将其递增。请注意，这是从右到左读取的。

组合它们的另一种方法是使用延续(由 k 表示):

inc' :: (Int -> Int) -> Int -> Int
inc' k n = k (n + 1)

dbl' :: (Int -> Int) -> Int -> Int
dbl' k n = k (n * 2)

请注意，第一个参数是一个延续。如果我们想恢复原来的功能，那么我们可以这样做:

inc :: Int -> Int
inc = inc' id

dbl :: Int -> Int
dbl = dbl' id

但是，如果我们想组合它们，那么我们按如下方式进行:

incDbl' :: (Int -> Int) -> Int -> Int
incDbl' = dbl' . inc'

incDbl :: Int -> Int
incDbl = incDbl' id

请注意，虽然我们仍然使用点运算符来组合函数，但它现在是从左到右读取的。

这是制作背后的关键 foldr表现为 foldl .我们从右向左折叠列表，但不是将它折叠成一个值，而是将它折叠成一个内函数，当应用于初始累加器值时，它实际上是从左到右折叠列表。

考虑我们的 incDbl功能:

incDbl = incDbl' id
       = (dbl' . inc') id
       =  dbl' (inc' id)

现在考虑 foldr 的定义:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _   acc []     = acc
foldr fun acc (y:ys) = fun y (foldr fun acc ys)

在基础情况下，我们只返回累积值。然而，在归纳的情况下，我们返回 fun y (foldr fun acc ys) .我们的 step函数定义如下:

step :: a -> (x -> x) -> x -> x
step x g a = g (f a x)

这里 f是 foldl的reducer函数类型为 x -> a -> x .请注意 step x是 (x -> x) -> x -> x 类型的内功能我们知道可以从左到右组合。

因此，列表 foldr step id 上的折叠操作(即 [y1,y2..yn] )好像:

step y1 (step y2 (... (step yn id)))

-- or

(step y1 . step y2 . {dots} . step yn) id

每个 step yx是一种内功能。因此，这相当于从左到右组合内函数。

当这个结果应用于初始累加器值时，列表从左到右折叠。因此， myFoldl f z xs = foldr step id xs z .

现在考虑 foldl函数(用标准机器学习而不是 OCaml 编写)。它被定义为:

fun foldl f e l = let fun g (x, f'') = fn y => f'' (f (x, y))
                  in  foldr g (fn x => x) l e end

foldr最大的区别Haskell 和 SML 的功能是:

在 Haskell 中，reducer 函数的类型为 a -> b -> b .

在 SML 中，reducer 函数的类型为 (a, b) -> b .

两者都是正确的。这只是一个偏好问题。在 SML 中，不是传递两个单独的参数，而是传递一个包含两个参数的元组。

现在，相似之处:

id Haskell 中的函数是匿名函数 fn x => x SML 中的函数。

step Haskell 中的函数是函数 g在 SML 中，它接受一个包含前两个参数的元组。

step函数是 Haskell step x g a已在 SML 中拆分为两个函数 g (x, f'') = fn y => f'' (f (x, y))为了更清楚。

如果我们重写 SML 函数以使用与 Haskell 中相同的名称，那么我们有:

fun myFoldl f z xs = let step (x, g) = fn a => g (f (a, x))
                     in foldr step (fn x => x) xs z end

因此，它们的功能完全相同。表达式 g (x, f'')简单地应用函数 g到元组 (x, f'') .这里 f''是一个有效的标识符。