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

Хорошо, это определение функции фильтра с использованием 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.

Источник

3 ответа

Решение

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

Однако важно помнить, что для того, чтобы добиться ленивой оценки, 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 строгое Но если вы думаете об этом так, как я обрисовал выше, это имеет смысл (для меня, во всяком случае).

Источник

Просто чтобы расширить ленивый порядок оценки: в основном 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 : []
Источник

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

Источник
Другие вопросы по тегам