ちょっと変わったリストのトラバース

Haskellではmapとかfoldl, foldrとか先日のポストへのコメントで教えてもらったmapAccumLやモナドを使ったmapMなどいろんなリストのトラバースの仕方が提供されています。のですが、試しに書いていたCUIのTicTacToe（マルバツですね）のなかで、ライブラリにあるものではうまく表現できないものにぶつかりました。

　何のことはない、表示の部分なんですが、ゲームの状態をIntが９ヶ入ったリストで表現しているのですが、これを３ｘ３の形で表示したい。ということで、[1, 2, 3, 4, 5, 6, 7, 8, 9]を[ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]にしてくれるような関数を書こうと思い立ったわけです…

最初に書いたのはこんなんでした：

splitEvery :: Int -> [a] -> [ [a] ]
splitEvery _ [] = [ [ ] ]
splitEvery i lst = [take i lst] ++ (splitEvery i $ drop i lst)

これだとリスト処理を関数の各イテレーションごとに２回してしまう(takeとdrop)ので、ちょっと気に入りませんでした。色々探していてsplitAt　:: Int -> [a] -> ([a], [a])　を見つけてきたので、次にできたのは

splitEvery :: Int -> [a] -> [ [a] ]
splitEvery _  = 
splitEvery i xs = (xi :splitEvery i xsi)
	where
		(xi, xsi) = splitAt i xs

でした。さらに進めて再帰部分だけを抽出したのがこれ：

varMap :: ([a] -> (b, [a])) -> [a] -> [b]
varMap _  = 
varMap f as = (ai : varMap f asi)
	where
		(ai, asi) = f as

可変長の要素をひとまとまりにしてMapできるのでvarMapという名前にしました。splitEveryを行うには

varMap (splitAt 3) lst

のように使います。リストを3つずつの要素に区切ってそれぞれの合計が出したかったら：

varMap (sumFst.(splitAt 3)) lst
	where
		sumFst (a, b) = (sum a, b)

なんて感じでやれますね…

さらに進めて、せっかくvarMapということで可変長の要素をマップできるといってるのだから、マップの各回ごとに違う長さの要素を取れるようにするにはどうしたらよいか考えてみました。

　varMap f lst

としたときに、ｆの行動が何かの影響を受けて変わるわけですね…lstそのものにfへの指令情報が入っているというのも一つの考え方ですが、StateやmapAccum*のようにステート情報を織り込む方法もありですね…

　varMap :: ([a] -> State s (b, [a])) -> [a] -> State s [b]

みたいにするか、mapAccum風に

　varMap :: ([a] -> c -> (c, b, [a])) -> c -> [a] -> (c, [b])

見たいな感じでしょうか…

ここまで考えて、ちょっとアイディアが浮かびました。ステート情報が関数そのものだったらどうでしょう？再帰も自分で書いてるのだから、わざわざStateモナドを使う必要もない気がします。（既存の関数は皆要素一つ一つに関数を適用するので、varMapの再帰を既存のライブラリ関数で書くことはできないのじゃないかというのが僕の今のところの理解です。いま、Applicativeの説明を読んでいるのですが、ひょっとしたらそっちの方面で何か見えてくるかもしれません...またそれは別に書きたいと思います。）

varMap :: (([a]  -> (f, b, [a]) ) =>f -> [a] -> [b]
varMap _  = 
varMap f as = b : varMap f' as'
	where
		(f', b, as') = f as

見たいなのができたのですが、、これ、コンパイルしません。fの型が決定しないのです…

ｆは自分自身をTripleの第一要素として帰す関数です。ということで、普通に書くと
[a] -> ([a]->([a]->……b, [a]), b, [a]) -> [b]
見たいなことになって、書ききれません…Cでやるリンクリストのように再帰的な型定義はできないものかと試してみました：

type VarMapper = [a] -> (VarMapper, b, [a])
varMap :: VarMapper -> [a] -> [b]
varMap _  = 
varMap f as = b : (varMap f' as')
	where
		(f', b, as') = f as

これは、type宣言がコンパイルしません。Haskell98Reportの４６ページあたりをみると、typeだけではできませんが、dataとtypeを組み合わせれば再帰的な宣言ができるようです。

type Rec a = [Circ a]
data Circ a = Tag [Rec a]

ということで、

type VarMapper a b = [a] -> (VarMapperD a b, b, [a])
data VarMapperD a b = VarMapper (VarMapper a b)

varMap :: (VarMapper a b) -> [a] -> [b]
varMap _ [ ] = [ ]
varMap f as = b : (varMap f' as')
	where
		(VarMapper f', b, as') = f as

と、これでやっとコンパイルするようになりました...タイプコンストラクタとか、名前が乱立して混乱を招きそうです。VarMapperDの名前は隠蔽してしまいたい気分ですね...これをやっているうちに、もう一つ別のアイディアが浮かんできます...ひょっとしてそっちのほうが楽？そのうち試してみよう...

そして、このvarMapの使い方はこんな感じです：

takeLess :: Int -> VarMapper a [a]
takeLess c xs = (VarMapper (takeLess $ c - 1), x, xs'')
	where
		(x, xs') = splitAt c xs
		xs'' = if c == 1 then [] else xs'
		
main = putStrLn.show $ varMap (takeLess 5) [1..20]


> [ [1,2,3,4,5],[6,7,8,9],[10,11,12],[13,14],[15] ]

といった感じです。個人的に少し気に入っているところは、
１．関数の自身がコンテキストを抱えている（takeLess 5がマップを繰り返すたびにtakeLess 4, 3,...と変化していきます。）
２．関数の中でマップの終了を指示出来る。（元のリストは２０までありますが、varMapは１５までで再帰を終了しています。）

いやー、型再帰のあたりで、ひょっとしてこれはダメ？とか思っちゃいましたが、とりあえず動くところまでこぎつけました…もっと簡単にやる方法とかありますかねぇ...

ではでは。