title: Any way to create the unmemo-monad?
body: <p>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.</p>
  
  <p>This tree would be very large, "practically infinite". Which isn't by itself a problem as Haskell supports infinite data structures.</p>
  
  <p>An familiar example of an infinite data structure:</p>
  
  <pre><code>fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
  </code></pre>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>One possible solution for this problem that I thought of is using an "unmemo-monad".</p>
  
  <p>I'll try to demonstrate what this monad is supposed to do using monadic lists:</p>
  
  <pre><code>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))
  </code></pre>
  
  <p>Using <code>nums :: [Int]</code>, the program would take a lot of memory as a reference to <code>nums</code> is needed by <code>lengthL nums</code> while it is being iterated over <code>foldlL (+) 0 nums</code>.</p>
  
  <p>The purpose of <code>Unmemo</code> is to make the runtime not keep the nodes iterated over.</p>
  
  <p>I attempted using <code>((-&gt;) ())</code> as <code>Unmemo</code>, but it yields the same results as <code>nums :: [Int]</code> does - the program uses a lot of memory, as evident by running it with <code>+RTS -s</code>.</p>
  
  <p>Is there anyway to implement <code>Unmemo</code> that does what I want?</p>