Реализации рекуррентных отношений на государственных монадах (в Haskell или Scala)

Question

я работаю над новой реализацией операторов в http://www.thalesians.com/archive/public/academic/finance/papers/Zumbach_2000.pdf EDIT: ясное объяснение здесь: https://www.olseninvest.com/customer/pdf/paper/001207-emaOfEma.pdf

Кратко, это целая куча операторов прохладного временных рядов основанный на рекуррентном соотношении экспоненциальной скользящей средней, где каждое приложение оператора ema() принимает новое значение и предыдущий результат ema. Я не могу сделать латекс в этом обмене стека, но в любом случае моя проблема теперь - проблема программного обеспечения.

Я реализовал это в Scala, сокрыв var глубоко внутри громкоговорителей, которые создают функции EMA. Все это работает, но это супер сложно, потому что вызов ema (5), а затем ema (5) снова, естественно, приведет к другому результату. Я хотел бы попробовать переделать все это, используя State Monads, но я быстро теряюсь в сорняках.

Например, у меня есть следующий упрощенный EMA State монаду в Haskell:

import Control.Monad.State 

type EMAState = Double 
type Tau = Double 

ema :: Tau -> Double -> State EMAState Double 
ema tau x = state $ \y -> 
    let alpha = 1/tau 
     mu = exp(-alpha) 
     mu' = 1 - mu 
     y' = (mu * y) + (mu' * x) 
    in (y', y') 

, которые можно легко проверить в GHCI:

*Main Control.Monad.State> runState (ema 5 10) 0 
(1.8126924692201818,1.8126924692201818) 

применяя вход 10 к 5-период EMA инициализируется до 0. Это все хорошо и полезно, используя forM. Я могу применять несколько входных значений и т. д. Теперь следующий шаг - реализовать «повторенную EMA», которая является EMA, применяемой к себе N раз.

iEMA[n](x) = EMA(iEMA[n-1](x)) 

Каждый из этих промежуточных ЕМА должны иметь свое собственное государство, иначе предыдущий результат, чтобы правильно рассчитать вектор итерированными ЕМА. Итак, что я ищу, это то, что, как это (я думаю):

iema :: Int -> Tau -> Double -> State [EMAState] [Double] 

который является по существу ромашка цепь ЕМА:

