3622
правки
Изменения
→Кр4
* [http://www.mit.edu/~mtikekar/posts/stream-fusion.html Применение в реальной жизни]
* [http://sprunge.us/ZONH Разбор задания с кр]
== zippers and functions differentiation ==
Для каждой структуры данных (datatype'а) в Haskell можно составить соответствующий ей zipper: это другая структура данных, которая позволяет "гулять" по нашей структуре, беря в фокус текущий элемент, запоминая при этом остальное состание структуры данных (или контекст). Для списка легко придумывается zipper: мы находимся на какой-то позиции в списке, знаем значение элемента на этой позиции, знаем часть списка слева от текущего элемента и справа (для более глубокого понимания читай LearnYourHaskell). Поэтому zipper для листа имеет следующий вид:
<code>
'''data''' ZipperList a = ZList a [a] [a]
</code>
Но не для всех типов получается легко придумать zipper методом пристального взгляда. Чтобы уметь составить zipper для произвольного типа, можно представить тип как функцию от параметра типа, а затем найти производную этого типа. Тогда если типу соответствует функция <tex> f(a) </tex>, то zipper выражается следующим образом: <tex> z(a) = a \cdot f'(a) </tex>.
Рассмотрим внимательней типа List:
<code>
'''data''' List a = Nil | Cons a (List a)
</code>
Ему соотвествует следующее уравнение в функциях типов: <tex> f(a) = 1 + a \cdot f(a) </tex>. Если теперь продифференцировать обе части уравнения, то можно будет найти производную для списка. Обозначим список элементов типа <tex> x </tex> как <tex>L(x)</tex>. Из формулы для списка легко выражется, что <tex> L(x) = \dfrac{1}{1 - x} </tex>. Этим равенством будем пользоваться в дальнейшем.
=== Пример ===
Найдём теперь zipper для какого-нибудь конкретного класса:
<code>
'''data''' Mice a = Haystack a (Mice a) a | Baboon (Mice a) | List' a a a
</code>
Запишем уравнение типа для него: <tex> f(a) = a \cdot f(a) \cdot a + f(a) + a \cdot a \cdot a</tex>. На самом деле порядок аргументов в типе не очень важен, мы сами его задаём, поэтому можно написать чуть более сокращенную запись:
<tex> f(a) = a^2 f(a) + f(a) + a^3 </tex>
Забудем на некоторое время, что мы работаем с типами. Продифференцируем обе части уравнение по переменной <tex> a </tex>, получим линейное уравнение относительно производной, а затем выразим её.
<tex> f'(a) = 2a f(a) + a^2 f'(a) + f'(a) + 3a^2 </tex>
* [http://learnyouahaskell.com/zippers LearnYourHaskell {{---}} Zippers]
* [http://sprunge.us/HCDN Пример zipper'a из кр]
