Как реализовать эту функцию 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 ?
  }
}

Я знаю, что легко реализовать рекурсивный foldl0 с итерационной логикой, определяя вспомогательный метод iter(list, func, part_result) и сохранить результат в качестве аргумента. Но как реализовать foldl0 без вспомогательного метода, как foldr0реализация?

---

ВНИМАНИЕ: я написал эту проблему с Javascript для удобства. Пожалуйста, решите это с car а также cdr, Спасибо.

Answer 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 сильно отличается - обратите внимание, как акк используется немедленно

// 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 - новый акк вычисляется на каждом шаге, и он необходим для вычисления следующего шага, поэтому мы не можем просто отбросить параметр и заменить на 0 как мы сделали с foldr, Вместо этого самая простая (и самая умная) реализация становится

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

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

Это не соответствует вашим критериям "без вспомогательного метода", но это не совсем так. Это упражнение, скорее всего, должно показать вам, почему сложно реализовать левую складку без вспомогательного помощника; как средство, помогающее вам визуализировать процесс.

---

ТЛ: д-р;

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 )

Answer 2

Просто используйте точно такой же подход, как в 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 функции с параметром для начального значения аккумулятора.

Answer 3

Очень упрощенный подход с использованием сопоставления с шаблоном Хаскеллеска оператором rest может быть сделан следующим образом;

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));