MonadFixの理解のために(1)---fixを考える4

Haskell

decWithMin問題

まだ具体例にこだわります．もうfixから離れている気もしますが，まあ，再帰すなわちfixということで．さて，Otter_OさんのところのArrowの話題ArrowLoopとCircularPrograming - 取り急ぎブログですに関連して（私はArrowって何？の人です）で，面白い問題を見ました．

decMinWith問題

与えられた（整数の）リストの最小値をminとしたときに，そのリストの各要素からminを引いた値からなるリストを作る

こういう問題です．もちろん2パスならほとんど自明なので，1パスで作ることが本質です．

すぐ気がついたのはrepminとの類似性．先頭の要素から順番に何らかの一つの値を「確定させずに」引きながら，そのときまでのリストの最小値を伝達しつつ，最後の要素を処理したらその時点で定まっている「リストの最小値」を引き算してることにすればよいのでしょう．

リストの要素を一個ずつ処理する定番はmapなのでmapの定義を基本にして，「仮の最小値を引きながら」，最小値を不動点として求めて最後にあわせるという方針でいきます．

decWithMin::[Int]->[Int]
decWithMin xs = let (t,m,n) = cp xs (head xs) m in t
                where cp:: [Int]->Int->Int->([Int],Int,Int) 
                      cp [] n m     = ([],n,m)
                      cp (x:xs) n m = let (t,n',m')=cp xs (x `min` n) m
                                      in ((x-m):t,n',m')

トリックはrepminと本質的に同じです．repminは木の各リーフが（まだ確定していない最小）値を持ってくれましたが，今回はそのような「値の格納場所」がないので，引数で持ちまわすことにします．また始めに与える「最小値の候補」はheadで与えます．