並列flatten

[KISHIMOTO, Makoto]

きしもとと申します。疑問な事項が2つありまして、相談に乗っていただけたら
と思います。

(1) リストのリストがあって、その各リストを単純にconcatするのではなく、
1個ずつ順番に取って並べていくようなflattenがあったら便利かな、と思った
のですが（各リストが無限のストリームとか）、標準とかにはなっていない
ようなのは、何か原理的な問題があるのでしょうか。

簡単には以下のような実装になるかと思います。

> parFlatten :: [[a]] -> [a]
> parFlatten = parFlattenLoop []
> where
> parFlattenLoop [] [] = []
> parFlattenLoop tmp [] = parFlattenLoop [] (reverse tmp)
> parFlattenLoop tmp ([]:xss) = parFlattenLoop tmp xss
> parFlattenLoop tmp ((x:xs):xss) = x : parFlattenLoop (xs:tmp) xss

実行例:
> parFlatten [[0,1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19],[20,21,22,23,24,25,26,27,28,29]]
--> [0,10,20,1,11,21,2,12,22,3,13,23,4,14,24,5,15,25,6,16,26,7,17,27,8,18,28,9,19,29]

(2) 上の実装だとreverseを使っているのを、なんとか除去しようとしたところ
謎な動作にぶつかってしまいました。以下のように書けば意図どおり動くの
ですが、

> parFlatten2 :: [[a]] -> [a]
> parFlatten2 lst = result
> where
> (result, tmp) = parFlattenLoop tmp lst
> parFlattenLoop y [] = (r, [])
> where
> (r, t)
> | null y = ([], undefined)
> | otherwise = parFlattenLoop t y
> parFlattenLoop y ([]:xss) = parFlattenLoop y xss
> parFlattenLoop y ((x:[]):xss) = (x:r, t)
> where
> (r, t) = parFlattenLoop y xss
> parFlattenLoop y ((x:xs):xss) = (x:r, xs:t)
> where
> (r, t) = parFlattenLoop y xss

ここで、ガードを使って振り分けている部分は、パターンマッチに書き換える
ことができそうに見えるのに、実際に次のように書き換えると、無限ループに
はまってしまっているように見える動作をするようになってしまいます。

> parFlattenLoop [] [] = ([], [])
> parFlattenLoop y [] = (r, [])
> where
> (r, t) = parFlattenLoop t y

どうして違ってしまうのでしょうか？

[Nobuo Yamashita]

(1) parFlatten = concat . transpose じゃだめですか？

(2) (r, t) = parFlattenLoop t y の右辺の関数適用の際に t でパターン照合が起こるからでは？

--nobsun

2016年3月17日 19:43 KISHIMOTO, Makoto <ksma...@dd.iij4u.or.jp>:

--
このメールは Google グループのグループ「haskell-jp」の登録者に送られています。
このグループから退会し、グループからのメールの配信を停止するには haskell-jp+...@googlegroups.com にメールを送信してください。
その他のオプションについては、https://groups.google.com/d/optout にアクセスしてください。