如何在没有辅助方法的情况下实现这个 foldl0 功能？

Question

我有以下代码：

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 ?
  }
}

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

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

Answer 1

只需使用与 foldr0 中完全相同的方法，但拆分数组 to the other side:

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 函数并带有初始累加器值的参数，这会容易得多。

Answer 2

我们将研究每个泛型 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) 如何在任何 [=18] 之前一直向下传递到调用堆栈=] 曾经被计算过

// 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 情况并非如此 – 每个步骤都会计算 new acc，并且需要计算 next 步骤，所以我们不能像 foldr 那样只是删除参数并替换为 0。相反，最简单（也是最聪明）的实现变成了

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

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

这不符合您 "no helper method" 的标准，但这不是真的。这个练习很可能是为了向您展示为什么在没有辅助助手的情况下实施左折叠具有挑战性；作为帮助您可视化过程的一种方式。

tl:dr;

JavaScript 充满了各种各样的技巧，所以你可以通过作弊来通过你的 class 并防止自己学到任何东西！

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 )

Answer 3

一种非常简单的方法是使用剩余运算符的 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));

如何在没有辅助方法的情况下实现这个 foldl0 功能？

How to implement this foldl0 function without helper method?

implementation

functional-programming

fold

foldleft