7

假设我有一条记录，例如Person，并且我希望能够通过多个数据结构查找此人。也许有一个按姓名的索引，另一个按人的邮政编码的索引，以及另一个按人的当前纬度和经度的索引。也许还有更多的数据结构。所有这些都存在，因为我需要有效地查找一个或多个具有不同标准的人。

如果我只需要读取一个人的属性，这没问题。但是现在假设我需要使用其中一种数据结构查找一个人，然后更新该人的数据。

在 OOP 语言中，每个数据结构都指向内存中的同一个人。因此，当您更新一个时，您也在隐式更新其他数据结构的所指对象。这几乎是副作用和杂质的定义。我知道这与 Haskell 范式完全背道而驰，而且我不希望 Haskell 以这种方式工作。

那么，Haskell 式的方法是什么？需要明确的是，问题是这样的：我通过一个数据结构查找一个人，然后将那个人（可能还有其他一些任意数据）传递给 type 的函数ArbitraryData -> Person -> Person。如何在所有各种查找结构中传播此更改？

作为一个相对较新的 Haskell，我的第一直觉是每次更新一个人时，用新更新的人重建每个查找结构。但这似乎是一种仪式，我有很多机会以 GHC 无法检测到的方式搞砸，而且一点也不优雅。Haskell 以其优雅而闻名，我无法想象它缺少一个优雅的解决方案来解决这样一个常见的基本问题。所以我想我错过了一些东西。

作为参考，这个问题扩展了我在以下问题中讨论的一些问题：

相同数据的多个查找结构：内存重复？

Haskell 中模拟对象的标识

编辑

我刚刚想到的一个解决方案：不要在主状态下维护每个查找结构的副本。只需保留一份所有人员的列表，这是我们更新人员时唯一需要更新的内容。每次您需要按邮政编码查找时，将所有人的列表传递给一个函数，该函数会生成有效的按邮政编码数据结构。然后对结果执行查找。

我不知道这是否有效。如果它导致 CPU 在每次使用时实际上都重新计算查找结构，这是不可接受的。但我知道 Haskell 有时可以避免重新评估相同的表达式。不幸的是，我还没有弄清楚什么时候会出现这种情况。所以我不知道这种方法是否可行。

换句话说：我可以编写我的函数，就好像它们每次都在计算查找一样，而实际上 GHC 会针对底层数据没有改变的情况对其进行优化？因为这将是我上面确定的问题的一个非常优雅的解决方案。

4

7 回答 7

5

自从我回答了这个问题后，Freenode 上#haskell 中的一些人推荐了替代的预制解决方案：

您可以创建一个包含查找表以及Vector实际Persons 的数据结构。查找表将为您提供一个Int或一个Ints 列表（而不是一个Person或一个Persons 列表），它是Vector Person. 例如：

data PersonStuff = PersonStuff {
                                 persons              :: Vector Person,
                                 firstNameLookupTable :: LookupTable Name,
                                 ...
                               }

data LookupTable a = LookupTable {
                                   table  :: Map a Int,
                                   update :: Person -> Person -> Map a Int -> Map a Int
                                 }

该update函数被赋予 oldPerson和 updated Person，并且只有在相关细节发生变化时才会更新表。当Person通过您将编写的便捷PersonStuff函数修改 a 时，这些函数将为您更新所有查找表，并返回PersonStuff包含所有关联数据的新表。这使得具有快速查找的纯数据结构成为可能。

您可以创建这样updatePeopleWithFirstName :: Name -> (Person -> Person) -> PersonStuff -> PersonStuff的函数来获取所有有名字的人，将 aPerson -> Person应用于每个人，修改他们在 中的条目Vector，并使用这些update函数更新所有查找表。

于 2013-10-21T21:55:02.183 回答
3

我可能会用新值更新每个查找结构。也许将结构分组在记录中并提供全局更新功能。

或者，也许您可​​以将搜索条件之一指定为“主要”，并让其他查找映射中的值指向对象的“主键”，而不是指向对象值本身。但是，这将导致对非主键的每次访问进行一次额外的查找。

于 2013-10-21T19:22:05.593 回答
3

我们面临两个挑战。第一个是“[我们]如何在……各种查找结构中传播[a]变化”。第二个是最小化我们执行查找时所做的工作。

让我们编写一些工作代码，以便我们有一些具体的讨论。

首先，让我们看看什么是“更新”或“改变”。更新或更改以一种状态开始，并以另一种状态结束。它是从前一个状态到下一个状态的函数。基本上是type Update = State -> State。在 Haskell 中，我们可以通过将状态隐藏在 some 中来使状态消失Monad；这是一种非常普遍的做法，因此尽管它看起来“不纯”，但它非常“Haskell-ish”。你可以通过阅读state monad来了解更多关于这个想法的信息。

