任何方式来创建unmemo-monad？ [英] Any way to create the unmemo-monad?
问题描述
这棵树会非常大，实际上是无限的。 Haskell支持无限数据结构本身并不是一个问题。
无限数据结构的熟悉示例：
fibs = 0：1：zipWith（+）fibs（尾纤）
节点仅在首次使用时分配，因此列表需要有限的内存。如果没有引用它的头部，也可以遍历一个无限列表，允许垃圾收集器收集它不再需要的部分。
返回到树的例子 - 假设我们对树进行了一些迭代，如果仍然需要树的根，那么迭代的树节点可能不会被释放（例如，在迭代深化搜索中，树会迭代几次，所以根$需要保留）。
这个问题的一个可能的解决方案，我想到的是使用unmemo-monad。
我将尝试使用monadic列表演示这个monad应该做些什么：
import控制.Monad.ListT（ListT） - cabal install列表
导入Data.Copointed - cabal安装指向
导入Data.List.Class
导入前导隐藏（enumFromTo）
nums :: ListT Unmemo Int - 什么是Unmemo？
nums = enumFromTo 0 1000000
main = print $ div（copoint（foldlL（+）0 nums））（copoint（lengthL nums））
使用 nums :: [Int] ，程序会占用很多内存在 foldlL（+）上进行迭代时，。 lengthL nums 需要引用 nums 0 nums
Unmemo 的目的是让运行时不保留
我尝试使用（（ - >）（））作为 Unmemo ，但它会产生与 nums :: [Int] 相同的结果 - 程序使用大量内存，它有 + RTS -s 。
是否有执行 Unmemo 做我想要的东西？
与流相同的技巧 - 不要直接捕获其余部分，而是捕获一个值和一个产生余数的函数。根据需要，您可以在此之上添加记忆。
数据UTree a = Leaf a |分支a（a - > [UTree a]）
我没心情想象它正好出现在这个时刻，但是我确信，这种结构自然而然就是一个相当简单的仿函数的cofree comonad。
编辑
或者这也许更容易理解： http://hackage.haskell.org/packages/archive/streams/0.7.2/doc/html/Data-Stream-Branching .html
在任何一种情况下，诀窍是您的 f 可以被选择为某物如数据N sa = N（s - >（s，[a]））适当的 s （s是流的状态参数的类型 - 如果您愿意的话，展开的种子）。这可能不完全正确，但接近应该做...
但是，当然对于真正的工作，您可以取消所有这些，直接像上面那样编写数据类型。
编辑2
下面的代码说明了这可以防止共享。请注意，即使在没有共享的版本中，配置文件中也有隆起，表示总和调用不在恒定空间中运行。我想我们需要明确的严格积累来打倒那些人。
{ - ＃LANGUAGE DeriveFunctor＃ - }
导入Data.Stream.Branching（Stream（..））
将限定的Data.Stream.Branching导入为S
导入Control.Arrow
导入Control.Applicative
import Data.List
$ b $ data UM sa = UM（s - >也许a）派生Functor
类型UStream sa = Stream（UM s）a
runUM s（UM f）= fs
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 x
| x < end = liftUM（x + 1）
|否则= 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]
- 所有这些都需要在堆栈增加的情况下运行以避免溢出。
- 这会生成一个带有两个小丘的hp文件（即列表不共享）
main = print $ div（fromIntegral $ sumUS'nums）（fromIntegral $ lengthUS'nums）
- 这会产生一个如上所述的hp文件，并且使用较少的内存，代价是
- GC数量的增加。 -H对此有很大的帮助。
- main = print $ div（fromIntegral $ sumUS nums）（fromIntegral $ lengthUS nums）
- 这将生成一个hump文件（即共享列表）
- main = print $ div（fromIntegral $ sum $ numsL）（fromIntegral $ length $ numsL）
Suppose someone makes a program to play chess, or solve sudoku. In this kind of program it makes sense to have a tree structure representing game states.
This tree would be very large, "practically infinite". Which isn't by itself a problem as Haskell supports infinite data structures.
An familiar example of an infinite data structure:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Nodes are only allocated when first used, so the list takes finite memory. One may also iterate over an infinite list if they don't keep references to its head, allowing the garbage collector to collect its parts which are not needed anymore.
Back to the tree example - suppose one does some iteration over the tree, the tree nodes iterated over may not be freed if the root of the tree is still needed (for example in an iterative deepening search, the tree would be iterated over several times and so the root needs to be kept).
One possible solution for this problem that I thought of is using an "unmemo-monad".
I'll try to demonstrate what this monad is supposed to do using monadic lists:
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], the program would take a lot of memory as a reference to nums is needed by lengthL nums while it is being iterated over foldlL (+) 0 nums.
The purpose of Unmemo is to make the runtime not keep the nodes iterated over.
I attempted using ((->) ()) as Unmemo, but it yields the same results as nums :: [Int] does - the program uses a lot of memory, as evident by running it with +RTS -s.
Is there anyway to implement Unmemo that does what I want?
Same trick as with a stream -- don't capture the remainder directly, but instead capture a value and a function which yields a remainder. You can add memoization on top of this as necessary.
data UTree a = Leaf a | Branch a (a -> [UTree a])
I'm not in the mood to figure it out precisely at the moment, but this structure arises, I'm sure, naturally as the cofree comonad over a fairly straightforward functor.
Edit
Or this is perhaps simpler to understand: http://hackage.haskell.org/packages/archive/streams/0.7.2/doc/html/Data-Stream-Branching.html
In either case, the trick is that your f can be chosen to be something like data N s a = N (s -> (s,[a])) for an appropriate s (s being the type of your state parameter of the stream -- the seed of your unfold, if you will). That might not be exactly correct, but something close should do...
But of course for real work, you can scrap all this and just write the datatype directly as above.
Edit 2
The below code illustrates how this can prevent sharing. Note that even in the version without sharing, there are humps in the profile indicating that the sum and length calls aren't running in constant space. I'd imagine that we'd need an explicit strict accumulation to knock those down.
{-# 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)
这篇关于任何方式来创建unmemo-monad？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
