foldr/foldl и поиск ключа в массиве

Ленивость?

Прочти исходник foldr, например.

Второй способ понятней. Тут имеется ввиду, что foldr наглядней, ксли не ошибаюсь это hs в реальном мире. Лучше кончено использовать готовую lookup.
--
Fluttershy.

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Значение аккумулятора возвращается только после прохода всего списка. И ленивость здесь не работает.

k - не может быть ленивой ф-ей?

// по сабжу: имхо, первый читабельнее (только guard заместо if), lookup так и сделан

Вот смотри ты прав, но читай выше. http://www.haskell.org/onlinereport/standard-prelude.html

-- lookup key assocs looks up a key in an association list.

lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup key []    =  Nothing
lookup key ((x,y):xys)
    | key == x   =  Just y
    | otherwise  =  lookup key xy

Потому что foldr это такой шаблон, и лучше использовать шаблоны.

ксли не ошибаюсь это hs в реальном мире

Нет, Learn You a Haskell for Great Good
Спасибо за помощь, флатти :)

«Ага, лучше использовать первый, так как он прервётся как только найдёт искомый ключ, а второй пройдёт по всему массиву в любом случае»

т.е. 2-ой findKey не выполнится на бесконечном списке? Советую проверить.

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

Безымянная функция во втором варианте игнорирует второй аргумент, если значение найдено,

а можно обоснование?

Можешь рассказать, кинуть почитать на тему «почему foldr» не вываливается и выполняется. Что-то тут не совсем чисто.

> let a = [(x, x*x) | x <- [1..]]
> let b = foldr (\(k,v) acc -> if 5 == k then Just v else acc) Nothing a
> b
Just 25

Но естественно падает, когда ключ не найден, единственное, что приходит в голову: что оптимизируется вызов.

Можешь проверить. Провел экспиремент, выходит, что foldr лениво обрабатывает список и так же гипотетически заполянет аккумулятор. Вот иллюстрация:

Prelude> let a = [x | x <- [1..]]
Prelude> let b = foldr (\int acc -> if int == 4 then int:acc else acc) [] a
Prelude> take 1 b
[4]
Prelude> let b = foldr (\int acc -> if int == 4 then acc++[int] else acc) [] a
Prelude> take 1 b
CInterrupted.

Второй вариант тоже прервётся, как только найдёт искомый ключ. По тем же причинам. Но он лучше, так как явную рекурсию ты убираешь в библиотечный комбинатор.

Значение аккумулятора возвращается только после прохода всего списка.

Нет, если функция k не требует вычисления второго аргумента.

http://www.haskell.org/haskellwiki/Non-strict_semantics

второй пройдёт по всему массиву в любом случае

> foldr (\e a -> e) 0 [1 ..]
1
> let findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing
> let inf = (1, 2) : inf
> take 10 inf
[(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2)]
> findKey 1 inf
Just 2

если функции k передаваемая foldr ленива относительно аккумулятора, то

            go (y:ys) = y `k` go ys

спокойно вернёт значение без дальнейшего вычисления go для ys.

Возможно, вот это поможет: http://ics.p.lodz.pl/~stolarek/blog/2012/09/why-foldr-works-for-infinite-list...