逆順ナンバリング

以下のお題をトップダウンでプログラミングしてみよう．

テキストファイルを指定するとそのファイル名と，行番号をふった内容を印字するプログラムを作成せよ．

ただし，ファイルは複数指定できるものとし，行番号は（そのファイルでの）残りの行数を表す数である．

（対象ファイルがn行からなる場合，n-1から0までの番号が降順にふられる．）

ファイル毎にI/O処理をする方針でトップダウンに処理を考えていく．

mainの構成

ファイル毎にI/O処理(revNumFileProc)をすることを表現する

code:haskell

module Main where

import System.Environment (getArgs)

main :: IO ()

main = mapM_ revNumFileProc =<< getArgs

revNumFileProc :: FilePath -> IO ()

revNumFileProc = undefined

トップレベルの名前には必ず型シグネチャを書きます．型シグネチャはプログラマが書くべきプログラムの意図（あるいは仕様）の一部です．revNumFileProcの定義はundefinedとしておきます．このプログラムはghciにロードすると，ghciが定義から推論できる式の型と型シグネチャとが矛盾しないかをチェックしてくれます．すなわち，実際の定義がプログラムの意図を反映しているものになっているかをチェックしてくれるわけです．言い換えると「型推論機構があるから型シグネチャを書く」のです．

上のコードをghciにロードすると成功します．revNumFileProcの定義は書かれていませんが，revNumFileProcの意図（型シグネチャ）は書かれています．ロードに成功したということはrevNumFileProcの意図とmainの定義は矛盾しないことがこれで確かめられたことになります．トップダウンにインクリメンタルに書くときには常にコードの意図が矛盾しない状態を保ちつつ進めます．

revNumFileProcの構成

revNumFileProcは2つのI/O処理

1. ファイル名を印字する

2. ファイル名を用いてファイルの中身を取得しそれに処理を施して結果を印字する

が含まれています．このように同じ対象に別の処理を施すというのは良くあるパターンなのでこれを

code:haskell

pair :: (a -> b, a -> c) -> a -> (b,c)

pair (f,g) x = (f x, g x)

という関数で抽象しておくと便利です．この関数はIFPH（『関数プログラミング入門—Haskellで学ぶ原理と技法』）でも良く使われる関数です．revNumFileProcは2つの処理を(>>)で連結すればいいですよね．

code:haskell

revNumFileProc :: FilePath -> IO ()

revNumFileProc = uncurry (>>) . pair (putFileName, revNumFile)

こんな感じですかね．ここまでで全体以下のようになります．

code:haskell

module Main where

import System.Environment (getArgs)

main :: IO ()

main = mapM_ revNumFileProc =<< getArgs

revNumFileProc :: FilePath -> IO ()

revNumFileProc = uncurry (>>) . pair (putFileName, revNumFile)

putFileName :: FilePath -> IO ()

putFileName = undefined

revNumFile :: FilePath -> IO ()

revNumFile = undefined

-- Utility

pair :: (a -> b, a -> c) -> a -> (b, c)

pair (f,g) x = (f x, g x)

putFileName と revNumFile の構成

putFileName はファイル名を印字し改行すればよいので putStrLn です．

revNumFileの処理は言葉で表せば，

1. 指定されたファイルを読む readFile fn

2. 行に分割 lines

3. 逆ナンバリング revnumbering

4. 行を連結 unlines

5. 印字 putStr

これを右から左を並べて連結したものが revNumFile の定義になります．

code:haskell

revNumFile :: FilePath -> IO ()

revNumFile fn = putStr . unlines . revnumberings . lines =<< readFile fn

ここまでの全体は

code:haskell

module Main where

import System.Environment (getArgs)

main :: IO ()

main = mapM_ revNumFileProc =<< getArgs

revNumFileProc :: FilePath -> IO ()

revNumFileProc = uncurry (>>) . pair (putFileName, revNumFile)

putFileName :: FilePath -> IO ()

putFileName = putStrLn

revNumFile :: FilePath -> IO ()

revNumFile fn = putStr . unlines . revnumberings . lines =<< readFile fn

revnumberings = undefined

-- Utility

pair :: (a -> b, a -> c) -> a -> (b, c)

pair (f,g) x = (f x, g x)

