Зачем менять порядок списков, когда мы пытаемся добавить два списка, используя foldr?

Question

Я вижу сообщение , объясняющее, как добавить два списка, используя foldr.

Но я не понимаю, почему мы должны изменить порядок списков.

append xs ys = foldr (\x y -> x:y) ys xs

Первый ход будет

[y,x] (\x y -> x:y) foldr (\x y -> x:y) ys' xs'

Я прав?Будет ли результат тогда ставить ys перед xs?

Разве это не должно быть

append xs ys = foldr (\x y -> x:y) xs ys

Answer 1

Первый ход будет

[y,x] (\x y -> x:y) foldr (\x y -> x:y) ys' xs'

Это не допустимое выражение Haskell, но я думаю, что вы хотите выразить здесь, это то, что вы берете один элемент из каждого списка, а затемвставить их как-нибудь впереди.Это не то, как работает foldr - он не перебирает элементы аргумента z (в данном случае ys) - фактически этот аргумент даже не должен быть списком.

Вместо этого foldr f z (x:xs') расширяется следующим образом:

x `f` foldr f z xs'

и foldr f z [] расширяется до z.

Итак, в вашем случае первым шагом будет:

x : foldr (\x y -> x:y) ys xs'

Это будет продолжаться до тех пор, пока мы не доберемся до пустого списка, и в этом случае результатом будет ys.Итак:

  foldr (\x y -> x:y) ys [x1, x2, ..., xn]
= x1 : foldr (\x y -> x:y) ys [x2, ..., xn]
= x1 : x2 : foldr (\x y -> x:y) ys [..., xn]
= ...
= x1 : x2 : ... : xn : foldr (\x y -> x:y) ys []
= x1 : x2 : ... : xn : ys

И из этого видно, что элементы xs ставятся перед ys.

Answer 2

Первый ход не был бы таким.Проверьте тип свёртки

    ghci>:t foldr
    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Просто для упрощения предположим, что t будет [].В этом случае, foldr:

Дайте мне функцию f, которая принимает a и b и возвращает b.Дайте мне начальный элемент и список a.Я произведу b.

Итак, он работает следующим образом: возьмите последний элемент списка и примените f к этому элементу, а начальное значение создаст b.Возьмите новое последнее значение в списке и примените f к этому и предыдущему результату ... и т. Д.

В вашем случае, начальный элемент на самом деле является списком, и это грязно.Но проверьте это вычисление.Имейте в виду, что [1,2,3] используется в качестве начального значения, поэтому мы не «зацикливаемся» над ним

    foldr (\x y -> x:y) [1,2,3] [4,5,6]
    foldr (\x y -> x:y) 6:[1,2,3] [4,5]
    foldr (\x y -> x:y) 5:6:[1,2,3] [4]
    foldr (\x y -> x:y) 4:5:6:[1,2,3] []

Надеюсь, это поможет!

Answer 3

Интуиция заключается в том, что foldr c n list "заменяет" каждые : в list на c, а финальные [] на n.

Для добавления xs на ys нужно "заменить" окончательный [] внутри xs на ys.Вместо этого : следует заменить на себя.

Следовательно, мы получим foldr (:) ys xs.