在国家单体上实现递归关系(在哈斯克尔或斯卡拉)

Question

我正在研究运算符的新实现 http://www.thalesians.com/archive/public/academic/finance/papers/Zumbach_2000.pdf编辑：这里更清晰的解释：https://www.olseninvest.com/customer/pdf/paper/001207-emaOfEma.pdf

简而言之，它是一大堆基于指数移动平均线递归关系的很酷的时间序列运算符，其中 ema(( 运算符的每个应用程序都采用新值和 ema 的先前结果。 我似乎不能在这个堆栈交换上做乳胶，但无论如何我现在的问题是一个软件问题。

我在 Scala 中通过将一个 var 隐藏在创建 EMA 函数的 thunks 深处来实现了这一点。 这一切都有效，但它非常棘手，因为再次调用 ema(5( 然后再次调用 ema(5( 自然会导致不同的结果。 我想尝试使用状态Monads重做所有这些，但我很快就迷失在杂草中。

例如，我在哈斯克尔有以下简化的 EMA 状态 monad：

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 应用于初始化为 0 的 5 周期 EMA。 这一切都很好，使用 forM 我可以应用多个输入值等。 现在，下一步是实现"迭代 EMA"，即应用于自身的 N 次 EMA。

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

这些中间 EMA 中的每一个都需要有自己的状态(即先前的结果(，以正确计算迭代 EMA 的向量。 所以，我正在寻找的是这样的东西，(我认为(：

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

它本质上是 EMA 的菊花链：

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

如果我关心的只是第 3 次迭代 EMA......

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

本文从那里开始，创建基于迭代 EMA 及其平均值等构建的更复杂的运算符，因此我希望能够在功能上和纯粹地组合这些有状态运算符，构建更复杂的状态，但仍然非常简单的输入和输出。

我真的觉得这就是函数式编程所擅长的，但我还没有专业知识来了解如何以正确的方式将这些状态 monads 组合在一起。 有人可以用这些迭代的递归运算符为我指出正确的方向吗？

编辑：

一些有用的人建议对输入数据重复应用相同的 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

x 列是原始输入，ema1 使用其左侧作为输入，并且由重复/状态决定。 EMA2 使用其左侧输入(而不是 X！(，并且它由状态决定。 这是一个ema (ema (x( (。 同上 ema3 = ema (ema (ema (x( ( (。 我想做的，我认为一定是可能的，是给出一个ema状态monad，组成ema3状态monad，或者更好的是，[ema]状态monad，每个后续ema都对前一个的输出进行操作。

Answer 1

让我们构建方便的旧 Mealy 机器

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

然后，通过所有这些机器，我们可以创建无限流的迭代 Mealy 机器

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

现在，我们可以根据需要编写这些 EMA

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

Answer 2

更新了答案...

定义：

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])

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 元组或列表。

在您的示例中，首先使用输入x = 1运行(ema3 5)，然后使用输入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 3

我可能没有完全理解您的用例，但您可能正在寻找这样的东西：

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 monad 时，无需将函数包装在 state $ y -> ... 业务中。您可以简单地将 monadic 代码包含在一个 do 块中，并使用 put 和 get 来访问状态。在这种情况下，对于函数的每次递归执行，我用 get 抓取最后一个y，然后在做数学运算后使用 put 来更新状态。

我认为在您的版本中，您包含State monad而实际上没有得到任何东西(因为您不使用put或get(。

此外，State monad 可能为此矫枉过正;您可以使用 x 值列表上的折叠来完成同样的事情。

Answer 4

根据评论进行更新...

可以使用 monadic 绑定运算符编写 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'

(原答案(

这不是一个完整的答案，但也许是OP评论关于这是否朝着正确的方向发展。

以下是我理解的计算结果：

          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>.