iEMA[3](x) = EMA(EMA(EMA(x,s1),s2),s3) = (x, [s1,s2,s3]) -> ([y1,y2,y3], [s1',s2',s3']) 

А если мне все равно это о третья итерация ЕМА ...

... -> (y3, [s1', s2', s3']) 

бумага движется оттуда, создавая все более сложные операторы, построенные на итеративных ЕМА и средние из них и т.д., поэтому я хочу, чтобы иметь возможность функционально и просто компоновать с учетом состояния OPERAT ors, создавая все более сложные состояния, но все же довольно простой ввод и вывод.

Я действительно чувствую, что это функциональное программирование, но у меня еще нет опыта, чтобы увидеть, как правильно собрать эти государственные монады. Может ли кто-нибудь указать мне в правильном направлении с этими повторными операторами повторения?

EDIT:

Несколько полезных людей, которые предложили повторное применение одного и того же оператора EMA к входным данным, но это не является достаточным. Каждый оператор ema должен поддерживать свое прежнее значение. Вот пример:

tau 5    
mu 0.818730753    
muprime 0.181269247    
     ema1 ema2 ema3  
    x 0  0  0  <- States_0 
    1 0.1812 0.03285 0.00595 <- States_1 
    5 1.0547 0.21809 0.04441 <- States_2 

В столбце х представляет собой необработанные входные данные, EMA1 использует его влево для ввода, и это до рецидива/состояния. ema2 использует свой левый для ввода (не x!), и он находится в состоянии. Это ema (ema (x)). Точно ema3 = ema (ema (ema (x))).То, что я хотел бы сделать, что, по моему мнению, должно быть возможным, дано монадой государства ema, сочинить монаду государства ema3 или, еще лучше, монаду государства [ema] с каждой каждой последующей ema, действующей на выходе предыдущего.

Answer 1

Обновленный ответ ...

Определение:

combine :: [ a -> State s a ] -> a -> State [s] a 
combine fs a = state $ \ys -> 
    let zs = zipWith (\f y a -> runState (f a) y) fs ys 
     pairs = chain a zs 
     as' = map fst pairs 
     a' = last as'   -- we are only returning one result in this case 
     ys' = map snd pairs 
    in (a', ys') 

chain :: a -> [ a -> (a,s) ] -> [ (a,s) ] 
chain a [] = [] 
chain a (f:fs) = let (a',s) = f a 
       in (a',s) : chain a' fs 

ema3 t = combine $ replicate 3 (ema t) 

ghci> runState (ema3 5 1) [0,0,0] 
(5.956242778945897e-3,[0.18126924692201818,3.2858539879675595e-2,5.956242778945897e-3]) 

ghci> runState (do ema3 5 1; ema3 5 5) [0,0,0] 
(4.441089130249448e-2,[1.0547569416524334,0.21809729359983737,4.441089130249448e-2]) 

The combine легко модифицируется, чтобы вернуть все результаты - просто вернуть as' вместо a'.

Оригинальный ответ:

combine :: (a -> State s b) -> (b -> State t c) -> (a -> State (s,t) c) 
combine f g a = state $ \(s,t) -> 
    let (b,s') = runState (f a) s 
     (c,t') = runState (g b) t 
    in (c,(s',t')) 

Тогда:

ema3 tau = ema tau `combine` ema tau `combine` ema tau 

и em3 имеет вид:

ema3 :: Tau -> Double -> State ((EMAState, EMAState), EMAState) Double 

Например:

ghci> runState (ema3 5 1) ((0,0),0) 
(5.956242778945897e-3,((0.18126924692201818,3.2858539879675595e-2),5.956242778945897e-3)) 

Обратите внимание, что тип состояния ema3 - ((Double,Double),Double), а не 3-х кортеж или список.

В вашем примере вы запускаете (ema3 5) первый вход с x = 1, а затем с входом x = 5 с начальным состоянием ((0,0),0):

ghci> runState (do ema3 5 1; ema3 5 5) ((0,0),0) 
(4.441089130249448e-2,((1.0547569416524334,0.21809729359983737),4.441089130249448e-2)) 

и что дает вторую строку в таблице.

Answer 2

не может быть полностью понять ваш случай использования, но, возможно, вы ищете что-то вроде этого:

ema' _ [] = get >>= return 
ema' tau (x:xs) = do 
    y <- get 
    let alpha = 1/tau 
     mu = exp $ negate alpha 
     mu' = 1 - mu 
     y' = (mu * y) + (mu' * x) 
    put y' 
    ema' tau xs 

Это как исходная функция, кроме него принимает список x значений, и она рекурсивно выполняется для каждого, обновляя y каждый раз. Когда ни один не оставлен, он возвращает значение y в качестве ответа.

Он может работать следующим образом:

*Main> evalState (ema' 5 [10]) 0 
1.8126924692201818 
*Main> evalState (ema' 5 [10, 10]) 0 
3.2967995396436076 
*Main> evalState (ema' 5 [10, 10, 10]) 0 
4.511883639059737 

При использовании State монады, вам не нужно, чтобы обернуть свои функции в state $ \y -> ... бизнесе. Вы можете просто заключить свой монадический код в блок do и использовать put и get для доступа к состоянию. В этом случае для каждого рекурсивного выполнения функции я беру последние y с get, а затем использую put после выполнения математики для обновления состояния.

Я думаю, что в вашей версии вы включаете монаду State, фактически ничего не получая для этого (так как вы не используете put или get).

Кроме того, монада State может быть излишней для этого; вы можете выполнить одно и то же, используя сгиб над списком значений x.

Answer 3

Обновления на основе комментариев ...

Три итерации ema можно записать с помощью монадического оператора связывания >>= как это:

ema3 tau x = ema tau x >>= ema tau >>= ema tau 

или с помощью Клейли стрелок:

ema3 tau = ema tau >=> ema tau >=> ema tau 

В качестве диаграммы вычисление происходит следующим образом:

  y1   /---------\ 
      |   |   | 
      v   |   v 
    x --> EMA --> EMA --> EMA --> x' = y3' 
      tau  tau  tau 
      |  ^  | 
      |   |   v 
      \----------/   y3' 

(Original ответ)

Это не полный ответ, но, возможно, ОП комментарий на ли это происходит в правильном направлении.

Вот что я понимаю, вычисление выглядит следующим образом:

  y1   y2  y3 
      |   |   | 
      v   v   v 
    x --> EMA --> EMA --> EMA --> x' 
      tau1  tau2  tau3 
      |   |   | 
      v   v   v 
      y1'  y2'  y3' 

Вопрос заключается в том, есть ли элегантный способ выразить это в виде композиции EMA блоков, например что-то вроде:

ema tau1 >o> ema tau2 >o> ema tau3 

для некоторого оператора >o>.

Answer 4

Давайте создадим удобную старую Мили машины

data Mealy i o where 
    Mealy :: (i -> s -> (i, s)) -> s -> Mealy i o 

, который имеет все виды экземпляров

instance Arrow Mealy 
instance ArrowChoice Mealy 
instance ArrowApply Mealy 
instance Strong Mealy 
instance Choice Mealy 
instance Profunctor Mealy 
instance Category * Mealy 
instance Monad (Mealy a) 
instance Functor (Mealy a) 
instance Applicative (Mealy a) 
instance Pointed (Mealy a) 

Мы можем использовать его, чтобы построить рекуррентные соотношения

recur :: (a -> a -> a) -> a -> Mealy a a 
recur f a0 = Mealy (\inp prior -> let post = f inp prior in (post, post)) a0 

мы можем перебирать их с нашим Category экземпляром

iter :: Int -> Mealy a a -> Mealy a a 
iter 0 _ = id 
iter 1 m = m 
iter n m = m >>> iter (n-1) m 

, а затем, со всей этой техникой, мы можем создать бесконечный поток повторных Мили машин

data Stream a = Stream a (Stream a) deriving Functor 

instance Functor Stream 
instance Applicative Stream 
instance Foldable Stream 
instance Traversable Stream 

ints :: Stream Int 
ints = go 0 where go n = Stream n (go $ n + 1) 

jet :: Mealy a a -> Stream (Mealy a a) 
jet m = fmap (`iter` m) ints 

Все это вместе дает нам, по существу, желаемую структуру. Но с ним трудно взаимодействовать напрямую. Мы дадим ему свои экземпляры, чтобы помочь

newtype MealyJet i o = MealyJet { runMealyJet :: Stream (Mealy i o) } 

instance Profunctor MealyJet 
instance Applicative (MealyJet i) 

instance Category MealyJet where 
    id = MealyJet (pure id) -- technically this should be `jet id`, but it's equal to pure 
    MealyJet f . MealyJet g = MealyJet (liftA2 (.) f g) 

viewMealyJet :: MealyJet i o -> Mealy i (Stream o) 
viewMealyJet (MealyJet m) = sequenceA m 

И теперь мы можем записать эти ЕМА при необходимости

type Tau = Double 

ema :: Tau -> Mealy Double Double 
ema tau = recur $ \fresh prior -> 
    let alpha = 1/tau 
     mu = exp (negate alpha) 
     mu' = 1 - mu 
    in (mu * y) + (mu' * x) 

emaJet :: Tau -> MealyJet Double Double 
emaJet = MealyJet . jet . ema 

emaComp :: MealyJet Double Double 
emaComp = emaJet 1 >>> emaJet 2 >>> emaJet 3 >>> emaJet 4 >>> emaJet 5 

fiveStack :: Mealy Double (Stream Double) 
fiveStack = viewMealyJet emaComp