1

我有以下代码：

function foldr0(list, func) {
  if (list.length == 0) {
    return 0;
  } else {
    return func(list[0], foldr0(list.slice(1), func));
  }
}

function foldl0(list, func) {
  if (list.length == 0) {
    return 0;
  } else {
    return ?
  }
}

foldl0我知道通过定义辅助方法iter(list, func, part_result)并将结果存储为参数很容易实现具有迭代逻辑的递归。但是如何在foldl0没有辅助方法的情况下实现，就像foldr0's implementation？

注意：为了方便起见，我用 Javascript 编写了这个问题。请用car和解决cdr，谢谢。

4

3 回答 3

1

我们将研究由每个泛型foldr和foldl. 看到下面的实现，比较如何f得到的结果foldr，但foldl得到的结果f

const foldr = ( f , acc , xs ) =>
  isEmpty (xs)
    ? acc
    : f ( foldr ( f , acc , tail ( xs ) )
        , head ( xs )
        )

const foldl = ( f , acc , xs ) =>
  isEmpty (xs)
    ? acc
    : foldl ( f
            , f ( acc , head ( xs ) )
            , tail ( xs )
            )

现在让我们仔细看看这个过程 - 在 中foldr，您可以看到acc( ) 在计算0任何内容之前如何一直沿调用堆栈向下传递f

// example call
foldr ( f , 0 , [ 1 , 2 , 3 ] )

// notice we can't run f yet, still waiting for foldr
f ( foldr ( f , 0 , [ 2 , 3 ] )
  , 1
  )


// now 2 f calls pending; still waiting on foldr
f ( f ( foldr ( f , 0 , [ 3 ] )
      , 2
      )
  , 1
  )

// now 3 f calls pending, still waiting on foldr
f ( f ( f ( foldr ( f , 0 , [] )
          , 3
          )
      , 2
      )
  , 1
  )

// now we can compute the inner most f, working our way out
f ( f ( f ( 0
          , 3
          )
      , 2
      )
  , 1
  )

// in other words, foldr traverses your input and creates a stack of f calls
f ( f ( f ( 0 , 3 ) , 2 ) , 1 )

调用堆栈foldl有很大不同——注意 acc 是如何立即使用的

// pretend f = ( x , y ) => x + y
foldl ( f 
      , 0
      , [ 1 , 2 , 3 ]
      ) 

// this time f is called first, and the result becomes the next acc
foldl ( f
      , f ( 0 , 1 ) // next acc = 1
      , [ 2 , 3 ]
      )

// f is always computed before recurring
foldl ( f
      , f ( 1 , 2 ) // next acc = 3
      , [ 3 ]
      )

// notice how foldl stays nice and flat (foldl uses a tail call, foldr doesn't)
foldl ( f
      , f ( 3 , 3 ) // next acc = 6
      , []
      )

// when the input is empty, the acc is just returned
foldl ( f
      , 6
      , [] // empty input
      )

// result
6

那么我们为什么要看这些泛型呢？那么重点是向您展示计算过程的样子。在流程的可视化中，您可以看到数据如何在程序中移动。

在foldr您可以看到如何acc立即从调用堆栈一路向下传递 – 因此您可以有效地删除acc参数并替换acc为0您的foldr0– 这正是您所拥有的

const foldr0 = ( f , xs ) =>
  isEmpty (xs)
    ? 0
    : f ( foldr0 ( f , tail ( xs ) )
        , head ( xs )
        )

然而，情况并非如此foldl——每一步都会计算一个新的acc 并且需要计算下一步，因此我们不能0像使用foldr. 相反，最简单（也是最聪明）的实现变成

const foldl0 = ( f , xs ) => 
  foldl ( f , 0 , xs )

const foldr0 = ( f , xs ) =>
  foldr ( f , 0 , xs )

这不符合您“无辅助方法”的标准，但这并不是真的。该练习可能旨在向您展示为什么在没有辅助助手的情况下实现左折叠具有挑战性；作为帮助您可视化过程的一种手段。

tl：博士；

JavaScript 充满了各种各样的技巧，所以你可以作弊以通过你的课程并阻止自己学习任何东西！

const isEmpty = xs =>
  xs.length === 0
  
const head = ( [ x , ... xs ] ) =>
  x
  
const tail = ( [ x , ... xs ] ) =>
  xs

const foldl0 = ( f , xs , acc = 0 ) =>
  isEmpty (xs)
    ? acc
    : foldl0 ( f
             , tail ( xs )
             , f ( acc , head ( xs ) )
             )
        
const myFunc = ( x , y ) =>
  `( ${x} + ${y} )`
  
console.log ( foldl0 ( myFunc , [ 1 , 2 , 3 ] ) ) 
// ( ( ( 0 + 1 ) + 2 ) + 3 )

于 2017-11-17T16:45:14.407 回答
0

只需使用与中完全相同的方法，foldr0但将数组拆分到另一边：

function foldl0(list, func) {
  if (list.length == 0) {
    return 0;
  } else {
    return func(list[list.length-1], foldr0(list.slice(0, -1), func));
//                   ^^^^^^^^^^^^^                     ^^^^^
//                       last                       without last
  }
}

当然，如果您有带有初始累加器值参数的foldl/函数，这会容易得多。foldr

于 2017-11-17T14:49:05.373 回答
0

一个非常简单的方法是使用由 rest 运算符进行的 Haskellesque 模式匹配，如下所示；

var foldl0 = ([x0,x1,...xs],f) => xs.length ? foldl0([f(x0,x1)].concat(xs),f)
                                            : f(x0,x1);

console.log(foldl0([1,2,3,4], (x,y) => x + y));

于 2017-11-22T21:11:31.947 回答