Я использую звуковые экваторные рассуждения о определении фильтра в терминах Foldr?

Question

Ну, это определение функции фильтра с использованием Foldr:

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

Так что, например, скажем, у меня есть эта функция:

myFilter odd [1,2,3,4]

Так что это будет:

foldr step [] [1,2,3,4]

И это будет

step 1 (foldr step [] [2,3,4])

И это будет

step 1 (step 2 (foldr step [] [3,4]))

И это будет

step 1 (step 2 (step 3 (foldr step [] [4])))

И это будет

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

а также foldr step [] [] является [] так:

step 1 (step 2 (step 3 (step 4 [])))

Теперь мы будем на самом деле попасть в step функция.
Вот определение step внутри myFilter Функция, сверху:

step x ys | p x       = x : ys
          | otherwise = ys

Кроме того, я напоминаю вам, что p на самом деле odd функция в нашем примере.

Ну, опять же, мы здесь:

step 1 (step 2 (step 3 (step 4 [])))

а также

x = 4 самым внутренним step, а также 4 не странно, поэтому мы возвращаем ys, который []

Так что теперь мы получаем это:

step 1 (step 2 (step 3 []))

Теперь, в самый внутренний step, x = 3, а также 3 нечетно, поэтому мы возвращаем x:ys, который 3 : [], который [3], А теперь мы получаем:

step 1 (step 2 [3])

И сейчас, во внутреннем step, x = 2, а также 2 не странно, поэтому мы возвращаем ys, который [3], Так что теперь мы получим:

step 1 [3]

и сейчас, x = 1, а также 1 нечетно, поэтому мы возвращаем x : ys, который 1 : [3], который [1,3].

Конец :-).

Я прямо во всех моих ходах?
большое спасибо :-).

PS Определение myFilter из книги Real World Haskell, в главе 4.

Answer 1

Это выглядит прямо мне на первом чтении.

Однако важно вспомнить, что для достижения ленивой оценки Haskell на самом деле будет смотреть на вещи на другую сторону. Другими словами, реальная последовательность больше похожа на

step 1 (step 2 (step 3 (step 4 [])))

становится

step 1 <block1>

который становится

[1, <block1>]

Затем, если вы попытаетесь вытащить следующий элемент из этого списка, он оценит

[1, step 2 <block2>]

который становится

[1, <block2>]

а затем пытаться оценить

[1, step 3 (step 4 [])]

превращается в

[1, step 3 <block3>]

который становится

[1, 3, <block3>]

И т.д. Это дало мне некоторое время, чтобы понять. Это было противоречито мне, что с foldr кажется, оценивается из «наизнания», но foldl оценивается из «снаружи», что foldr будет ленивым (что это есть), тогда как foldl строго. Но если вы думаете об этом, как я изложил выше, это имеет смысл (для меня, в любом случае).

Answer 2

Просто чтобы расширить порядок ленивого оценки: в основном Haskell всегда оценивает функцию сначала, не глядя на аргументы, пока он не должен.

Если результат вызова myFilter используется (например, напечатано), функция будет оценена в следующем порядке:

myFilter odd [1,2,3,4]

Сначала myFilter Функция оценивается:

foldr step [] [1,2,3,4]

Сейчас foldr Это внешняя функция и оценивается:

step 1 (foldr step [] [2,3,4])

Сейчас step Получает оценку производства 1, поскольку 1 нечетно:

1 : foldr step [] [2,3,4]

Теперь первый элемент списка результатов доступен и может использоваться функцией вызова. Если функция вызывания также использует следующие оценки элементов, продолжается с foldr:

1 : step 2 (foldr step [] [3,4])

Оценка step Сейчас не дает никаких новых элементов, так как 2 даже:

1 : foldr step [] [3,4]

Так foldr опять таки:

1 : step 3 (foldr step [] [4])

Теперь оценка step производит 3:

1 : 3 : foldr step [] [4]

Оценка foldr;

1 : 3 : step 4 (foldr step [] [])

А также step еще раз:

1 : 3 : foldr step [] []

Ну наконец то foldr Оценивается в пустом списке:

1 : 3 : []

Answer 3

На первый взгляд, шаги, которые вы предпринимали в вашем конкретном примере, выглядят правильно индивидуально. Тем не менее, я хотел бы отметить, что оба filter а также foldr может быть полезно применен к Бесконечные списки- что должен указать, что порядок ваших шагов неверно, насколько касается Haskell.