这是一个类似于MonadState的类，它让我们讨论可以分配 ( new)、更新 ( set) 和检查 ( get) 的值。

-- Class for a typed dictionary in a monadic context
class (Monad m) => MonadReference m where
    type Reference :: * -> *
    new :: (Typeable a) => a -> m (Reference a)
    set :: (Typeable a) => (Reference a) -> a -> m ()
    get :: (Typeable a) => (Reference a) -> m a

我们将使用它来编写一些非常简单的示例代码。

data Person = Person {
    name :: String
} deriving (Show, Typeable)

data Company = Company {
    legalName :: String
} deriving (Show, Typeable)

-- the only thing we need MonadIO for in this exmple is printing output
example1 :: (MonadIO m, MonadReference m) => m ()
example1 = do
    -- alice :: Reference Person
    alice <- new $ Person { name = "Alice" }
    bob <- new $ Person { name = "Bob" }
    -- company :: Reference Company
    company <- new $ Company { legalName = "Eve's Surveillance" }
    (liftIO . print) =<< get alice
    (liftIO . print) =<< get bob
    (liftIO . print) =<< get company
    (liftIO . putStrLn) ""
    set alice Person { name = "Mike" }
    set company Company { legalName = "Mike's Meddling" }
    (liftIO . print) =<< get alice
    (liftIO . print) =<< get bob
    (liftIO . print) =<< get company

我们使用new、get和set来创建一些References、检查它们并修改它们。

为了让它工作，我们需要一些无聊的样板。我们将借用IORefa 的实现Reference来运行此代码，而无需自己编写太多代码。

