根据标准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

让我们剖析一下Haskell的实现,myFoldl然后看看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.因此,它接受三个参数而不是两个.累加器是一个内功能(即其域和codomain相同的函数).

内功能具有特殊属性,它们由左到右而不是从右到左组成.例如,让我们组成一堆Int -> Int函数:

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

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

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

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

该incDbl函数首先将一个数字加倍,然后递增它.请注意,这从右到左阅读.

构成它们的另一种方法是使用continuation(表示为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,是类型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函数(用标准ML而不是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

foldrHaskell和SML 的最大区别在于:

1. 在Haskell中,reducer函数具有类型a -> b -> b.
2. 在SML中,reducer函数具有类型(a, b) -> b.

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

现在,相似之处:

1. 将id在Haskell功能是匿名fn x => x的SML功能.
2. 的step在Haskell功能是功能g在SML这需要含有第一两个参数的元组.
3. 该step功能哈斯克尔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''是一个有效的标识符.