Haskell Quiz No.9

難易度: λλ

以下の2つのコードのうち、1つめはコンパイルできますが、2つめはコンパイルできません。

なぜでしょう!

#!/usr/bin/env stack
-- stack script --resolver lts-11.16
import Conduit

main :: IO ()
main = print $ runConduitPure $ return () .| do
  mapM_ leftover [1..10]
  sinkList
#!/usr/bin/env stack
-- stack script --resolver lts-11.16
import Conduit

main :: IO ()
main = print $ runConduitPure $ do
  mapM_ leftover [1..10]
  sinkList

エラーメッセージ

error:
    • No instance for (Num ()) arising from the literal ‘1’
    • In the expression: 1
      In the second argument of ‘mapM_’, namely ‘[1 .. 10]’
      In a stmt of a 'do' block: mapM_ leftover [1 .. 10]

    mapM_ leftover [1..10]

答えは次回

はじめに

前回の問題と答えは以下の通りです。

問題

難易度: λλλ

以下の Conduit を使ったコードの実行結果を予想してみてください!

#!/usr/bin/env stack
-- stack script --resolver lts-11.3
import Conduit

main :: IO ()
main = print $ runConduitPure $ return () .| do
  mapM_ leftover [1..10]
  sinkList

こたえ

実際に実行してみましょう!

$ ./Quiz8.hs
[10,9,8,7,6,5,4,3,2,1]

leftover[1..10] を与えたのに、なぜか逆順になってしまいましたね。

解説

この問題で抑えておきたいポイントは leftover の動作についてです。

問題の例を上記のように leftover ではなく sourceList を使うように修正した場合、プログラムの実行結果は次のようになります。

#!/usr/bin/env stack
-- stack script --resolver lts-11.3
import Conduit
import Data.Conduit.List

main :: IO ()
main = print $ runConduitPure $ sourceList [(1::Int)..10]
                             .| sinkList
[1,2,3,4,5,6,7,8,9,10]

入力として与えたリストの順番がきちんと保存されています。

この挙動を理解するためには Conduit の内部をちょっとだけみていく必要があります。

定義の確認

まずは sourceList, yield, leftover の定義を確認してみましょう。

sourceList :: Monad m => [a] -> ConduitT i a m ()
sourceList = Prelude.mapM_ yield

yield :: Monad m => o -> ConduitT i o m ()
yield    o = ConduitT $ \rest -> HaveOutput (rest ()) o

leftover :: i -> ConduitT i o m ()
leftover i = ConduitT $ \rest -> Leftover   (rest ()) i

yeldleftover はほとんど同じ関数です。本質的に異なる点は HaveOutputLeftover という構成子の違いだけです。

しかし、この違いが今回のような違いを生み出します。

次に、runConduitPure 関数の定義を確認します。

runConduitPure :: ConduitT () Void Identity r -> r
runConduitPure = runIdentity . runConduit

runConduit :: Monad m => ConduitT () Void m r -> m r
runConduit (ConduitT p) = runPipe $ injectLeftovers $ p Done

injectLeftovers が今回の問題で一番重要な関数です。

injectLeftovers 関数

injectLeftovers 関数の定義は以下のとおりです。

injectLeftovers :: Monad m => Pipe i i o u m r -> Pipe l i o u m r
injectLeftovers = go []
  where
    go ls (HaveOutput p o) = HaveOutput (go ls p) o
    go (l:ls) (NeedInput p _) = go ls $ p l
    go [] (NeedInput p c) = NeedInput (go [] . p) (go [] . c)
    go _ (Done r) = Done r
    go ls (PipeM mp) = PipeM (liftM (go ls) mp)
    go ls (Leftover p l) = go (l:ls) p

go が少しごちゃごちゃしていますが、実際に着目すべきポイントは以下の行です。

injectLeftovers :: Monad m => Pipe i i o u m r -> Pipe l i o u m r
injectLeftovers = go []
  where
    ...
    go ls (Leftover p l) = go (l:ls) p

go 関数の第一引数の lsleftover によって上流に戻される値を保存しておくための蓄積変数です。

ここで mapM_ leftover [1..10] はこんなような形をしているパイプです。

p = Leftover (Leftover (Leftover nextPipe 3) 2) 1

mapM_ leftover [1..10] のときに、ls が逆順になっていることを確認するため、実際に go 関数を簡約してみます。

go [] p
  = go [] (Leftover (Leftover (Leftover p 3) 2) 1)
  = go (1:[]) (Leftover (Leftover p 3) 2)
  = go (2:(1:[])) (Leftover p 3)
  = go (3:(2:(1:[]))) p

ここで leftover した値が逆順で蓄積され、次のパイプに渡されることになります。

今回の例では、次のパイプは sinkList となっていました。実装は次のようになっています。

sinkList :: Monad m => ConduitT a o m [a]
sinkList = loop id
  where
    loop front = await >>= maybe (return $ front []) (\x -> loop $ front . (x:))

await :: Monad m => Consumer i m (Maybe i)
await = ConduitT $ \f -> NeedInput (f . Just) (const $ f Nothing)

awaitNeedInput になっていますね。

これは injectLeftoversgo ではこのようにパターンマッチしていました。

go (l:ls) (NeedInput p _) = go ls $ p l
go [] (NeedInput p c) = NeedInput (go [] . p) (go [] . c)

つまり、先に leftover で積んだ値を全て消費してから、上流に対して値を要求します。

おわりに

  • leftover を使えば任意の値を上流に返すことができる。(実際には消費した値を返すことが多いと思う)
  • 値を1つだけ上流に返す場合は特に気にすることは無い
  • 一度にまとめて複数の値を返そうとすると、処理の順番が変わってしまうことがあるので注意が必要

以上です。