[ruby-dev:40633] Re: Enumerable#interleave

2010年3月14日7:30 Yukihiro Matsumoto <[e-mail]>:
>
> ちょっと調べてみたのですが、Haskellに組み込みであるのではな
> いようです。が、permutationの定義に(自前で定義して)使われて
> いるようです。
>
> -- permutations xs returns the list of all permutations of xs.
> -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
> permutations            :: [a] -> [[a]]
> permutations []         =  [[]]
> permutations (x:xs)     =  [zs | ys <- permutations xs, zs <- interleave x ys ]
>  where interleave          :: a -> [a] -> [[a]]
>        interleave x []     =  [[x]]
>        interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)
>
> はからずもinterleaveのユースケースになってるのかもしれません。

この interleave はその interleave ではないような気がします。

% cat interleave.hs
interleave          :: a -> [a] -> [[a]]
interleave x []     =  [[x]]
interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)
% ghci interleave.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( interleave.hs, interpreted )
Ok, modules loaded: Main.
*Main> interleave 1 [2,3,4]
[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]]

型も a -> [a] -> [[a]] ですが、
今回の interleave なら [a] -> [[a]] -> [a] あたりでしょう。

> |それなら join を使えよ、という気もしますが、join と比較すると
> |* 最後の要素の終わりにもつけられる
> |* 区切りを複数種にできる
> |* 文字列以外にも使える
> |というあたりが利点になるでしょうか。
>
> あと、joinはくっつけて文字列にしてしまうので、それがうれしい
> 時と、うれしくない時があるでしょうね。

文字列以外にも使えるという項目で指摘したつもりでしたが、
そういう用途も検索すると見つかります。
cond の中身を作るとか、マクロ関係が目立つ気がしますが。
http://paste.lisp.org/display/93626
http://s-expressions.com/2010/01/24/conjure-simple-mocking-and-stubbing-for-clojure-unit-tests/

そっちだと比較対象は Enumerable#zip や Array#transpose あたりでしょうか。
flatten(1) も行うから、ネストしたものを扱わなくて済むぶん
頭を使わなくて済むという可能性はあるかなぁ。

あぁ、Hash[k,v,k,v,...] の生成に... ってこれはすでに
Hash[[[k,v],[k,v],...]] で解決されてるか。
もちろん複数の解決があってもいいわけですが。

> 今回の実装では、一番短いEnumerableからの要素を使いきった時点
> で停止します。Clojureもそういう挙動でした。

なるほど。

zip で以前、そのあたりが変わって戻ったような記憶があるんですが、
どうでしたっけ?

> http://code.activestate.com/recipes/511480-interleaving-sequences/
>
> で紹介されているPython版は、なぜか残ったものを取り出し続ける
> 挙動になっていますが、これは使いにくいんじゃないかなあ。

そこで頭の中に浮かんでいる用途を書くのです。

それとも本当に用途を思い浮かべずに使いにくいと感じるんでしょうか。
そうだとしたら書けないかもしれませんが、そうなのかなぁ。
-- 
[田中 哲][たなか あきら][Tanaka Akira]