Stream Fusion

先简单介绍一下stream fusion吧，stream fusion通过把列表（或其他数据结构）转换成一个通用Stream类型，然后通过rewrite rule消除中间的Stream转换，减少中间数据结构的生成实现了优化。这里我不讲优化，只讲Existential Quantification的使用。

stream-fusion中有两个关键的数据类型（代码简化自stream-fusion 0.1.2.5）：

data Stream a = forall s.
    Stream !(s -> Step a s)  -- a stepper function
    !s                       -- an initial state

data Step a s = Yield a !s
              | Skip    !s
              | Done

我解释一下这两个类型的作用，首先Stream维护了一个状态s和一个steppr函数，stepper :: s -> Step a s能根据一个状态产生一个Step，通过不断调用这个stepper函数就能产生一系列的类型s和输出a。

注意，Stream类型里用了一个Existential quantification，forall s，表示使用Stream a类型的用户是不知道这个s的具体是什么类型，他只知道存在着一个s而已。一个类型不明的数据是完全没用的，所以Stream a还提供了stepper函数，这个函数刚好能接受s类型的参数。这么说当用户有一个Stream a类型的数据时，他能做的就是用这个s调用这个stepper函数，这可能产生一个新的s1（包装在Step里），s1和s的类型是相同的，用户可以继续新状态调用stepper，一直迭代到Done。

一句话总结：状态对用户是透明的，用户不知道具体状态是什么，只能不断产生更多的状态和输出值。

如果不用Existential quantification，能实现同样的效果吗？

data StreamE a s = StreamE !(s -> Step a s) !s

我们同样可以实现自然数流和转换到列表：

nats :: StreamE Int Int
nats = StreamE next 0
  where
    next s = Yield s (s + 1)

toList :: StreamE a s -> [a]
toList (StreamE f s') = loop s'
  where
    loop s =
        case f s of
          Done -> []
          Skip s1 -> loop s1
          Yield a s1 -> a : loop s1

注意这里nats暴露了状态的类型Int，这有什么影响？我们实现一个takeS :: Int -> StreamE a s -> StreamE a s来截取流的前n项。

你要先试试。

经过一番尝试之后，我发现takeS需要维护多一个状态来记录还要取多少个值，即状态的类型是要改变的：

takeS :: Int -> StreamE a s -> StreamE a (s, Int)
takeS n (StreamE f s) = StreamE next (s, n)
  where
    next (s, 0) = Done
    next (s, n) =
        case f s of
          Done -> Done
          Skip s1 -> Skip (s1, n)
          Yield a s1 -> Yield a (s1, n - 1)

这有问题吗？类型难看是个问题，用多了状态类型会越来越大，大到一定程度你就完全不想写类型了：

takeS 10 $ takeS 10 $ takeS 10 $ nats :: StreamE Int (((Int, Int), Int), Int)

第二问题是，用户可以修改状态了：

takeMore :: Int -> StreamE a (s, Int) -> StreamE a (s, Int)
takeMore m (StreamE f (s, n)) = StreamE f (s, n + m)

{--
ghci> toList $ takeMore 5 $ takeS 10 nats
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
--}

这能力真的有必要暴露给用户吗？为了保证流和函数可以放心地组合，每个流的状态都应该要隐藏的。

GHC IO Manager

data Backend = forall a. Backend {
      _beState :: !a

    -- | Poll backend for new events.  The provided callback is called
    -- once per file descriptor with new events.
    , _bePoll :: a                         -- backend state
              -> Timeout                   -- timeout in milliseconds
              -> (Fd -> Event -> IO ())    -- I/O callback
              -> IO ()

    -- | Register, modify, or unregister interest in the given events
    -- on the given file descriptor.
    , _beModifyFd :: a
                  -> Fd     -- file descriptor
                  -> Event  -- old events to watch for ('mempty' for new)
                  -> Event  -- new events to watch for ('mempty' to delete)
                  -> IO ()

    , _beDelete :: a -> IO ()
    }

poll :: Backend -> Timeout -> (Fd -> Event -> IO ()) -> IO ()
modifyFd :: Backend -> Fd -> Event -> Event -> IO ()

GHC在不同OS要用不同的IO事件处理机制（epoll、kqueue之类的），这个Backend就抽象了这些不同的后端。其实和strem-fusion很像，有个类型不明的状态（_beState），还有操做这个状态的函数，不多说了。

Anti-pattern?

Existential quantification很好用，但是有些时候是没必要的，有些可以用其他方法实现，而且扩展性更好。我的理解是，Existential quantification让你不知道具体类型，你只能通过同时声明的那些函数去操作它，就像上面stream-fusion的例子一样，其实你丢失了一些类型信息，放弃了一些功能。等我有了更好的理解再详细写写。

Functions are the masters of reuse: when you use an advanced feature, you need a yet more advanced feature to abstract over it (think: classes < existential types < universally quantified constraints < unknown). But all you need to abstract over a function is another function.

— Luke Palmer

ExistentialQuantification的应用

Stream Fusion

GHC IO Manager

Anti-pattern?

参考