3622
правки
Изменения
→Кр4
=Кр4=
== deforestation ==
Дана функция, необходимо её упростить, пользуясь техникой ''deforestation''.
'''Мотивация:''' допустим, есть какая-то функция следующего вида:
<code>
foldl 0 (*) . filter (> 0) . map (\ x -> 3 * x - 10)
</code>
Первый map создаёт новый список, потом filter возвращает ещё список, и так далее. Если функций много (а их вполне может быть сколько угодно), то такой подход перестаёт быть эффективным. Идея в том, чтобы написать функцию, которая делает все необходимые действия "за раз": в данном примере можно рассматривать элемент списка, применять к нему функцию, потом проверять на условие в filter, а потом сразу считать произведение. Иногда можно посмотреть на композицию функций и придумать сразу оптимальный вариант. Это и требуется сделать во втором задании. Но можно и не думать, а применить стандартный алгоритм для преобразования, который даёт ответ.
[http://www.sciencedirect.com/science/article/pii/030439759090147A По этой ссылке] описаны правила, по которым нужно преобразовывать функцию. Если коротко, то всё сводится к inline'у тел функций, причём мы хотим добиться отсутствия вызовов других функций на месте аргументов внешней функции (рекомендуется для начала почитать ссылку, посмотреть правила и пример оттуда).
=== Пример ===
Будет разобран пример из [https://pp.vk.me/c622121/v622121192/ff98/NtvrRei7bR4.jpg фото].
<code>
<font color=green>-- дано</font>
func = foldr (+) 0 . map (\x -> x * 10)
<font color=green>-- сначала перепишем композицию в обычную аппликацию для дальнейшей ясности</font>
func0 l = foldr (+) 0 (map (\x -> x * 10) l)
<font color=green>-- теперь инлайним foldr, то есть раскрываем его тело</font>
func1 l = '''case''' (map (\x -> x * 10) l) '''of'''
[] -> 0
(x:xs) -> x + (foldr (+) 0 xs)
<font color=green>-- а теперь инлайним map, заодно раскроем лямбду</font>
func2 l = '''case''' ('''case''' l '''of'''
[] -> []
(y:ys) -> y * 10 : map (*10) ys) '''of'''
[] -> 0
(x:xs) -> x + (foldr (+) 0 xs)
<font color=green>-- применяем преобразование case'a case'ов, то есть выносим внутренний case на первое место</font>
func3 l = '''case''' l '''of'''
[] -> ('''case''' [] '''of'''
[] -> 0
(x:xs) -> x + (foldr (+) 0 xs))
(y:ys) -> ('''case''' (y * 10 : map (*10) ys) '''of'''
[] -> 0
(x:xs) -> x + (foldr (+) 0 xs))
<font color=green>-- раскрываем внутренние case'ы: в них pattern-matching сразу срабатывает</font>
func4 l = '''case''' l '''of'''
[] -> 0
(y:ys) -> 10 * y + (foldr (+) 0 (map (*10) ys))
<font color=green>-- замечаем, что у нас получилось в конце выражение foldr (+) 0 (map (*10) ys), а это по сути наша функция func0,
которую мы раскрывали изначально, поэтому тому куску можно дать имя другое имя</font>
func5 l = '''case''' l '''of'''
[] -> 0
(y:ys) -> 10 * y + func5 ys
</code>
