haskell - 在 haskell 中实现 channel ——解决尴尬的小队问题

Question

论文中Tackling the awkward squad ，Simon Peyton Jones 提供了 Channel 的“可能实现”。

type Channel a = (MVar (Stream a) , -- Read end
                  MVar (Stream a) ) -- Write end (the hole)

type Stream a = MVar (Item a)

data Item a = MkItem a (Stream a)

现在，他实现了一个函数putChan::Channel a -> a -> IO ()，如下所示

putChan (read, write) val
  = do { new_hole <- newEmptyVar ;
         old_hole <- takeMVar write ;
         putMVar write new_hole ;
         putMVar old_hole (MkItem val new_hole) }

上面的函数从写入中取出一个 MVar，然后将一个空的 MVar 放入其中。
然后它写入从 write 中提取的 old_hole。

问题是，为什么要写入old_hole？已经从 write 中取出来了，作用域也仅限于当前 block ，那有什么区别呢？

Answer 1

The question is, why does it write to old_hole? It has been taken out from write and its scope is limited to the current block only, then what difference does it make?

不完全是。 old_hole 位于读取端的“范围内”。您必须查看 newChan 才能了解完整情况:

newChan = do { 
    read <- newEmptyMVar ;
    write <- newEmptyMVar ;
    hole <- newEmptyMVar ;
    putMVar read hole ;
    putMVar write hole ;
    return (read,write) }

因此，在调用 newChan 后，putChan 中的“old_hole”与 MVar 相同newChan 中的孔。随着 channel 操作的进展，old_hole 始终嵌套在 read 的 MVar 中。

我发现链表式 channel 的设计一开始确实很难理解。该论文中的插图很好地展示了结构，但基本思想是读者“剥离”一层 MVar 以显示一个值，而作者则在 MVar 堆的“底部”插入值，以维护指向最底部的指针。

顺便说一句，这是Control.Concurrent.Chan中使用的设计