tailDropWhile - HaHaHa!

複数行からなるテキストデータを処理するとき，行末の空白を除去したいときがある．

rmTailSpaces :: String -> String
rmTailSpaces = unlines . map chop . lines

1行分の文字列を末尾の空白を取り除いた文字列に変換する関数chopの実装を考えてみよう．素朴に実装するなら

chop :: String -> String
chop = reverse . dropWhile isSpace . reverse

この実装は単純で，正しいことが一目でわかる．さてこれを一般化すると「指定した条件を満す要素をリストの末尾から除去する」ということになる．Preludeには「指定した条件を満す要素をリストの先頭から除去する」dropWhileという関数がある．これに因んでid:kazu_yamamotoさんがtailDropWhileと命名したようなのでここでもそれを採用しよう．

tailDropWhile :: (a -> Bool) -> [a] -> [a]
tailDropWhile p = reverse . dropWhile p . reverse

tailDropWhileを使ってchopを書きなおすと

chop :: String -> String
chop = tailDropWhile isSpace

となる．さて，上のtailDropWhileの定義では前後にreverseが使われているが．これは「あんまりな」気がする．reverseの実装は左畳み込み（foldl）で定義されているので，元のリストをすべて辿りおわった後でないと結果の値（WHNF）が得られない．したがって他の計算と組み合せたときに遅延評価と恩恵や，融合変換による最適化の恩恵が得られない．そこで reverse版のtailDropWhileを右畳み込みfoldrを使った版に書き換えてみよう．

畳み込み第3双対定理

なんか，かっこよくないですか．

閑話休題．Bird先生のIntroduction To Functional Programming, 2nd Edition (Prentice Hall Series in Computer Science)によれば，リスト上の畳み込み演算には3つの双対定理があるが，その3つめがこれ．

  foldr f e = foldl (flip f) e . reverse

ということは，reverse . dropWhile p を foldl f で表現できれば，
tailDropWhile p = foldl f . reverse なので，
tailDropWhile p = foldr (flip f) [] と定義できる．

reverse . dropWhile p の意味は全部を反転の対象にせず，先頭からいくつか落してから反転という意味である．reverse は foldl で定義されており，リストを先頭から辿ってそれを FILO つまりスタックに積んでいって（蓄積して），積むものがなくなれば，積んだものそれが答である．したがって，これを融合すると，リストを辿って，スタックが空状態のときに，条件を満す要素が来たら捨てて，スタックにすでに何か積まれているかまたは条件を満す要素がこなかったらそのままスタックに積むとやればよいのである．したがって，

tailDropWhile p = foldl f [] . reverse
  where
    f a x | null a && p x = a
          | otherwise     = x:a

と定義できるから

tailDropWhile p = foldr g []
  where
    g x a | p x && null a = a
          | otherwise     = x:a

g の局所定義でガード部 && のオペランドを入れ換えたのは g が第2引数に対して「常に正格」にはならないようにするためである．