有什么方法可以创建 unmemo-monad 吗？

假设有人编写了一个下棋或解数独的程序。在这种程序中，使用表示游戏状态的树结构是有意义的。

这棵树会非常大，“几乎是无限的”。这本身并不是一个问题，因为 Haskell 支持无限数据结构。

一个常见的无限数据结构示例：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

节点仅在第一次使用时分配，因此列表占用有限的内存。如果不保留对其头部的引用，也可以迭代无限列表，从而允许垃圾收集器收集不再需要的部分。

回到树的例子 - 假设对树进行一些迭代，如果仍然需要树的根，则迭代的树节点可能不会被释放（例如，在迭代加深搜索中，树将被迭代多次因此需要保留根）。

我想到的这个问题的一个可能的解决方案是使用“unmemo-monad”。

我将尝试使用单子列表来演示这个单子应该做什么：

import Control.Monad.ListT (ListT)  -- cabal install List
import Data.Copointed  -- cabal install pointed
import Data.List.Class
import Prelude hiding (enumFromTo)

nums :: ListT Unmemo Int  -- What is Unmemo?
nums = enumFromTo 0 1000000

main = print $ div (copoint (foldlL (+) 0 nums)) (copoint (lengthL nums))

Using nums :: [Int]，该程序将占用大量内存作为对nums需要由lengthL nums当它被迭代时foldlL (+) 0 nums.

的目的Unmemo是为了让运行时不让节点迭代。

我尝试使用((->) ()) as Unmemo，但它产生的结果与nums :: [Int]确实 - 该程序使用了大量内存，通过运行它可以明显看出+RTS -s.

有没有办法实施Unmemo这就是我想要的吗？

与流相同的技巧——不直接捕获余数，而是捕获一个值和一个产生余数的函数。您可以根据需要在此基础上添加记忆。

data UTree a = Leaf a | Branch a (a -> [UTree a]) 

我现在没有心情去准确地弄清楚它，但我确信这种结构自然会出现，就像一个相当简单的函子上的 cofree comonad 一样。

Edit

找到了：http://hackage.haskell.org/packages/archive/comonad-transformers/1.6.3/doc/html/Control-Comonad-Trans-Stream.html http://hackage.haskell.org/packages/archive/comonad-transformers/1.6.3/doc/html/Control-Comonad-Trans-Stream.html

或者这可能更容易理解：http://hackage.haskell.org/packages/archive/streams/0.7.2/doc/html/Data-Stream-Branching.html http://hackage.haskell.org/packages/archive/streams/0.7.2/doc/html/Data-Stream-Branching.html

无论哪种情况，诀窍是你的f可以选择类似的东西data N s a = N (s -> (s,[a]))为一个适当的s（s 是流的状态参数的类型——展开的种子，如果你愿意的话）。这可能不完全正确，但应该做一些接近的事情......

但当然，对于实际工作，您可以放弃所有这些，直接按照上面的方式编写数据类型。

Edit 2

下面的代码说明了这如何阻止共享。请注意，即使在没有共享的版本中，配置文件中也存在驼峰，表明总和和长度调用没有在恒定空间中运行。我想我们需要一个明确的严格积累来消除这些。

{-# LANGUAGE DeriveFunctor #-}
import Data.Stream.Branching(Stream(..))
import qualified Data.Stream.Branching as S
import Control.Arrow
import Control.Applicative
import Data.List

data UM s a = UM (s -> Maybe a) deriving Functor
type UStream s a = Stream (UM s) a

runUM s (UM f) = f s
liftUM x = UM $ const (Just x)
nullUM = UM $ const Nothing

buildUStream :: Int -> Int -> Stream (UM ()) Int
buildUStream start end = S.unfold (\x -> (x, go x)) start
    where go x
           | x < end = liftUM (x + 1)
           | otherwise = nullUM

sumUS :: Stream (UM ()) Int -> Int
sumUS x = S.head $ S.scanr (\x us -> maybe 0 id (runUM () us) + x) x

lengthUS :: Stream (UM ()) Int -> Int
lengthUS x = S.head $ S.scanr (\x us -> maybe 0 id (runUM () us) + 1) x

sumUS' :: Stream (UM ()) Int -> Int
sumUS' x = last $ usToList $ liftUM $ S.scanl (+) 0  x

lengthUS' :: Stream (UM ()) Int -> Int
lengthUS' x = last $ usToList $ liftUM $ S.scanl (\acc _ -> acc + 1) 0 x

usToList x = unfoldr (\um -> (S.head &&& S.tail) <$> runUM () um) x

maxNum = 1000000
nums = buildUStream 0 maxNum

numsL :: [Int]
numsL = [0..maxNum]

-- All these need to be run with increased stack to avoid an overflow.

-- This generates an hp file with two humps (i.e. the list is not shared)
main = print $ div (fromIntegral $ sumUS' nums) (fromIntegral $ lengthUS' nums)

-- This generates an hp file as above, and uses somewhat less memory, at the cost of
-- an increased number of GCs. -H helps a lot with that.
-- main = print $ div (fromIntegral $ sumUS nums) (fromIntegral $ lengthUS nums)

-- This generates an hp file with one hump (i.e. the list is shared)
-- main = print $ div (fromIntegral $ sum $ numsL) (fromIntegral $ length $ numsL)