7

おそらくこれは明らかですが、IO 値の無限リストを最適にフィルタリングする方法がわかりません。簡単な例を次に示します。

infinitelist :: [IO Int]

predicate :: (a -> Bool)

-- how to implement this?
mysteryFilter :: (a -> Bool) -> [IO a] -> IO [a]

-- or perhaps even this?
mysteryFilter' :: (a -> Bool) -> [IO a] -> [IO a]

なんらかの使い方をしなければならないのかもしれませんがsequence、評価はゆるくしてほしいです。助言がありますか？本質は、出力のそれぞれについて、入力のいくつかの値IO Intをチェックする必要があるかもしれないということです。IO Int

ありがとうございました！

4

1 に答える 1

11

などを使わないと無理unsafeInterleaveIOです。2 番目の型シグネチャを使用してフィルターを作成することはできません。

unsafePerformIOBool :: IO Bool -> Bool
unsafePerformIOBool m  = case mysteryFilter' id [m] of
    []    -> False
    (_:_) -> True

同様に、最初の型シグネチャは機能しません。再帰呼び出しは type の何かを返しますが、これからIO [a]リストを作成するには、結果を返す前にこのアクションを実行:する必要があります ( is が含まれていないため) IO を使用する必要があります>>=)。誘導により、結果を返す前に、リスト内のすべてのアクションを実行する必要があります (リストが無限に長い場合、これには永遠に時間がかかります)。

unsafeInterleaveIOこれを解決しますが、安全ではありません。

 mysteryFilter f [] = return []
 mysteryFilter f (x:xs) = do ys <- unsafeInterleaveIO $ mysteryFilter f xs
                             y <- x
                             if f y then return (y:ys) else return ys

問題は、これがモナドが提供するはずのシーケンスを壊してしまうことです。モナド アクションがいつ発生するかについての保証はもうありません (決して発生しないかもしれませんし、複数回発生するかもしれません)。

リストは IO とは相性が悪いです。これが、多数のストリーミング タイプ (反復、コンジット、パイプなど) がある理由です。

そのような最も単純なタイプはおそらく

data MList m a = Nil | Cons a (m (MList m a))

私たちはそれを観察することに注意してください

[a] == MList Id a

以来

toMList :: [a] -> MList Id a
toMList [] = Nil
toMList (x:xs) = Cons x $ return $ toMList xs

fromMList :: MList Id a -> [a]
fromMList Nil = []
fromMList (Cons x xs) = x:(fromMList . runId $ xs)

また、MList はファンクターです

instance Functor m => Functor (MList m) where
  fmap f Nil = Nil
  fmap f (Cons x xs) = Cons (f x) (fmap (fmap f) xs)

そして、それは Functor の変換と Natural 変換のカテゴリの Functor です。

trans :: Functor m => (forall x. m x -> n x) -> MList m a -> MList n a
trans f Nil = Nil
trans f (Cons x xs) = Cons x (f (fmap trans f xs))

これを使えば、あなたが望むものを簡単に書くことができます

mysteryFilter :: (a -> Bool) -> MList IO (IO a) -> IO (MList IO a)
mysteryFilter f Nil = return Nil
mysteryFilter f (Cons x xs)
  = do y <- x
       let ys = liftM (mysteryFilter f) xs
       if f y then Cons y ys else ys

または他のさまざまな同様の機能。

于 2013-03-09T03:56:11.990 に答える