Использую ли я обоснованные рациональные рассуждения об определении фильтра в терминах 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])))

, и это будетbe

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

При первом прочтении мне это кажется правильным.

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

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.