revnumberings の構成

逆ナンバリングは素朴に考えると，テキスト行のリストを反転して，通常のナンバリングをして，またリストを反転すればよい．

code:haskell

revnumberings = reverse . numberings . reverse

code:haskell

numbering :: (Int,String) -> String

numbering (i,s) = printf "%06d: %s" i s

ここで numbering の定義を良くみると

code:haskell

numbering = uncurry (printf "%06d: %s")

です．そうすると，

code:haskell

と定義してもいいわけです．この map (uncurry f) . zip xs というのも良くあるパターンで，実は

code:proof

map (uncurry f) . zip xs = zipWith f xs

が成り立ちます．左辺と右辺のちがいは右辺は中間データとしてのリストを作らないということです．zipWithを使って，

code:haskell

というわけで素朴に実装すると，全体としては以下のようになります．

code:haskell

module Main where

import System.Environment (getArgs)

main :: IO ()

main = mapM_ revNumFileProc =<< getArgs

revNumFileProc :: FilePath -> IO ()

revNumFileProc = uncurry (>>) . pair (putFileName, revNumFile)

putFileName :: FilePath -> IO ()

putFileName = putStrLn

revNumFile :: FilePath -> IO ()

revNumFile fn = putStr . unlines . revnumberings . lines =<< readFile fn

revnumberings = reverse . numberings . reverse

numbering :: Int -> String -> String

numbering = printf "%06d: %s"

-- Utility

pair :: (a -> b, a -> c) -> a -> (b, c)

pair (f,g) x = (f x, g x)

森林伐採（デフォレステーションdeforestation）

前節で「中間データを作らないようにする」という手法を使いましたが，この技法をデフォレステーションといいます．一般には融合変換という技法ですが一般化した技法については今回は省略します．

numberings の行番号をリストとして生成していますがこれもリストとして生成するのではなく，カウンターを用意してこれをインクリメントしていくようにすれば行番号を供給するためにリストを生成する必要がなくなります．これを続けて行うには numbering :: Int -> String -> (Int,String) という，行番号と1行分の文字列を引数としてとり，次の行番号と番号づけした結果の文字列の対を返す関数を考えます．

code:haskell

numbering :: Int -> String -> (Int,String)

numbering i s = (i+1,printf "%06d: %s" i s)

これを以下のような図式で合成します．

code:code

行 : 行 ... : 行 : []

↓ ↓ ↓ ↓

0 → number → 1 → number →...→ n-1 → number → n → number → n

↓ ↓ ↓ ↓

番号++行 : 番号++行 : 番号++行 : []

code:haskell

numberings = snd . mapAccumL numbering 0

しかし，ここまでやったなら revnumberings の定義もなんとかしたいですよね．

code:haskell

revnumberings = reverse . numberings . reverse

2度も中間リストを作っていますからこれを止めたいわけです．さきほどの mapAccumL の反対方向の図式を実現する高階関数があればよさそうです．

code:code

行 : 行 ... : 行 : []

↓ ↓ ↓ ↓

n ← number ← n-1 ← number ←...← 1 ← number ← 0 ← number ← 0

↓ ↓ ↓ ↓

番号++行 : 番号++行 : 番号++行 : []

code:haskell

revnumberings = snd . mapAccumR numbering 0

と定義できます．というわけで少しリファクタリングすれば最終的には以下のようなプログラムになるというわけです．

code:revnumbering.hs

module Main where

import Data.List (mapAccumR)

import System.Environment (getArgs)

import Text.Printf (printf)

main :: IO ()

main = mapM_ revNumFileProc =<< getArgs

revNumFileProc :: FilePath -> IO ()

revNumFileProc = uncurry (>>) . pair (putFileName, revNumFile)

putFileName :: FilePath -> IO ()

putFileName = putStrLn

revNumFile :: FilePath -> IO ()

revNumFile fn = putStr . unlines . revnumberings . lines =<< readFile fn

revnumberings = snd . mapAccumR numbering 0

numbering :: Int -> String -> (Int,String)

numbering i s = (i+1, printf "%06d: %s" i s)

-- Utility

pair :: (a -> b, a -> c) -> a -> (b, c)

pair (f,g) x = (f x, g x)