Почему foldr работает с бесконечным списком?

Эта функция может работать с бесконечными списками ассоциаций, и легко понять, почему:

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v  
findKey key [] = Nothing  
findKey key ((k,v):xs) = if key == k  
                         then Just v  
                         else findKey key xs

Когда он находит ключ, он возвращает Just v, останавливая рекурсию. Теперь посмотрите на эту другую реализацию:

 findKey' :: (Eq k) => k -> [(k,v)] -> Maybe v  
 findKey' key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing

Откуда компилятор/интерпретатор знает, что когда ключ соответствует k, он может его вернуть?

 *Main> findKey' 1 $ zip [1..] [1..]

возвращает Just 1

Когда он находит это key == k, он возвращает Just v. Почему на этом рекурсия останавливается, позволяя нам делать такие вещи с бесконечными списками ассоциаций?


recursion fold haskell
person FtheBuilder    schedule 06.06.2015    source источник
comment
Оцените его вручную и убедитесь сами.   -  person n. 1.8e9-where's-my-share m.    schedule 06.06.2015
comment
acc не является аккумулятором (слева); это рекурсивный результат (справа), поэтому лучше называть его r, чтобы избежать когнитивного диссонанса.   -  person Will Ness    schedule 07.06.2015
comment
@WillNess, вы имели в виду, что когда мы используем foldl/foldl', мы должны называть acc действительно acc, а когда мы используем foldr, мы должны называть его r, потому что это рекурсивная часть функции?   -  person FtheBuilder    schedule 07.06.2015
comment
@FtheBuilder, если подумать, в принципе, да, вот и все. :)   -  person Will Ness    schedule 17.06.2015

Ответы (2)


arrow_upward
6
arrow_downward

Потому что функция, переданная в foldr, не всегда оценивает параметр acc, т. е. ленится в этом параметре.

Например,

(\(k,v) acc -> if 1 == k then Just v else acc) (1,"one") (error "here be dragons!")

вернет "one", даже не пытаясь вычислить выражение error.

Более того, foldr по определению удовлетворяет:

foldr f a (x:xs) = f x (foldr f a xs)

Если x:xs бесконечно, но f не использует свой второй аргумент, то foldr может вернуться немедленно.

В вашем примере f оценивает свой второй элемент тогда и только тогда, когда первый аргумент не является желаемой ассоциацией. Это означает, что список ассоциаций будет оцениваться ровно настолько, чтобы найти ассоциацию key.

Если вы любите экспериментировать, попробуйте следующее:

foldr (\(k,v) acc -> case acc of
          Nothing -> if key == k then Just v else acc
          Just y  -> if key == k then Just v else acc) Nothing

case выглядит избыточным, так как функция возвращает одно и то же в обеих ветвях. Однако это требует оценки acc нарушения кода в бесконечных списках.

Еще одна вещь, которую вы, возможно, захотите попробовать

foldr (:) [] [0..]

Это в основном перестраивает бесконечный список как есть.

foldr (\x xs -> x*10 : xs) [] [0..]

Это умножает все на 10 и эквивалентно map (*10) [0..].

person chi    schedule 06.06.2015
comment
Большое спасибо, ваш пример очень помог. Небольшое замечание: так что, учитывая, что foldr f a (x:xs) = f x (foldr f a xs), если бы вместо него было foldr f a (x:xs) = f (foldr f a xs) x, это не работало бы в бесконечных списках? - person FtheBuilder; 07.06.2015
comment
@FtheBuilder Если f необходимо полностью оценить точное значение первого аргумента (как в вашем примере \(k,v) acc -> if k == 1 then ... else ...), то это не сработает. Однако, если f не нужно его оценивать (например, \pair acc -> acc), то он должен работать. - person mucaho; 07.06.2015
comment
@mucaho Мм, значит, он оценивает аргумент (не имеет значения порядок), только если он в основном нужен внутри его логики ?? - person FtheBuilder; 07.06.2015
comment
@FtheBuilder Да, в этом суть ленивой оценки. Вызов вашей второй папки таким образом foldr (\_ x -> x) 0 [10..] оценивается как (\_ x -> x) *thunk* 10 и печатает 10. - person mucaho; 07.06.2015
comment
@FtheBuilder Да, порядок не имеет значения. Важно то, является ли аргумент вынужденным/требуемым/необходимым. Например, сопоставление с образцом (case) и базовые операторы (==,+,*,...) могут вызвать аргумент. Это делает (\x -> 4) и (\x -> x*0 + 4) разными функциями: последняя будет оценивать x в отличие от первой. - person chi; 07.06.2015
comment
@mucaho @chi - Ваши примеры действительно прояснили меня, потому что, конечно, различия между (\x -> 4) и (\x -> x*0 + 4) не являются простыми деталями: если x - сложная вещь, которую нужно оценить, первый способ позволит избежать бесполезных вычислений. - person FtheBuilder; 07.06.2015

arrow_upward
2
arrow_downward

Непустой случай foldr можно определить как foldr f init (x:xs) = f x (foldr f init xs). В вашем случае f равно (\(k,v) acc -> if key == k then Just v else acc), поэтому (k,v) обозначает текущий элемент в списке, а acc обозначает (foldr f init xs). То есть acc означает рекурсивный вызов. В случае then вы не используете acc, поэтому рекурсивный вызов не происходит, поскольку Haskell ленив, что означает, что аргументы не оцениваются до тех пор, пока (и пока) не будут использованы.

person sepp2k    schedule 06.06.2015
comment
Что вы подразумеваете под непустым случаем foldr? Ваш ответ также был очень полезен для меня, спасибо! - person FtheBuilder; 07.06.2015
comment
@FtheBuilder Определение foldr состоит из двух случаев: один для пустого списка (foldr _ init [] = init) и один для непустых списков (foldr f init (x:xs) = f x (foldr f init xs)). Поскольку первое не имело отношения к вопросу, я говорил только о последнем случае. Вот что я имел в виду под непустым случаем. - person sepp2k; 07.06.2015
comment
Спасибо, теперь ваш ответ мне совершенно ясен! - person FtheBuilder; 07.06.2015