kb
17.10.2012 13:30 04a3831c
Да уж, ленивость окончательно запутывает и так непростую ситуацию с foldl и foldr. Приходится ломать мозги.
Получается, что, в классическом варианте, когда вы проходите по всему списку, то (по возможности) лучше использовать foldl', т.к. хвостовая рекурсия и всё такое.
С другой стороны, в виду ленивости, foldr имеет возможность прервать свою работу когда ему необходимо, при этом не вычисляя foldr хвоста.
Или здесь я тоже где-то ошибаюсь? :)
37 comments
recommend
bookmark
subscribe
Какого хвоста? foldr идет справа.
ну, хвоста — в смысле "остатка".
о, ты тоже попался, выходит. нифига оно не с хвоста идёт, а вполне с головы. просто если функция делает вычисления, учитывая аккумулятор, то он тоже вычисляется и т.п.
в результате, вот это:
findKey :: (Eq k) => k → [(k,v)] → Maybe v
findKey key = foldr (\(k,v) acc → if key == k then Just v else acc) Nothing
очень даже эффективно работает, никакого хвоста не дёргая.
Prelude> let a = [1, 2, 3]
Prelude> (foldl (-) 0 a, foldr (-) 0 a)
(-6,2)
да, но только это не "оно идёт справа", а "оно подставляет аккумулятор вправо / влево". а "идёт" оно как раз всегда слева направо.
ну, то есть, это ваше "справа" и "слева" — это просто порядок аргументов к функции твоей и не более.
Ну блядь.
http://zvon.org/other/haskell/Outputprel...
it takes the second argument and the last item of the list and applies the function, then it takes the penultimate item from the end and the result, and so on. See scanr for intermediate results.
> the last item
Читай внимательно сорсы foldr, там вполне видно, что идет оно именно справа налево.
нахуй мне твои тексты, вот исходник
-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
А теперь подумай, что выполнится сначала, f x (foldr f z xs) или foldr f z xs. Вопрос глупый, да.
> (x:xs)
> справа налево
Ты неправильно читаешь исходник.
Все правильно. foldr в ленивом режиме, foldl — в энергичном.
ну еще раз. соль (которую я еле допёр) в том, что
*Main> findKey 1 (map (\x → (x, x)) [1..10000000000000000000000000])
сработает мгновенно, т.к. в этом здоровом списке он возьмёт только первый элемент. если ты будешь делать findKey 2, то возьмутся первых два элемента. это я и называю "слева направо".
Не надо меня троллить :(
wut?
Если твоя f из foldr такова, что ее можно заэвалюейтить без вычисления второго аргумента, то да, все так. Но дело-то не в этом.
Имеется ввиду, конечно же, «иногда можно».
что, правда есть понятие "энергичный режим"?
ок, энергичные вычисления
ну об этом же и вся речь
ну, ок. я думал издеваешься.
ага, и еще прикол в том, что с foldl это сделать "никогда нельзя".
я добрый хуй
звучит как кавер на песню найка борзова
Никогда не слушал Найка Борзова.
ну там про куркуму в роли лошади
Звучит как откровенное признание
!
А, заебись.
Звучит как пойдем попилить личкрафты
;]
Непристойное предложение.
Ж(
Ты должен привлечь разработчика! Будь мужиком, не мямли, пригласи его на ревью. Однажды он зайдет к тебе на гитхаб и у вас будет жаркий merge.
я ленивый и поэтому не тыкаю хаскелль, всем советую
кстати да, не тыкать х-ь — это мета-ленивое программирование на х-е.
в целом, нужно очень хорошо понимать, что делаешь и что там внутри творится, когда ленивые вычисления сознательно используются для прерывания прохождения большого набора данных и для кое-каких подобных вещей.
Может "клитор в цепь засосать", в результате — типичное поведение типичных х-евых поделок в реальных условиях — пережор памяти.
Ну я благодаря SICP'у (и, в частности, главе, где ленивый интерпретатор писался), наверное, и въехал без совсем уж перелома костей. Так бы фиг осознал, наверное.