10

たとえば、次のような関数がある場合、リストのリストを単一のリストにインターリーブする関数をHaskellでどのように記述できるのでしょうか。

interleavelists :: [[a]] -> [a]

要素をインターリーブできる必要があります。

例：[[1,2,3] [4,5,6] [7,8]] --> [1,4,7,2,5,8,3,6]。

リストは有限または無限の両方にすることができます...使用できますfoldrか？

4

4 に答える 4

28

それを記述する最も簡単な方法は、transposefromを使用することData.Listです。

import Data.List

interleavelists :: [[a]] -> [a]
interleavelists = concat . transpose

transposeは、その引数の空でない各リストの最初の要素を選択し、それらを 1 つのリストに入れ、その後、引数の要素の stransposeのリストを作成します。の結果のリストを作成すると、必要に応じてリストがインターリーブされます。一部の要素リストが無限の場合は機能しますが、リストのリスト自体に無限に多くの要素がある場合、もちろんs のリストを通過することはありません。しかし、とにかくそのケースの処理には問題があります。tailconcattransposehead

foldrリストをインターリーブするために使用するのは簡単ではありません。あなたが持っていたとしましょう

interleavelists xss = foldr something zero xss

interleavelists []おそらく を生成するはず[]なので、それがzero値になります。と

interleavelists [xs] = xs

自然に見えるので、

something xs [] = xs

しかし、2 番目の引数が ではない場合はどうなる[]でしょうか。something次に、さまざまな距離にある の最初の引数の要素を 2 番目の引数に挿入します。しかし、どの距離で？すべてのリストの長さが同じで、各リストの距離が一定である場合、距離を追加のパラメーターとして渡すことができます。

interleavelists = snd . foldr insertAtDistance (0, [])
  where
    insertAtDistance xs (d, ys) = (d+1, helper d xs ys)
    helper _ [] ws = ws
    helper k (b:bs) cs = b : us ++ helper k bs vs
      where
        (us,vs) = splitAt k cs

これはあまりきれいではありません。また、リストがすべて同じ長さでない場合、おそらく目的の出力ではないものが生成されます。しかし、リストがすべて同じ長さであれば、それでうまくいきます。

于 2013-01-06T20:49:49.403 に答える
5

単純な再帰バージョン:

inter :: [[a]] -> [a]
inter [] = []
inter xs = inter2 (filter (\x -> not (null x)) xs)
   where inter2 xs = map head xs ++ inter (map tail xs)

さて、foldrについて...

于 2013-01-06T20:51:25.673 に答える
4

SICP（および後にReasoned Scheme）の陽気な時代にさかのぼる、リストをインターリーブする「標準的な」（またはおそらく有名な）方法は、

infixr 5 ++/

[]     ++/ ys = ys
(x:xs) ++/ ys = x:(ys ++/ xs)

と一緒に使用できますfoldr、

*Main> foldr (++/) [] [[1,2,3],[4,5,6],[7,8]]
[1,4,2,7,3,5,8,6]

これは明らかにあなたが望む順序で結果を生成しませんが、リストの入力リストが無限である場合、OTOHは正常に機能します。入力リストが無限であるかどうかを知る方法がないため、両方の要件を同時に満たす方法はないと思います。

上記の結果は、ダニエルの答えinsertAtDistanceからの関数が、次の代わりに常に距離で挿入するように変更された場合に生成されるものです。1d+1

insertAtDistance xs (d, ys) = (1, helper d xs ys)

それで定義するd+1と、「フラット」インターリーブをfoldr (++/) []生成しますが、スキューインターリーブを生成します。

*Main> take 20 $ foldr (++/) [] [cycle[i] | i<-[1..]]
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3]
于 2013-01-26T15:12:04.447 に答える
2

私たちはあなたが望むことをすることができます 

testList = [[1,2,3],[4,5,6],[7,8]]

interleave l = foldr' (concat [map (\x -> f x idx) l | idx <- [0..]])  
    where
        f x n = if (length(x)<=n) then Nothing else Just (x !! n)
        foldr' (x:xs) = case x of 
                         Nothing -> []
                         Just a  -> (:) a (foldr' xs)

必要に応じてインターリーブ [[1,2,3] [4,5,6] [7,8]] => [1, 4, 7, 2, 5, 8, 3, 6]

于 2013-01-08T13:03:46.463 に答える