4

標準ライブラリには関数が含まれています

unzip :: [(a, b)] -> ([a], [b])

これを定義する明白な方法は、

unzip xs = (map fst xs, map snd xs)

ただし、これは結果を構築するためにリストを 2 回トラバースすることを意味します。私が疑問に思っているのは、1回のトラバーサルだけでこれを行う方法はありますか?

リストへの追加は高価です - 実際には O(n) です。しかし、初心者なら誰でも知っているように、遅延と再帰を巧みに利用して、再帰呼び出しでリストに「追加」できます。したがって、次のようにzip簡単に実装できます。

zip :: [a] -> [b] -> [(a, b)]
zip (a:as) (b:bs) = (a,b) : zip as bs

ただし、このトリックは、 1 つのリストを返す場合にのみ機能するようです。ソーストラバーサルを複製することなく、複数のリストの末尾を同時に構築できるようにこれを拡張する方法がわかりません。

私は常に、標準ライブラリの が 1 回のトラバーサルでこれを行うことができると想定していました (これは、ライブラリでこの単純な関数を実装することの要点のようなものです) が、実際にどのように機能するかはわかりません。unzip

4

2 に答える 2

7

次のアイデアは、The Beautiful Folderから派生しています。

リストに対して 2 つの折り畳み操作がある場合は、両方の状態を保持したまま折り畳むことで、いつでも一度に実行できます。これを Haskell で表現してみましょう。まず、折りたたみ操作とは何かをキャプチャする必要があります。

{-# LANGUAGE ExistentialQuantification #-}
import Control.Applicative

data Foldr a b = forall r . Foldr (a -> r -> r) r (r -> b)

折り畳み操作には、折り畳み関数、開始値、および最終状態から結果を生成する関数があります。存在量化を使用することで、状態のタイプを隠すことができます。これは、フォールドをさまざまな状態と組み合わせるために必要です。

a をリストに適用するには、適切な引数を指定してFoldr呼び出すだけです。foldr

fold :: Foldr a b -> [a] -> b
fold (Foldr f s g) = g . foldr f s

当然のことながら、Foldrはファンクターであり、ファイナライズする関数にいつでも関数を追加できます。

instance Functor (Foldr a) where
    fmap f (Foldr k s r) = Foldr k s (f . r)

さらに興味深いことに、これはApplicativeファンクタでもあります。実装pureは簡単です。与えられた値を返すだけで、何もフォールドしません。最も興味深い部分は<*>. 両方の折り畳みの状態を保持する新しい折り畳みを作成し、最後に結果を結合します。

instance Applicative (Foldr a) where
    pure x  = Foldr (\_ _ -> ()) () (\_ -> x)
    (Foldr f1 s1 r1) <*> (Foldr f2 s2 r2)
            = Foldr foldPair (s1, s2) finishPair
      where
        foldPair a ~(x1, x2) = (f1 a x1, f2 a x2)
        finishPair ~(x1, x2) = r1 x1 (r2 x2)
    f *> g  = g
    f <* g  = f

(leftaroundabout の回答のように)~タプルに遅延パターン マッチがあることに注意してください。これにより、<*>が十分に怠惰であることが保証されます。

mapこれで、次のように表現できますFoldr。

fromMap :: (a -> b) -> Foldr a [b]
fromMap f = Foldr (\x xs -> f x : xs) [] id

これにより、定義unzipが容易になります。2 つのマップを結合するだけです。1 つは を使用しfst、もう 1 つは を使用しsndます。

unzip' :: Foldr (a, b) ([a], [b])
unzip' = (,) <$> fromMap fst <*> fromMap snd

unzip :: [(a, b)] -> ([a], [b])
unzip = fold unzip'

入力を 1 回だけ (そして遅延して) 処理することを確認できます。

head . snd $ unzip (repeat (3,'a'))
head . fst $ unzip (repeat (3,'a'))

正しい結果が得られます。

于 2013-08-17T12:54:49.533 に答える