Изменения

Перейти к: навигация, поиск

Функциональное программирование

12 955 байт добавлено, 19:05, 4 сентября 2022
м
rollbackEdits.php mass rollback
=== Решение ===
В нормальной форме нет редукций. Если нормальная форма существует, то её можно достичь при помощи редукций [[#Нормальный порядок редукции|нормальным порядком]], а [[#Аппликативный порядок редукции|аппликативным ]] можно и не достичь.
# Уже в нормальное форме, как ни странно
[http://pv.bstu.ru/flp/fpLectures.pdf Здесь] ещё про стратегии редуцирования, но немного другим языком (может быть, кому-то более понятным).
'''Аппликативный порядок редуцирования''' {{---}} первым делом редуцируем самый правый левый самый глубокий терм. То есть сначала упрощаем "аргументы" аппликации.
Те же примеры (во всех случаях одна редукция будет произведена):
((λ x . y) (λ z . t)) ((λ a b c . a b c ((λ s . t) y) (λ t . x) u) (λ x . x)) ((λ x . x x) z) <tex> \Rightarrow </tex>
((λ x . y) (λ z . t)) ((λ a b c . a b c ((λ s . t) y) (λ t . x) u) (λ x . x)) (z z)
 
== Ленивый порядок редукции ==
 
'''Ленивый порядок редуцирования''' {{---}} это когда мы якобы заворачиваем терм в коробку, и если делаем редукцию в одном из термов коробки, то она делается во всех. При этом сам порядок редуцирования нормальный.
 
То есть пример:
 
(λ f . f f) ((λ x . x) z)
 
Сначала делаем обычную редукцию нормальным порядком и получаем:
 
((λ x . x) z) ((λ x . x) z)
 
А потом после редукции нормальным порядком надо сделать изменения сразу в двух термах, потому что они якобы в коробках, и получим суммарно за 2 редукции:
 
z z
==Выписать систему уравнений типизации==
Интересное наблюдение: переменная p в case является как раз нужным конструктором, в котором уже подставлены все аргументы этого конструктора.
== A2. Закодировать типы через <tex> \mu </tex> - комбинатор ==  '''data''' Return a b = List (Return b a) (Return b a) b | Roll (Return a a) (Return a a) (Mice a) '''data''' Mice a = Bucket (Mice a) (Return a a) | Haystack (Mice a) a === Решение === <font color=magenta> '''Магия как в E2!''' </font> Опять делаем соотвествие между TypeName и TypeName'. Чтобы написать TypeName', необходимо преобразовать объявление дататипов по Чёрчу следующим правилам:* сначала идёт mu (это как fix, только для типов),* потом какая-нибудь уникальная буква для типа (например x для Return и y для Mice),* после точки абстракция, которая сначала принимает в качестве аргумента другую уникальную букву, а затем аргументами параметры типа,* T1 | T2 заменяется на T1 + T2,* T1 T2 заменяется на T1 <tex> \times </tex> T2,* параметры типа оставляем как есть,* если в конструкторе идёт наш тип, то пишем нашу уникальную букву, а затем уникальную букву другого типа, а если другой типа {{---}} наоборот; после чего параметры конструктора,* если тип не наш и не буковка параметр датайпа, и не принимает параметров (с взаимной рекурсиейнапример Nothing) , то пишем 1 вместо неё.  Return' =mu x . \ y . \ a b . (x y b a) <tex> \times </tex> (x y b a) <tex> \times </tex> b + (x y a a) <tex> \times </tex> (x y a a) <tex> \times </tex> (y x a) Mice' =mu y . \ x . \ a . (y x a) <tex> \times </tex> (x y a a) + (y x a) <tex> \times </tex> a После этого пишем ответ:
): Return = Return' Mice' Mice = Mice' Return'
== H1. Написать Haskell-код какой-нибудь структуру данных ==
* [[АВЛ-дерево]]: [http://pastie.org/private/qbiu60aetjm9zrpqzrow ссылка на pastie]*: почему я не знал Haskell, когда это дерево было в лабе по дискретке на первом курсе? ;( просто списывается с конспекта один в один...* [[Квадродеревья | Квадродерево]]: [http://pastiepastebin.org/privatecom/sf1vdmrpe7ifvqgdongwq jV4DeRvv ссылка на pastiepastebin]
*: не совсем то, что требует Ян, но я пока не распарсил то, что он требует; возможно, более правильная версия появится позже
#* [https://github.com/itanf/ITMO-Training-FunctionalProgramming/blob/master/ITMOPrelude/Primitive.hs Primitive.hs]
#* [https://github.com/itanf/ITMO-Training-FunctionalProgramming/blob/master/ITMOPrelude/List.hs List.hs]
 ==Primitive=====Nat=Натуральные числа== data Nat = Zero | Succ Nat deriving (+.) (-.) (Show,Read*.) <font color=green  divides :: Nat ->Nat -> Bool ===Rat=== data Rat (%+) (%- Определение натуральных чисел<) (%*) (%/font>)  natZero euler :: ? == Zero <font colorList=green= ===Угадайка===Дают тип, надо написать название функции из '''List.hs''' и реализовать её. ===Комбинаторика=== '''Тут можно использовать только набор заранее определённых функций листа( среди которых нет даже ''++'' )'''  subsequences :: [a] ->[ [ a ] ]  permutations :: [a] -- 0</font>[ [ a ] ]  natOne = Succ Zero <font color=greenAlgebra== class Monoid a where mempty :: a mappend :: a ->a -- 1</font>a
natCmp class Monoid a => Group a where ginv :: Nat -> Nat -> Tri <font color=green>-a - Сравнивает два натуральных числа</font> natCmp Zero Zero = EQ natCmp Zero (Succ _) = LT natCmp (Succ _) Zero = GT natCmp (Succ n) (Succ m) = natCmp n ma
natEq mconcat :: Nat -> Nat -> Bool <font color(Monoid a) =green>List a -- n совпадает с m</font>a natEq Zero Zero = True natEq Zero (Succ _) = False natEq (Succ _) Zero = False natEq (Succ n) (Succ m) mconcat = natEq n mfoldr mappend mempty
natLt :: Nat -> Nat -> Bool <font color=green>-- n меньше m</font> natLt Zero Zero = False natLt Zero (Succ m) = Trueinstance Monoid Unit where natLt (Succ n) Zero mempty = FalseUnit natLt (Succ n) (Succ m) mappend _ _ = natLt n mUnit
infixl 6 +. <font color=green>-- Сложение для натуральных чисел</font> (+.) :: Nat -> Nat -> Nat Zero +. m = minstance Group Unit where (Succ n) +. m ginv _ = Succ (n +. m)Unit
infixl 6 -. <font colorinstance (Monoid a, Monoid b) =green>-- Вычитание для натуральных чисел</font> Monoid (-.Pair a b) :: Nat -> Nat -> Natwhere Zero -. _ mempty = ZeroPair mempty mempty n -. Zero mappend a b = nPair {fst = fst a `mappend` fst b, (Succ n) -. (Succ m) snd = n -. msnd b `mappend` snd b}
infixl 7 *. <font colorinstance (Monoid a) =green>-- Умножение для натуральных чисел</font> Monoid (*.Maybe a) :: Nat -> Nat -> Natwhere Zero *. m mempty = ZeroJust mempty mappend (Succ nJust a) *. m = m +. (n *. mJust b)= Just $ mappend a b mappend _ _ = Nothing
natDivMod newtype First a = First { getFirst :: Nat -> Nat -> Pair Nat Nat <font color=green>-- Целое и остаток от деления n на m</font> natDivMod n m = if (n natLt m) then Pair Zero n else Pair (Succ div) mod where Pair div mod = ((n -. m) natDivMod m)Maybe a}
natDiv n instance Monoid (First a) where mempty = First Nothing mappend (First Nothing) x = x mappend x _ = x newtype Last a = Last { getLast :: Maybe a} instance Monoid (Last a) where mempty = Last Nothing mappend x (Last Nothing) = x mappend _ x = x newtype Any = Any { getAny :: Bool } instance Monoid Any where mempty = Any False mappend (Any a) (Any b) = Any $ a || b newtype All = All { getAll :: Bool } instance Monoid All where mempty = fst . natDivMod n <font colorAll True mappend (All a) (All b) =green>All $ a && b -- Целое</font>Лексикографическое сравнение instance Monoid Tri where mempty = EQ mappend LT _ = LT mappend EQ a = a mappend GT _ = GT newtype Sum a = Sum { getSum :: a } natMod n instance Monoid (Sum Nat) where mempty = Sum natZero mappend (Sum a) (Sum b) = snd Sum $ a +. natDivMod n <font colorb newtype Product a = Product { getProduct :: a } instance Monoid (Product Nat) where mempty = Product natOne mappend (Product a) (Product b) = Product $ a *. b instance Monoid (Sum Int) where mempty = Sum intZero mappend (Sum a) (Sum b) = Sum $ a .+. b instance Group (Sum Int) where ginv = Sum . intNeg . getSum instance Monoid (Product Int) where mempty = Product intOne mappend (Product a) (Product b) = Product $ a .*. b instance Monoid (Sum Rat) where mempty = Sum ratZero mappend (Sum a) (Sum b) = Sum $ a %+ b instance Group (Sum Rat) where ginv = Sum . ratNeg . getSum instance Monoid (Product Rat) where mempty = Product ratOne mappend (Product a) (Product b) = Product $ a %* b instance Group (Product Rat) where ginv = Product . ratInv . getProduct instance Monoid (List a) where mempty = Nil mappend = (++) ==Categories==green>-- Остаток</font>
class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c class Functor f where fmap :: (a -> b) -> f a -> f b class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a class (Functor f) =Целые числа> Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b class Functor m => MonadJoin m where returnJoin :: a -> m a join :: m (m a) -> m a data Identity a = Identity a runIdentity a = a instance Monad Identity where return x = Identity x (Identity x) >>= f =f x data Int Maybe a = Plus Nat Just a | Minus Nat deriving Nothing instance Monad Maybe where Nothing >>= f = Nothing (Show,ReadJust x)>>= f = f x return x = Just x
intZero instance Monad [] where m >>= Plus Zerof intOne = Plus concat (Succ Zeromap f m) intNegOne return x = Minus (Succ Zero)[x]
intNeg class MonadFish m where returnFish :: Int a -> Intm a intNeg (>=>) :: (Plus xa -> m b) = Minus x intNeg -> (b -> m c) -> (Minus xa -> m c) = Plus x
intCmp :: Int -> Int data State s r = State (s -> Tri intCmp (Plus Zeror, s) (Minus Zero) = EQ intCmp (Minus Zero) (Plus Zero) = EQ intCmp (Plus Zero) (Minus (Succ x)) = GT intCmp (Minus Zero) (Plus (Succ x)) = LT intCmp (Plus (Succ x)) (Minus Zero) = GT intCmp (Minus (Succ x)) (Plus Zero) = LT intCmp (Plus x) (Plus y) = natCmp x y intCmp (Minus x) (Minus y) = natCmp y x
intEq :: Int -> Int -> Bool intEq runState (Plus Zero) (Minus Zero) = True intEq (Minus Zero) (Plus Zero) = True intEq (Plus Zero) (Minus (Succ x)) = False intEq (Minus Zero) (Plus (Succ x)) = False intEq (Plus (Succ x)) (Minus Zero) = False intEq (Minus (Succ x)) (Plus Zero) = False intEq (Plus x) (Plus y) = natEq x y intEq (Minus x) (Minus yState f) s = natEq x yf s
intLt :: Int -> Int -> Bool intLt instance Monad (Plus ZeroState s) where return r = State (Minus Zero) = False intLt \s -> (Minus Zeror, s) (Plus Zero) = False intLt (Plus Zero) (Minus (Succ State x)) >>= f = FalseState h intLt (Minus Zero) (Plus (Succ x)) where h s0 = True intLt let (Plus (Succ x)) (Minus Zeror1, s1) = Falsex s0 intLt (Minus (Succ x)) (Plus Zero) State g = Truef r1 intLt (Plus x) (Plus yr2, s2) = natLt x yg s1 in intLt (Minus x) (Minus yr2, s2) = natLt y x
infixl 6 .+newtype IdentityCPS a = IdentityCPS {runIdentityCPS :: forall r ., .-. (.+.) :: Int a -> Int r) -> Int (Plus m) .+. (Plus n) = Plus (m +. n) (Minus m) .+. (Minus n) = Minus (m +. n) (Plus (Succ m)) .+. (Minus (Succ n)) = (Plus m) .+. (Minus n) (Minus (Succ m)) .+. (Plus (Succ n)) = (Plus m) .+. (Minus n) x .+. (Plus Zero) = x x .+. (Minus Zero) = x (Plus Zero) .+. y = y (Minus Zero) .+. y = yr}
(.-.) caseIdentityCPS :: Int IdentityCPS a -> Int (a -> r) -> Intr n .caseIdentityCPS = \x -> \f -. m = n .+. (intNeg m)> runIdentityCPS x f
infixl 7 .*.constrIdentityCPS :: a -> IdentityCPS a (.*.) :: Int constrIdentityCPS = \a -> Int IdentityCPS $ \f -> Intf a instance Functor IdentityCPS where fmap f ma = IdentityCPS $ \g -> caseIdentityCPS ma (Plus m) .*. \a -> g (Plus nf a) = Plus (m *. n) (Minus m) . instance Applicative IdentityCPS where pure = constrIdentityCPS mf <*. > ma = IdentityCPS $ \g -> caseIdentityCPS ma (Minus n) = Plus \a -> caseIdentityCPS mf (m *. n) \f -> g (Plus mf a ) .*. (Minus n) = Minus (m *. n) instance Monad IdentityCPS where return = constrIdentityCPS ma >>= f = IdentityCPS $ \g -> caseIdentityCPS ma (Minus m) .*. \a -> runIdentityCPS (Plus nf a) = Minus (m *. ng==Рациональные числа== data Rat newtype MaybeCPS r a = Rat Int NatMaybeCPS {runMaybeCPS :: (a -> r) -> r -> r}
ratNeg caseMaybeCPS :: Rat MaybeCPS r a -> Rat(a -> r) -> r -> r ratNeg (Rat caseMaybeCPS = \x y) = Rat (intNeg -> \f -> \g -> runMaybeCPS x) yf g
ratInv justCPS :: Rat a -> RatMaybeCPS r a ratInv (Rat (Plus x) y) justCPS a = Rat (Plus y) xMaybeCPS $ \f -> \g -> f a nothing :: MaybeCPS r a ratInv (Rat (Minus x) y) nothing = Rat (Minus y) xMaybeCPS $ \f -> \g -> g
ratCmp :: Rat instance Functor (MaybeCPS r) where fmap f ma = MaybeCPS $ \g -> Rat \h -> Tri ratCmp caseMaybeCPS ma (Rat \a b) (Rat c d) = intCmp -> g (f a .*. (Plus d)) (c .*. (Plus b))h
ratEq :: Rat instance Applicative (MaybeCPS r) where pure = justCPS mf <*> ma = MaybeCPS $ \g -> Rat \h -> Bool ratEq caseMaybeCPS ma (Rat \a b) (Rat c d) = intEq -> caseMaybeCPS mf (\f -> g $ f a .*. (Plus d)) (c .*. (Plus b)h)h
ratLt :: Rat instance Monad (MaybeCPS r) where return = justCPS ma >>= f = MaybeCPS $ \g -> Rat \h -> Bool ratLt caseMaybeCPS ma (Rat \a b) (Rat c d) = intEq -> runMaybeCPS (f a .*. (Plus d)) (c .*. (Plus b)g h)h
internalRatPlus newtype StateCPS s a = StateCPS {runStateCPS :: Rat forall r . s -> Rat (s -> Rat internalRatPlus (Rat a b) (Rat c d) = Rat ((a .*. (Plus d)) .+. (c .*. (Plus b))) (b *. d-> r)-> r}
internalRatShorten caseStateCPS :: Rat -> Rat internalRatShorten (Rat (Plus StateCPS s a) b) = Rat -> (Plus (a /. s -> (gcd s, a b))-> r) (b /. (gcd a b))-> r internalRatShorten (Rat (Minus a) b) caseStateCPS = Rat (Minus \x -> \f -> f $ \s -> runStateCPS x s (\s -> \a /. (gcd a b))) (b /. -> (gcd s, a b))
infixl 7 %+, %- (%+) state' :: Rat (s -> Rat (s, a)) -> RatStateCPS s a n %+ m state' st = internalRatShorten StateCPS $ \s -> \f -> let (internalRatPlus n ms', a)= st s in f s' a
instance Functor (%-StateCPS s) :: Rat where fmap f sa = StateCPS $ \s -> Rat \g -> Rat n %caseStateCPS sa (\st - m > let (s', a) = n %+ st s in g s' (ratNeg mf a))
infixl 7 %*instance Applicative (StateCPS s) where pure a = state' $ \s -> (s, %/a) (% sf <*) :: Rat > sa = StateCPS $ \s -> \g -> Rat caseStateCPS sf (\stf -> Rat let (Rat a bs', f) %* = stf s in caseStateCPS sa (\sta -> let (Rat c ds'', a) = Rat sta s' in g s'' (f a .*. c) (b *. d))
instance Monad (%/StateCPS s) :: Rat where return a = state' $ \s -> (s, a) sa >>= f = StateCPS $ \s -> \g -> Rat caseStateCPS sa (\sta -> Rat n %/ m let (s', a) = n %* sta s in runStateCPS (ratInv mf a)s' g) =Кр4=== deforestation ==Дана функция, необходимо её упростить, пользуясь техникой ''deforestation''. '''Мотивация:''' допустим, есть какая-то функция следующего вида:
==GCD==<code> foldl 0 (*) . filter (> 0) . map (\ x -> 3 * x - 10)</code>
'''Тут я Первый map создаёт новый список, потом filter возвращает ещё список, и так далее. Если функций много (а их вполне может быть сколько угодно), то такой подход перестаёт быть эффективным. Идея в том, чтобы написать функцию, которая делает все необходимые действия "за раз": в данном примере можно рассматривать элемент списка, применять к нему функцию, потом проверять на условие в filter, а потом сразу считать произведение. Иногда можно посмотреть на композицию функций и придумать сразу оптимальный вариант. Это и требуется сделать во втором задании. Но можно и не уверендумать, можем ли использовать ''natMod'' или надо дополнительно реализовывать еёа применить стандартный алгоритм для преобразования, который даёт ответ.<br/>Ещё мы вроде бы не можем использовать дополнительные функции!'''
gcd [http:: Nat -> Nat -> Nat gcd n Zero = n gcd n m = gcd m //www.sciencedirect.com/science/article/pii/030439759090147A По этой ссылке] описаны правила, по которым нужно преобразовывать функцию. Если коротко, то всё сводится к inline'у тел функций, причём мы хотим добиться отсутствия вызовов других функций на месте аргументов внешней функции (natMod n mрекомендуется для начала почитать ссылку, посмотреть правила и пример оттуда).
==Метод Ньютона=Пример ===subsequences== subsequences :: List a -> List (List a) subsequences Nil = Cons Nil Nil subsequences xs = (subseqtoend xs) ++ (subseqtoend (init xs)) where subseqtoend :Будет разобран пример из [https: List a -> List (List a) subseqtoend Nil = Nil subseqtoend (Cons x xs) = (Cons (Cons x xs) (subseqtoend(xs)))//pp.vk.me/c622121/v622121192/ff98/NtvrRei7bR4.jpg фото].
==permutations==<code> permutations :: List a <font color=green>-- дано</font> List (List a) permutations Nil func = Nil permutations foldr (Cons x Nil+) = 0 . map (Cons (Cons \x -> x Nil) Nil* 10) permutations (Cons x xs) <font color= insertAtEveryPosForList (permutations xs) x where insertAtEveryPos :: List a -green> a -> Nat -сначала перепишем композицию в обычную аппликацию для дальнейшей ясности</font> List (List a) insertAtEveryPos str elem Zero func0 l = Cons foldr (insert Zero elem Nil str+) Nil insertAtEveryPos str elem pos = 0 (insertAtEveryPos str elem map (pos \x -. natOne)) ++ (Cons (insert pos elem Nil str> x * 10) Nill)
insertAtEveryPosForList <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: List ys) -> y * 10 : map (*10) ys) '''of''' [] -> 0 (List ax:xs) -> x + (foldr (+) 0 xs) <font color=green>-- применяем преобразование case'a case'ов, то есть выносим внутренний case на первое место</font> func3 l = '''case''' l '''of''' [] -> List (List a)'''case''' [] '''of''' [] -> 0 insertAtEveryPosForList (Cons x Nil:xs) elem = insertAtEveryPos -> x elem + (foldr (length x+) 0 xs)) insertAtEveryPosForList (y:ys) -> ('''case''' (y * 10 : map (*10) ys) '''of''' [] -> 0 (Cons x :xs) -> x + (foldr (+) 0 xs) elem ) <font color= green>-- раскрываем внутренние case'ы: в них pattern-matching сразу срабатывает</font> func4 l = '''case''' l '''of''' [] -> 0 (insertAtEveryPosForList xs elemy:ys) -> 10 * y + (foldr (+) 0 (map (*10) ys)) <font color=green>-- замечаем, что у нас получилось в конце выражение foldr (+ ) 0 (insertAtEveryPos x elem map (length x*10) ys), а это по сути наша функция func0, которую мы раскрывали изначально, поэтому тому куску можно дать другое имя</font> func5 l = '''case''' l '''of''' [] -> 0 (y:ys)-> 10 * y + func5 ys</code>
==А так жеstream fusion ==* Дают тип какого-нибудь foldr и просят написать какой-нибудь foldr.* Написать определения каких-нибудь тайпклассов.* Написать какие-нибудь инстансы.* Доказать эквивалетность каких-нибудь двух определений монады.* CPS-преобразовать какие-нибудь типы.* Написать монадные инстансы для CPS-преобразованных типов.
По сути это то же самое, только вводятся два дополнительных типа, а стандартные функции подстраиваются под них.* [http://code.haskell.org/~dons/papers/icfp088-coutts.pdf Статья]* [http://www2.tcs.ifi.lmu.de/~senjak/haskellbeatsc.pdf Презентация с красивым форматированием (мотивация)]* [http://www.mit.edu/~mtikekar/posts/stream-fusion.html Применение в реальной жизни]* [http://sprunge.us/ZONH Разбор задания с кр] =Кр4=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 \ (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> Забавное, но бесполезное для сдачи ФП, продолжение: Выразим производную. <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> В итоге у нас производная является произведением двух функций, а для типа это значит, что он является произведением двух типов. При умножении на константу у нас будет просто несколько одинаковых конструкторов с разными именами.<code> <font color=green>--сначала распишем производную типа, полученного сразу после дифференцирования (1), если соблюдать исходный порядок аргументов в типах</font> '''data''' DMice a = S (Mice a) a | H a (DMice a) a | M a (Mice a) | Y (DMice a) | A a a | K a a | Shmyak a a</code> Теперь распишем первую скобку в (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 из кр]
1632
правки

Навигация