双方向畳み込み

双方向の畳み込みというのを考えてみた.

 a  ┏━━┓ a' ┏━━┓          ┏━━┓ a''
 → ┃    ┃ → ┃    ┃ → … → ┃    ┃ →
 ← ┃    ┃ ← ┃    ┃ ← … ← ┃    ┃ ←
 c''┗━━┛ c' ┗━━┛          ┗━━┛ c

コードは

fold :: ((a,c) -> b -> (a,c)) -> (a,c) -> [b] -> (a,c)
fold f (a,c) (x:xs) = (a'',c'')
  where 
    (a'',c') = fold f (a',c) xs
    (a',c'') = f (a,c') x
fold _ z _ = z

与えられたリストを2つに分割する関数 halve は

halve :: [a] -> ([a],[a])
halve xs = g (fold f ((xs,xs),[]) xs)
  where
    f ((ys,[ ]),zs) w = ((ys,[]),[])
    f ((ys,ys'),zs) w = ((tail ys,drop 2 ys'),w:zs)
    g ((ys,_),zs) = (zs,ys)

与えられた数値のリストを,平均値とのずれのリストにする.

diffav :: [Double] -> [Double]
diffav (x:xs) = (x-a):ys
  where
   a = s/n
   ((s,n),ys) = fold f ((x,1),[]) xs
   f ((s,n),ys) z = ((s+z,n+1),(z-a):ys)
diffav _ = []