3622
правки
Изменения
м
* [[АВЛ-дерево]]: [http://pastebin.com/seB7yYyu ссылка на pastebin]
*: почему я не знал Haskell, когда это дерево было в лабе по дискретке на первом курсе? ;( просто списывается с конспекта один в один...
<tex> f(a) = a^2 f(a) + f(a) + a^3 </tex>Выразим производную.
Забудем на некоторое время, что мы работаем с типами. Продифференцируем обе части уравнение по переменной <tex> f'(a ) = \dfrac{2a \cdot f(a) + 3a^2}{1 - (a^2 + 1)} = (2a \cdot f(a) + 3a^2) \cdot \dfrac{1}{1 - (a^2 + 1)} \ (2)</tex>, получим линейное уравнение относительно производной, а затем выразим её.
→H1. Написать Haskell-код какой-нибудь структуру данных
=== Решение ===
В нормальной форме нет редукций. Если нормальная форма существует, то её можно достичь при помощи редукций [[#Нормальный порядок редукции|нормальным порядком]], а [[#Аппликативный порядок редукции|аппликативным ]] можно и не достичь.
# Уже в нормальное форме, как ни странно
== H1. Написать Haskell-код какой-нибудь структуру данных ==
* [[Квадродеревья | Квадродерево]]: [http://pastebin.com/jV4DeRvv ссылка на pastebin]
*: не совсем то, что требует Ян, но я пока не распарсил то, что он требует; возможно, более правильная версия появится позже
<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'''
<font color=green>-- замечаем, что у нас получилось в конце выражение foldr (+) 0 (map (*10) ys), а это по сути наша функция func0,
которую мы раскрывали изначально, поэтому тому куску можно дать имя другое имя</font>
func5 l = '''case''' l '''of'''
[] -> 0
== zippers and functions differentiation ==
Для каждой структуры данных (datatype'а) в Haskell можно составить соответствующий ей zipper: это другая структура данных, которая позволяет "гулять" по нашей структуре, беря взяв в фокус текущий элемент, и запоминая при этом остальное состание состояние структуры данных (или контекст). Для списка легко придумывается zipper: мы находимся на какой-то позиции в списке, знаем значение элемента на этой позиции, знаем часть списка слева от текущего элемента и справа (для более глубокого понимания читай LearnYourHaskell). Поэтому zipper для листа списка имеет следующий вид:
<code>
</code>
Но не для всех типов получается легко придумать zipper методом пристального взгляда. Чтобы уметь составить zipper для произвольного типабез особых усилий, можно представить тип как функцию от параметра типа, а затем найти производную этого типа. Тогда если типу соответствует функция <tex> f(a) </tex>, то zipper выражается следующим образом: <tex> z(a) = a \cdot f'(a) </tex>.
Рассмотрим внимательней типа List:
</code>
Запишем уравнение типа для него: <tex> f(a) = a \cdot f(a) \cdot a + f(a) + a \cdot a \cdot a\ (1)</tex>. На самом деле порядок аргументов в типе не очень важен, мы сами его задаём, поэтому можно написать чуть более сокращенную запись: <tex> f(a) = a^2 \cdot f(a) + f(a) + a^3 </tex> Забудем на некоторое время, что мы работаем с типами. Продифференцируем обе части уравнение по переменной <tex> a </tex>, получим линейное уравнение относительно производной. <tex> f'(a) = 2a \cdot f(a) + a^2 \cdot f'(a) + f'(a) + 3a^2 </tex> Заметка: на этом надо остановиться и написать соответствующий рекурсивный тип. За дальнейшие действия будет сняты 0.5 баллов(ЯН: "слишком сложное решение") <code> <font color=green>-- Итого ответ:</font> '''data''' DMice a = S a (Mice a) | H a (Mice a) | M a a (DMice a) | Y (DMice a) | A a a | K a a | Shmyak a a</code> Забавное, но бесполезное для сдачи ФП, продолжение:
В итоге у нас производная является произведением двух функций, а для типа это значит, что он является произведением двух типов. При умножении на константу у нас будет просто несколько одинаковых конструкторов с разными именами.<texcode> f <font color=green>--сначала распишем производную типа, полученного сразу после дифференцирования (1), если соблюдать исходный порядок аргументов в типах</font> '''data''' DMice a = S (Mice a) = 2a fa | H a (DMice a) + a^2 f'| M a (Mice a) + f'| Y (DMice a) + 3a^2 | A a a | K a a | Shmyak a a</texcode>
Теперь распишем первую скобку в (2):
<code>
'''data''' DMice' = M1 a (Mice a) | M2 a (Mice a) | C1 a a | C2 a a | C3 a a
</code>
Дальше идёт дробь. Вспоминаем, что на самом деле ей отвечает тип <tex> L(a^2 + 1) </tex>.
Поэтому получаем в итоге:
<code>
'''data''' DMiceListElem a = DM1 a a | DM0
'''data''' DMiceList a = MNil | MCons (DMiceListElem a) (DMiceList a)
'''data''' ZMice a = ZMice a (DMice' a) (DMiceList a)
</code>
* [http://learnyouahaskell.com/zippers LearnYourHaskell {{---}} Zippers]
* [http://sprunge.us/HCDN Пример zipper'a из кр]
