定义的代码是
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)
最佳答案
让我们来剖析 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 的功能是:a -> b -> b
. (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''
是一个有效的标识符。
关于haskell - 在标准 ML 中根据 foldr 定义 foldl,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29715959/