{-# LANGUAGE TypeFamilies, DeriveDataTypeable #-}
module Main (
    main
) where

import Data.Typeable
import Data.Traversable
import Control.Applicative
import Data.IORef

--transformers package:
import Control.Monad.IO.Class

main = example1

-- Instead of implementing a dictionary, for an example we'll just use IORefs when we have IO.
instance MonadReference IO where
    type Reference = IORef
    new = newIORef
    set = writeIORef
    get = readIORef

现在，除了更新人员之外，我们还希望在多个数据结构中更新人员。我们将看两个数据结构：一个列表[Person]， 和一个元组，(Person,Company)。现在，我们可以Reference为人们制作一个 s 列表，比如(people :: [Reference Person]) = [alice, bob]，但这不是很有用。例如，我们真的不知道该怎么做show。如果Reference不混合在列表中会更有用。天真，Reference [Person]会更有用。但这对此毫无意义set，Reference所以很明显我们的类型错误。Reference [Person]只会让我们打电话get把它变成一个m [Person]，所以我们可以跳过它而只使用m [Person]. 这是一个这样做的例子：

-- the only thing we need MonadIO for in this exmple is printing output
example2 :: (MonadIO m, MonadReference m) => m ()
example2 = do
    -- alice :: Reference Person
    alice <- new $ Person { name = "Alice" }
    bob <- new $ Person { name = "Bob" }
    -- company :: Reference Company
    company <- new $ Company { legalName = "Eve's Surveillance" }
    (liftIO . print) =<< get alice
    (liftIO . print) =<< get bob
    (liftIO . print) =<< get company
    let people = do
        a <- get alice
        b <- get bob
        return [a, b]
    let structure2 = do
        a <- get alice
        c <- get company
        return (a, c)
    (liftIO . print) =<< people
    (liftIO . print) =<< structure2
    (liftIO . putStrLn) ""
    set alice Person { name = "Mike" }
    set company Company { legalName = "Mike's Meddling" }
    (liftIO . print) =<< get alice
    (liftIO . print) =<< get bob
    (liftIO . print) =<< get company
    (liftIO . print) =<< people
    (liftIO . print) =<< structure2

现在我们对一个或多个用于执行此操作的库应该是什么样子有了相当多的了解。以下是我们可能已经想到的一些要求：

  • 我们需要一些东西来保持所有实体的状态
  • 我们需要一种方法来从一个状态到一个拥有新实体的新状态
  • 我们需要一种方法来更新存储在状态中的实体
  • 我们需要一种从状态中检索实体的方法

以下是对一些代码进行试验后出现的一些要求：

  • 我们需要一种方法来生成依赖于实体当前状态的状态依赖值。我们在 、 和 中看到了get alice这get bob一点get company。
  • 我们需要一种方法来从常量中生成依赖于状态的值。我们在 、 和 构造函数的使用中看到了(:)这[]一点(,)。
  • 我们需要一种方法将多个状态相关值组合成新的状态相关值。

我们的示例也存在一些问题。如果我们接受MonadReference m => m atype 的状态依赖值的类型a，那么没有什么可以阻止我们认为从状态中获取值的东西也修改它。

  • 依赖于状态的值不应该能够修改状态。

我们也有性能问题。每次我们使用它们时，我们所有的状态相关值都会被完全重新计算。良好的性能要求可能是：

  • 除非它所依赖的状态已被修改，否则不应计算状态相关值。

有了这些新要求，我们就可以制作新的接口。在我们制作新接口之后，我们可以为它们配备一个简单的实现。在我们有了一个简单的实现之后，我们可以解决我们对性能的要求，并做出一个高性能的实现。

一些可以让我们为下一步做准备的练习包括阅读或使用Control.Applicative、发布者-订阅者设计模式、可操作的 monad 和转换器Program或ProgramT免费的 monad 和转换器Free、FreeF、 和FreeT、Data.Traversable、Control.Lens和 knockout.js javascript 库。

更新：新界面

根据我们对状态相关值的新要求，我们可以编写一个新接口：

-- Class for a monad with state dependent values
class (MonadReference m, Applicative Computed, Monad Computed) => MonadComputed m where
    type Computed :: * -> *
    track :: (Typeable a) => Reference a -> m (Computed a)
    runComputed :: (Typeable a) => (Computed a) -> m a

这些解决了我们的新要求，如下所示：

  • track生成一个依赖于 a 的状态相关值Reference，它满足我们的第一个新要求。
  • Applicative'spure和Monad' return 都提供了一种方法来创建Computed包含常量的新值。
  • Applicative's<*>和Monad's>>=提供了将计算值组合成新计算值的方法。
  • 该Computed类型为实现排除不需要的类型提供了一种方法。

现在我们可以根据这个接口编写新的示例代码。我们将用三种不同的方式构造计算值：在带有实例的列表上使用' Data.TraversablesequenceA ，使用实例 for ，最后使用实例 for 。ApplicativeComputedMonadComputedApplicativeComputed

-- the only thing we need MonadIO for in this exmple is printing output
example :: (MonadIO m, MonadComputed m) => m ()
example = do
    -- aliceRef :: Reference Person
    aliceRef <- new $ Person { name = "Alice" }
    -- alice :: Computed Person
    alice <- track aliceRef
    bobRef <- new $ Person { name = "Bob" }
    bob <- track bobRef
    -- companyRef :: Reference Company
    companyRef <- new $ Company { legalName = "Eve's Surveillance" }
    -- company :: Computed Company
    company <- track companyRef
    (liftIO . print) =<< runComputed alice
    (liftIO . print) =<< runComputed bob
    (liftIO . print) =<< runComputed company
    let people = Traversable.sequenceA [alice, bob]
    let structure2 = do
        a <- alice
        c <- company
        return (a, c)
    let structure3 = (pure (,)) <*> structure2 <*> bob
    (liftIO . print) =<< runComputed people
    (liftIO . print) =<< runComputed structure2
    (liftIO . print) =<< runComputed structure3
    (liftIO . putStrLn) ""
    set aliceRef Person { name = "Mike" }
    set companyRef Company { legalName = "Mike's Meddling" }
    (liftIO . print) =<< runComputed alice
    (liftIO . print) =<< runComputed bob
    (liftIO . print) =<< runComputed company
    (liftIO . print) =<< runComputed people
    (liftIO . print) =<< runComputed structure2
    (liftIO . print) =<< runComputed structure3

请注意，如果我们不想或不需要track aliceRef并且track bobRef独立地，我们可以通过创建一个Computed值列表mapM track [aliceRef, bobRef]。

现在我们可以为 IO 做另一个简单的实现，这样我们就可以运行我们的示例并看到我们在正确的轨道上。我们将使用操作的Program类型来简化此操作，并为我们提供一个Applicative和一个Monad实例。

-- Evaluate computations built in IO
instance MonadComputed IO where
    -- Store the syntax tree in a Program from operational
    type Computed = Program IORef
    track = return . singleton
    runComputed c = case view c of 
        Return x -> return x
        ref :>>= k -> do
            value <- readIORef ref
            runComputed (k value)

此时整个运行示例为：

{-# LANGUAGE TypeFamilies, DeriveDataTypeable, FlexibleContexts #-}
module Main (
    main
) where

import Data.Typeable
import qualified Data.Traversable as Traversable
import Control.Applicative
import Data.IORef

--transformers package:
import Control.Monad.IO.Class

--operational package:
import Control.Monad.Operational

main = example

data Person = Person {
    name :: String
} deriving (Show, Typeable)

data Company = Company {
    legalName :: String
} deriving (Show, Typeable)

-- the only thing we need MonadIO for in this exmple is printing output
example :: (MonadIO m, MonadComputed m) => m ()
example = do
    -- aliceRef :: Reference Person
    aliceRef <- new $ Person { name = "Alice" }
    -- alice :: Computed Person
    alice <- track aliceRef
    bobRef <- new $ Person { name = "Bob" }
    bob <- track bobRef
    -- companyRef :: Reference Company
    companyRef <- new $ Company { legalName = "Eve's Surveillance" }
    -- company :: Computed Company
    company <- track companyRef
    (liftIO . print) =<< runComputed alice
    (liftIO . print) =<< runComputed bob
    (liftIO . print) =<< runComputed company
    let people = Traversable.sequenceA [alice, bob]
    let structure2 = do
        a <- alice
        c <- company
        return (a, c)
    let structure3 = (pure (,)) <*> structure2 <*> bob
    (liftIO . print) =<< runComputed people
    (liftIO . print) =<< runComputed structure2
    (liftIO . print) =<< runComputed structure3
    (liftIO . putStrLn) ""
    set aliceRef Person { name = "Mike" }
    set companyRef Company { legalName = "Mike's Meddling" }
    (liftIO . print) =<< runComputed alice
    (liftIO . print) =<< runComputed bob
    (liftIO . print) =<< runComputed company
    (liftIO . print) =<< runComputed people
    (liftIO . print) =<< runComputed structure2
    (liftIO . print) =<< runComputed structure3


-- Class for a typed dictionary in a monadic context
class (Monad m) => MonadReference m where
    type Reference :: * -> *
    new :: (Typeable a) => a -> m (Reference a)
    set :: (Typeable a) => Reference a -> a -> m ()
    get :: (Typeable a) => Reference a -> m a


-- Class for a monad with state dependent values
class (MonadReference m, Applicative Computed, Monad Computed) => MonadComputed m where
    type Computed :: * -> *
    track :: (Typeable a) => Reference a -> m (Computed a)
    runComputed :: (Typeable a) => (Computed a) -> m a

-- Instead of implementing a dictionary, for an example we'll just use IORefs when we have IO.
instance MonadReference IO where
    type Reference = IORef
    new = newIORef
    set = writeIORef
    get = readIORef    

-- Evaluate computations built in IO
instance MonadComputed IO where
    -- Store the syntax tree in a Program from operational
    type Computed = Program IORef
    track = return . singleton
    runComputed c = case view c of 
        Return x -> return x
        ref :>>= k -> do
            value <- readIORef ref
            runComputed (k value)

我们仍然需要解决我们的性能要求，以最大限度地减少执行查找时所做的工作。我们的目标要求是：

  • 除非它所依赖的状态已被修改，否则不应计算状态相关值。

我们现在可以根据我们的界面来澄清这一点：

  • runComputedComputed除非自上次执行以来它所依赖的值已被修改，否则不应计算runComputed。

我们现在可以看到，我们想要的解决方案将是缓存失效或自下而上的查询评估。我猜想在一种具有惰性求值的语言中，它们的结果都是一样的。

最后更新：性能

配备新界面后，我们现在可以探索并实现我们的性能目标。在这样做的过程中，我发现我们遗漏了一个额外的、微妙的要求。runComputed如果值未更改，我们希望重用先前计算的值。我们没有注意到的是 Haskell 的类型系统应该并且正在阻止我们这样做。一个类型的值Computed a总是意味着同样的事情，它从来没有真正被修改过。因此，构建我们的结构的计算将意味着同样的事情，“由这些部分构建的计算”即使在我们执行之后也是如此runComputed。我们需要溜到某个地方来放置第一次运行计算的副作用。我们可以用类型m (Computed a)来代替。这样做的新方法MonadComputed m是：

share :: (Typeable a) => (Computed a) -> m (Computed a)

我们得到的新的Computed a含义略有不同：“由这些部分构建的可能缓存的计算”。我们已经在做类似的事情，但是告诉 Haskell 而不是告诉我们的代码。例如，我们写道：

    let people = Traversable.sequenceA [alice, bob]

这let告诉 Haskell 编译器每次遇到people它都应该使用相同的 thunk。如果我们在Traversable.sequenceA [alice, bob]每次使用时都编写它，Haskell 编译器可能不会创建和维护指向单个 thunk 的指针。在处理内存时知道这可能是一件好事。如果您想在内存中维护某些内容并避免计算，请使用let，如果您想重新计算它以避免占用内存，请不要使用let. 在这里，我们明确地想要保留我们的计算结构，所以我们将使用我们的新等价物，share

    people <- share $ Traversable.sequenceA [alice, bob]

最后对示例代码的其余更改是为了演示更多可能的更新。

现在我们已经完成了接口，我们可以着手实现。此实现仍将利用IOand IORefs。我们的实现将基于订阅更改通知，并在更改发生时使缓存的更改及其依赖项无效。此数据结构存储一个值和想要通知的订阅者：

-- A published value for IO, using Weak references to the subscribers
data Published a = Published {
    valueRef :: IORef a,
    subscribers :: IORef [Weak (IO ())]
}

当 IO 中发生某些事情时需要通知的事情可能很简单IO ()，但是依赖计算和值之间的循环会将所有依赖计算保存在内存中，直到忘记原始值。相反，指向依赖项更新操作的Weak指针（从System.Mem.Weak）应该允许垃圾收集器收集这些。

首先我们将实现MonadReference IO. 我们处理References 到实体的代码被修改为窥视Published以获取值，并在设置值时执行所有订阅者。

-- A new implementation that keeps an update list
instance MonadReference IO where
    type Reference = Published
    new = newIORefPublished
    set = setIORefPublished
    get = readIORefPublished

-- Separate implemenations for these, since we'd like to drop the Typeable constraint
newIORefPublished value =
    do
        ref <- newIORef value
        subscribersRef <- newIORef []
        return Published { valueRef = ref, subscribers = subscribersRef }

setIORefPublished published value =
    do
        writeIORef (valueRef published) value
        notify $ subscribers published                 


--readIORefPublished = readIORef . valueRef

readIORefPublished x = do
    putStrLn "getting"
    readIORef $ valueRef x

通知订阅者有点棘手。我们需要忘记任何已被垃圾收集删除的订阅者。我预计订阅者可能会在其更新操作期间订阅事物以应对棘手的绑定情况，因此当订阅者被垃圾收集时，我们不会假设新的订阅者集是旧集，除了垃圾收集的订阅者，而是将它们过滤为单独的cleanupWeakRefs步骤。

notify :: IORef [Weak (IO ())] -> IO ()
notify = go
    where
        go subscribersRef = do
            subscribers <- readIORef subscribersRef
            needsCleanup <- (liftM (any id)) (mapM notifySubscriber subscribers)
            when needsCleanup $ cleanupWeakRefs subscribersRef
        notifySubscriber weakSubscriber = do
            maybeSubscriber <- deRefWeak weakSubscriber
            case maybeSubscriber of
                Nothing -> return True
                Just subscriber -> subscriber >> return False


cleanupWeakRefs :: IORef [Weak a] -> IO ()
cleanupWeakRefs ref = do
    weaks <- readIORef ref
    newWeaks <- (liftM catMaybes) $ mapM testWeak weaks
    writeIORef ref newWeaks
    where
        testWeak weakRef = liftM (>> Just weakRef) $ deRefWeak weakRef

我们已经完成了对实体的处理，是时候进入有趣且棘手的部分，即计算了。这是计算或状态相关值的完整数据类型：

-- Data type for building computations
data IORefComputed a where 
    Pure :: a -> IORefComputed a
    Apply :: IORefComputed (b -> a) -> IORefComputed b -> IORefComputed a
    Bound :: IORefComputed b -> (b -> IORefComputed a) -> IORefComputed a
    Tracked :: Published a -> IORefComputed a
    Shared :: Published (Either (IORefComputed a) a) -> IORefComputed a

Pure表示不依赖于任何东西的值。Apply表示由 的应用程序构建的值<*>。Bound表示使用Monad实例的>>=. Tracked是使用track. Shared是我们记住计算并被通知跟踪值更改的点，使用share. 我们重用该Published类型来存储一个值及其订阅者，但我们存储的值是Either共享缓存脏时需要执行的计算(IORefComputed a)，或者缓存干净时的缓存值a。以下是让用户使用这些的实例：

instance Monad IORefComputed where
    return = Pure
    (>>=) = Bound
    (>>) _ = id

instance Applicative IORefComputed where
    pure = return
    (<*>) = Apply

instance Functor IORefComputed where
    fmap = (<*>) . pure     

-- Evaluate computations built in IO
instance MonadComputed IO where
    type Computed = IORefComputed
    track = trackIORefComputed
    runComputed = evalIORefComputed
    share = shareIORefComputed

-- Separate implementations, again to drop the Typeable constraint
trackIORefComputed = return . Tracked

注意： 的优化>>几乎肯定会在 存在的情况下违反单子定律_|_。

runComputed现在我们需要对和进行非平凡的实现share。首先我们看一下share，它完成了大部分新工作：

shareIORefComputed :: IORefComputed a -> IO (IORefComputed a)
shareIORefComputed c =
    case c of          
        Apply cf cx -> do
            sharedf <- shareIORefComputed cf
            sharedx <- shareIORefComputed cx
            case (sharedf, sharedx) of
                -- Optimize away constants
                (Pure f, Pure x) -> return . Pure $ f x 
                _ -> do
                    let sharedc = sharedf <*> sharedx
                    published <- newIORefPublished $ Left sharedc
                    -- What we are going to do when either argument changes
                    markDirty <- makeMarkDirty published published sharedc
                    subscribeTo sharedf markDirty
                    subscribeTo sharedx markDirty
                    return $ Shared published     
        Bound cx k -> do
            sharedx <- shareIORefComputed cx
            case cx of
                -- Optimize away constants
                (Pure x) -> shareIORefComputed $ k x
                _ -> do
                    let dirtyc = sharedx >>= k
                    published <- newIORefPublished $ Left dirtyc
                    -- What we are going to do when the argument to k changes
                    markDirty <- makeMarkDirty published published dirtyc
                    subscribeTo sharedx markDirty            
                    return $ Shared published
        _ -> return c

当我们被要求分享 , 的应用时<*>，Apply我们首先分享它的两个论点。如果我们可以确定它是恒定的，我们会优化掉这个值。如果我们不能优化它，我们会创建一个新的、最初是脏的缓存，并在任一参数更改时要求更新。

处理起来>>=要困难得多。我们与 共享参数>>=，但我们不知道Computed函数将返回什么值，直到我们对每个参数进行评估。我们说它可以通过评估整个绑定来计算，并在参数更改时要求缓存无效。我们一定会在以后改进这一点。

在所有其他情况下，无需做任何事情来缓存该值。它要么是一个常量，要么是一个已经缓存的Trackedor Shared。

如果您怀疑是否需要share，请将此定义替换为

shareIORefComputed c = return c

并运行示例。您会看到每次运行时都会读取每个涉及的值runComputed。您无法runComputed修改现有Computed内容以了解它已被缓存的位置，因为我们无法更改 Haskell 中的现有值。

现在我们将实现runComputed. 基本思想是我们像以前一样评估事物，但是当我们遇到脏共享缓存时，我们会计算它的新值并更新缓存。这些更新不会触发订阅者的通知。

evalIORefComputed :: IORefComputed a -> IO a
evalIORefComputed c = 
    case c of
        Pure x -> return x
        Apply cf cx -> do
            f <- evalIORefComputed cf
            x <- evalIORefComputed cx
            return (f x) 
        Bound cx k -> do            
            value <- evalIORefComputed cx
            evalIORefComputed (k value)
        Tracked published -> readIORefPublished published
        Shared publishedThunk -> do
            thunk <- readIORefPublished publishedThunk
            case thunk of
                Left computation@(Bound cx k) -> do
                    x <- evalIORefComputed cx
                    -- Make a shared version of the computed computation
                    currentExpression <- shareIORefComputed (k x)
                    let gcKeyedCurrentExpression = Left currentExpression
                    writeIORef (valueRef publishedThunk) gcKeyedCurrentExpression
                    markDirty <- makeMarkDirty publishedThunk gcKeyedCurrentExpression computation
                    subscribeTo currentExpression markDirty
                    evalIORefComputed c
                Left computation -> do
                    value <- evalIORefComputed computation
                    writeIORef (valueRef publishedThunk) (Right value)
                    return value
                Right x ->
                    return x

这很简单，除了我们为脏共享做的事情>>=。我们评估参数，然后share进行计算。诀窍是我们要求在更新这个新值时将整个共享 thunk 标记为脏。当为此的脏标记是垃圾收集时，我们要求收集的垃圾忘记这一点currentExpression。这提供了一个窗口，在此期间，thunk 可能会被标记为脏，即使它不再依赖于currentExpression. 现在，共享绑定将通过对其参数的更改、对依赖于其参数的计算值的更改以及对最近依赖于其参数但尚未被垃圾回收的计算值的更改标记为脏。

实现的其余部分是构建对通知的弱引用并通过预先添加新订阅者来订阅已发布的值。

makeMarkDirty :: Published (Either (IORefComputed a) a) -> k -> IORefComputed a -> IO (Weak (IO ())) 
makeMarkDirty published key definition =
    do
        let markDirty = do
            existing <- readIORef (valueRef published)
            case existing of
                Right _ -> setIORefPublished published $ Left definition
                _ -> return ()
        mkWeak key markDirty Nothing


subscribeTo :: IORefComputed a -> Weak (IO ()) -> IO ()
subscribeTo (Tracked published) trigger = modifyIORef' (subscribers published) (trigger :)
subscribeTo (Shared published) trigger = modifyIORef' (subscribers published) (trigger :)    
subscribeTo _ _ = return ()

完整的编译示例代码在 github 上。它需要变压器包。

如果您运行示例代码，您会注意到：

  • company改名后，runComputed people只执行一次get获取缓存值
  • 在不进行任何更改后，所有三个结构都只执行一次 get 以获取整个缓存结构
  • 更改后bob，runComputed structure2仅执行一次 get 即可获取缓存值，并且计算完成的工作structure3较少，即使bob在structure3.
  • structure2，使用实例构建的一个Monad，由于额外的中间共享值，需要最多的计算工作。
于 2013-10-22T00:17:30.210 回答
2

如果您需要有效地完成它，则必须降级为可变数据结构，基本上是IOmonad。

这些对象之间的可更新引用（如 OO）在 Haskell 中也可用。这些是IORefs。它们也有线程安全的版本：MVar并且TVar- 它们之间的选择取决于您的并发模型。

这种在对象之间具有不同类型引用的数据结构称为Graph，它发生在我目前正在处理 Haskell Graph Database 项目时。该项目正在接近其第一个版本。内存中的数据结构已经实现，持久层也是如此，剩下的就是客户端和服务器。所以只要留意它。我会在发布时在 reddit 上发布。源存储库在这里：https ://github.com/nikita-volkov/graph-db/ ，虽然我已经有一段时间没有推送更新了，所以它有点过时了。

于 2013-10-21T22:37:31.870 回答
1

“更新所有索引结构”方法不一定是不必要的仪式，如果您将“具有高效查找操作的人员集合”的概念建模为一个单一的事物本身，而不是一堆独立的集合，你'正在“手动”尝试彼此保持同步。

假设你有一个Person类型。然后你有一个Person你想被类型Name和索引的对象集合Zip。Map Name Person您可以使用and之类的东西Map Zip Person，但这并不能真正表达您的意思。您没有两组人，一组由 键控，另一组由Name键控Zip。您有一组人，可以通过Name或查找Zip，因此您编写的代码和您使用的数据结构应该反映这一点。

让我们调用集合类型People。对于您的索引查找，您最终会得到类似findByName :: People -> Name -> Personand的东西findByZip :: People -> Zip -> Person。

您还拥有Person -> Person可以“更新”Person记录的类型函数。因此，您可以使用findByName从 a 中Person提取 a People，然后应用更新功能来获取新的Person. 怎么办？您必须构建一个 new People，并将原始Person替换为 new Person。“更新”函数无法处理这个问题，因为它们只关心Person值，并且对您的商店一无所知People（甚至可能有很多People商店）。所以你需要一个类似的函数updatePeople :: Person -> Person -> People -> People，你最终会写很多这样的代码：

let p = findByName name people
    p' = update p
in updatePeople p p' people

这有点样板。看起来像一份工作updateByName :: Name -> (Person -> Person) -> People -> People。

people.findByName(name).changeSomething(args)有了这个，你可以在 OO 语言中写出你现在可以写的东西updateByName name (changeSomething args) people。不太一样！

请注意，我根本没有谈到这些数据结构或操作是如何实际实现的。我纯粹在考虑您拥有的概念以及对它们有意义的操作。这意味着无论您如何实施它们，这样的方案都将起作用；您甚至可以（可能应该？）将实现细节隐藏在模块屏障后面。您可以很好地实现People多个集合的记录，将不同的事物映射到您的Person记录，但是从“外部”您可以将其视为支持多种不同类型的查找/更新操作的单个集合，并且没有担心保持多个索引同步。这只是在执行People您必须担心的类型及其操作，这为您提供了一个解决问题的地方，而不必在每个操作上都正确执行。

你可以更进一步。有了一些额外的假设（例如知道您的Name,Zip和任何其他索引都在Person/的不同字段上使用相同的模式实现），您可能可以使用类型类People和/或模板 Haskell 来避免必须实现findByName,findByZip等findByFavouriteSpoon分开（尽管有单独的实现使您有更多机会根据所涉及的类型使用不同的索引策略，并且可能有助于优化更新，例如您只需要更新可能无效的索引）。你可以使用类型类和类型族来实现一个findBy它使用调用它的任何索引键的类型来确定要使用哪个索引，无论您有单独的实现还是单个通用实现（尽管这意味着您不能有多个具有相同类型的索引）。

这是我应该在工作时敲出的一个示例，提供基于类型类的 findBy操作updateBy：

{-# LANGUAGE FlexibleContexts, MultiParamTypeClasses, TypeFamilies #-}

import Data.Map (Map, (!), adjust, delete, insert)


-- sample data declarations
newtype Name = Name String
    deriving (Eq, Ord, Show)

newtype Zip = Zip Int
    deriving (Eq, Ord, Show)

data Person = Person
  { name    :: Name
  , zipCode :: Zip
  }

-- you probably wouldn't export the constructor here
data People = People
  { byName :: Map Name Person
  , byZip  :: Map Zip Person
  }


-- class for stores that can be indexed by key
class FindBy key store where
    type Result key store
    findBy :: key -> store -> Result key store
    updateBy :: key -> (Result key store -> Result key store) -> store -> store


-- helper functions
-- this stuff would be hidden
updateIndex
    :: Ord a
    => (Person -> a) -> Person -> Person -> Map a Person -> Map a Person
updateIndex f p p' = insert (f p') p' . delete (f p)

-- this function has some per-index stuff;
-- note that if you add a new index to People you get a compile error here
-- telling you to account for it
-- also note that we put the *same* person in every map; sharing should mean
-- that we're not duplicating the objects, so no wasted memory
replacePerson :: Person -> Person -> People -> People
replacePerson p p' ps = ps { byName = byName', byZip = byZip' }
  where
    byName' = updateIndex name    p p' $ byName ps
    byZip'  = updateIndex zipCode p p' $ byZip  ps

-- a "default" definition for updateBy in terms of findBy when the store happens
-- to be People and the result happens to be Person
updatePeopleBy
    :: (FindBy key People, Result key People ~ Person)
    => key -> (Person -> Person) -> People -> People
updatePeopleBy k f ps =
    let p = findBy k ps
    in replacePerson p (f p) ps


-- this is basically the "declaration" of all the indexes that can be used
-- externally
instance FindBy Name People where
    type Result Name People = Person
    findBy n ps = byName ps ! n
    updateBy = updatePeopleBy

instance FindBy Zip People where
    type Result Zip People = Person
    findBy z ps = byZip ps ! z
    updateBy = updatePeopleBy
于 2013-10-22T06:14:19.467 回答
1

Haskell 试图鼓励你思考价值，而不是实体。我的意思是，在大多数情况下，纯代码将通过将值从一种转换为另一种来构造事物，而不是修改或更新许多其他人共享的数据。对象的平等/身份完全由它们的内容定义，而不是它们的位置。但让我更具体一些。

“纯突变”的一般解决方案是创建一个内同态。在您的情况下，如果您有一个Directory人，您可以使用带有签名的函数读取一个人的数据

type Name = String
get :: Name -> Directory -> Person

并用一个函数修改它

mod :: Name -> (Person -> Person) -> (Directory -> Directory)

如果你有很多修改函数f, g, h,i那么你可以把它们串起来

mod i . mod h . mod g . mod f

但重要的是要意识到，Directory在该链中创建的每一个都可能独立存在并被更新/读取/修改。这就是不变性的本质——数据是持久的，我们必须在修改数据时“通过时间”手动推送数据。

那么如何将更改传播到其他结构呢？简而言之……你不能。如果您尝试这样做，那么您正在以非常难以纯粹做的方式对事物进行建模。

Haskell 问你“传播”是什么意思？这些对象是基于过去的数据，我们不能改变这个事实。

纯粹的、不可变的数据肯定是有局限性的。一些算法无法翻译，通常通过在唯一名称生成器和有限Map. 如果这是您的情况，最好通过STorIO单子开始引入不纯的效果，您可以从STRef和IORef容器类型中获得真正的内存突变。

于 2013-10-21T19:37:42.880 回答
0

Jarret，我强烈建议您调查Zippers，无论是在 Haskell wiki 上记录的简单形式，还是由 Oleg Kiselyov 开发的更高级的通用版本。引用奥列格的话，

Zipper 是一个数据结构中的可更新但纯功能游标。它允许我们替换数据结构深处的项目，例如树或术语，而无需任何突变。结果将尽可能多地与旧结构共享其组件。旧的数据结构仍然可用，如果我们希望稍后“撤消”操作，这很有用。

wiki 页面提供了一个简单示例，说明如何更新树的一个节点而无需重建树的其余部分。

如果您将不同的视图包装在拉链中并使用共享密钥，您应该会看到显着的效率提升。如果您将不同的视图包装在适当的 monad（例如 State Monad）中，您可以通过一个操作更新位置并看到所有不同的视图移动到指向“相同”的对象。

于 2013-10-23T18:14:05.263 回答