Control.Monad.Writer as Python generator
Hi, I was thinking to myself: What in Haskell would give me a "yield" command like a Python generator? And the answer was "tell" in Control.Monad.Writer -- and I wrote some simple examples (see below). Most Python code using yield would be translated to something much more idiomatic in Haskell than using Writer, or to something more complicated if it needed IO. I thought this interesting enough to put on the haskell mailing list and wiki since it seemed to be in neither place (I searched, but your searching may be better than mine). If there are no objections then I'll put this example on the wiki; any suggestions where on wiki to place it (e.g. MonadWriter)? === CUT HERE === import Control.Monad.Writer -- Some type signatures would need -fglasgow-exts to compile -- We only care about the Writer output, not the function return value asGenerator :: Writer [a] v -> [a] asGenerator writer = values where (_,values) = runWriter writer --yield :: (MonadWriter [a] m) => a -> m () yield x = tell [x] -- This allows several items to be yielded with one command --yieldMany :: (MonadWriter [a] m) => [a] -> m () yieldMany = tell zeros :: [Integer] zeros = asGenerator (do yield 0 yield 0 yield 0) zerosInf :: [Integer] zerosInf = asGenerator zeros' where zeros' = (yield 0 >>zeros') -- The Collatz sequence function foo :: (Integral a) => a -> a foo x = case (x `mod` 2) of 0 -> x `div` 2 1 -> (3*x+1) -- Uses "return ()" to end the list when 1 is reached --collatzW :: (MonadWriter [a] m, Integral a) => a -> m () collatzW x = do yield x case x of 1 -> return () _ -> collatzW (foo x) -- Keeps going, will repeat "1,4,2,1,.." if 1 is reached --collatzInfW :: (MonadWriter [a] m, Integral a) => a -> m t collatzInfW x = do yield x collatzInfW (foo x) --collatzGen :: (MonadWriter [a] (Writer [a]), Integral a) => a -> [a] collatzGen x = asGenerator (collatzW x) --collatzInfGen :: (MonadWriter [a] (Writer [a]), Integral a) => a -> [a] collatzInfGen x = asGenerator (collatzInfW x) -- And these can be combined collatz1 x = asGenerator (collatzW x >> yield 0 >> collatzW (x+1)) === CUT HERE === *Main> zeros [0,0,0] *Main> take 10 zerosInf [0,0,0,0,0,0,0,0,0,0] *Main> collatzGen 13 [13,40,20,10,5,16,8,4,2,1] *Main> take 100 $ collatzInfGen 13 [13,40,20,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2, 1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2, 1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1] *Main> collatz1 12 [12,6,3,10,5,16,8,4,2,1,0,13,40,20,10,5,16,8,4,2,1]
ChrisK writes:
I was thinking to myself: What in Haskell would give me a "yield" command like a Python generator?
And the answer was "tell" in Control.Monad.Writer -- and I wrote some simple examples (see below).
Another possibility would be a continuation monad. import Control.Monad.Cont yield :: a -> Cont [a] () yield x = Cont (\c -> x : c ()) asGenerator :: Cont [a] v -> [a] asGenerator (Cont f) = f (const []) -- David Menendez <zednenem@psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"
Thanks for the Cont example, David. But... The MonadCont is clever and it works ... but then fails -- ghci does not garbage collect and it blows up. With the MonadCont version I can count up to 10^7 zeros: *Main> length $ take (10^7) zerosInf 10000000 (26.20 secs, 0 bytes) But this increases RSIZE of ghc-6.4 to 165MB. The 10^8 version goes to swap space and I had to kill it. My original MonadWriter version does not increase RSIZE when run (constant space), so the garbage collection must be working, and it is O(N) in the # of zeros counted: *Main> length $ take (10^7) zerosInf 10000000 (1.22 secs, 0 bytes) *Main> length $ take (10^8) zerosInf 100000000 (10.05 secs, 0 bytes) *Main> length $ take (10^9) zerosInf 1000000000 (109.83 secs, 6 bytes) -- Chris On Apr 14, 2005, at 1:05 AM, David Menendez wrote:
ChrisK writes:
I was thinking to myself: What in Haskell would give me a "yield" command like a Python generator?
And the answer was "tell" in Control.Monad.Writer -- and I wrote some simple examples (see below).
Another possibility would be a continuation monad.
import Control.Monad.Cont
yield :: a -> Cont [a] () yield x = Cont (\c -> x : c ())
asGenerator :: Cont [a] v -> [a] asGenerator (Cont f) = f (const []) -- David Menendez <zednenem@psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"
However, after compiling with optimisations turned on, there is no such problem with the continuation-based version, memory usage appears constant. - Cale On 4/14/05, ChrisK <chrisk@mit.edu> wrote:
Thanks for the Cont example, David. But...
The MonadCont is clever and it works ... but then fails -- ghci does not garbage collect and it blows up. With the MonadCont version I can count up to 10^7 zeros:
*Main> length $ take (10^7) zerosInf 10000000 (26.20 secs, 0 bytes)
But this increases RSIZE of ghc-6.4 to 165MB. The 10^8 version goes to swap space and I had to kill it. My original MonadWriter version does not increase RSIZE when run (constant space), so the garbage collection must be working, and it is O(N) in the # of zeros counted:
*Main> length $ take (10^7) zerosInf 10000000 (1.22 secs, 0 bytes) *Main> length $ take (10^8) zerosInf 100000000 (10.05 secs, 0 bytes) *Main> length $ take (10^9) zerosInf 1000000000 (109.83 secs, 6 bytes)
-- Chris
You are correct. Moand.Cont yield even runs without -O optimizing, just slower: Monad.Writer counts 10^9 zeros in 99 seconds (user time) Monad.Cont counts 10^8 zero in 35 seconds user time. So the writer is 3.5 times faster without '-O' With -O Monad.Writer counts 10^9 zeros in 105 seconds Monad.Cont counts 10^8 zeros in 11 seconds, 10^9 zeros in 110 seconds. So with '-O' they are the same speed. Nice. Anyone have an idea why ghci can't garbage collect it? Is this an actual bug or an innate quirk of the REPL ? -- Chris On Apr 15, 2005, at 12:43 AM, Cale Gibbard wrote:
However, after compiling with optimisations turned on, there is no such problem with the continuation-based version, memory usage appears constant.
- Cale
On 4/14/05, ChrisK <chrisk@mit.edu> wrote:
Thanks for the Cont example, David. But...
The MonadCont is clever and it works ... but then fails -- ghci does not garbage collect and it blows up. With the MonadCont version I can count up to 10^7 zeros:
*Main> length $ take (10^7) zerosInf 10000000 (26.20 secs, 0 bytes)
But this increases RSIZE of ghc-6.4 to 165MB. The 10^8 version goes to swap space and I had to kill it. My original MonadWriter version does not increase RSIZE when run (constant space), so the garbage collection must be working, and it is O(N) in the # of zeros counted:
*Main> length $ take (10^7) zerosInf 10000000 (1.22 secs, 0 bytes) *Main> length $ take (10^8) zerosInf 100000000 (10.05 secs, 0 bytes) *Main> length $ take (10^9) zerosInf 1000000000 (109.83 secs, 6 bytes)
-- Chris
On Fri, 15 Apr 2005 12:03:01 -0400 ChrisK <chrisk@MIT.EDU> wrote:
You are correct. Moand.Cont yield even runs without -O optimizing, just slower:
Monad.Writer counts 10^9 zeros in 99 seconds (user time) Monad.Cont counts 10^8 zero in 35 seconds user time. So the writer is 3.5 times faster without '-O'
With -O Monad.Writer counts 10^9 zeros in 105 seconds Monad.Cont counts 10^8 zeros in 11 seconds, 10^9 zeros in 110 seconds.
So with '-O' they are the same speed. Nice.
Anyone have an idea why ghci can't garbage collect it? Is this an actual bug or an innate quirk of the REPL ?
GHCi does not "compile" with optimizations, without -O the strictness analyzer isn't run. The difference is most likely due to strictness analysis. A well placed strictness annotation or two should be able to make it work in GHCi as well. A similar situation occurs with sum: in GHCi for large inputs it overflows the stack, but when compiled with -O it works correctly, this is because sum is defined with foldl and not foldl' in GHC.
You are correct. Moand.Cont yield even runs without -O optimizing, just slower ... Anyone have an idea why ghci can't garbage collect it? Is this an actual bug or an innate quirk of the REPL ?
GHCi does not "compile" with optimizations, without -O the strictness analyzer isn't run.
The optimizer is irrelevant to whether it runs in constant space, as ghc without '-O' runs it just fine. The optimizer is only useful for speed, which is not the issue.
The difference is most likely due to strictness analysis. A well placed strictness annotation or two should be able to make it work in GHCi as well.
In this code, adding a strictness $! did not work.
A similar situation occurs with sum: in GHCi for large inputs it overflows the stack, but when compiled with -O it works correctly, this is because sum is defined with foldl and not foldl' in GHC.
As for adding one strictness annotation, the brute for approach to adding '$!' did not work: yield :: a -> Cont [a] () -- original --yield x = Cont (\c -> x : c () ) -- original in prefix form --yield x = Cont (\c -> (((:) x) (c ()))) -- memory exhaustion -- non-trivial --yield x = Cont (\c -> (((:) x) $! (c ()))) -- stack overflow -- silly --yield x = Cont (\c -> (((:) $! x) (c ()))) -- memory exhaustion -- definitely silly --yield x = Cont (\c -> (((:) x) (c $! ()))) -- memory exhaustion So adding two '$!' to the above looks like a non-starter. The asGenerator definition is asGenerator :: Cont [a] v -> [a] asGenerator (Cont f) = f (const []) which has no useful place to insert a '$!'. So to use continuations in GHCI, it may be necessary to build a new version of Cont and its internals, or maybe use the callCC interface? And I had not luck adding '$!' to callCC/Cont or callCC/mapCC versions: -- yield using callCC yieldCC x = callCC genContCCArg where genContCCArg = (\oldGenContFunc -> let newCont = Cont { runCont = newRunCont } newRunCont = (\contFunc -> (x:(oldRunCont contFunc))) oldRunCont = runCont oldCont oldCont = oldGenContFunc () in newCont ) -- Use the mysterious mapCont function yieldM x = callCC genContCCArg where genContCCArg = (\genContFunc -> mapCont (\xs -> x:xs) (genContFunc ())) I found no useful explanation of mapCont via Google. It was another case of deriving the function's action from the type. Since this is now a "gchi problem", should this be taken to the ghc mailing list as well? instead? -- Chris
On Apr 15, 2005, at 6:07 PM, ChrisK wrote:
You are correct. Moand.Cont yield even runs without -O optimizing, just slower ... Anyone have an idea why ghci can't garbage collect it? Is this an actual bug or an innate quirk of the REPL ?
GHCi does not "compile" with optimizations, without -O the strictness analyzer isn't run.
The optimizer is irrelevant to whether it runs in constant space, as ghc without '-O' runs it just fine. The optimizer is only useful for speed, which is not the issue.
Not true! The optimizer can change the asymptotic space consumption of your program. The example of sum is particularly germaine. If we write: x = foldl (+) 0 [1..n] this will, as it is evaluated, generate the suspended computation (((....((((0 + 1) + 2) + 3) + ...) + n This require O(n) space. Whereas the strict foldl' will evaluate each parenthesized expression as it is encountered: (0+1) = 1 (1+2) = 3 (3+3) = 6 (6+4) = 10 ... (... + n) = your answer If only we all used mostly-eager evaluation, these kinds of confusions would [almost] never happen. -Jan-Willem Maessen
On Apr 15, 2005, at 7:03 PM, Jan-Willem Maessen wrote:
On Apr 15, 2005, at 6:07 PM, ChrisK wrote:
You are correct. Moand.Cont yield even runs without -O optimizing, just slower ... Anyone have an idea why ghci can't garbage collect it? Is this an actual bug or an innate quirk of the REPL ?
GHCi does not "compile" with optimizations, without -O the strictness analyzer isn't run.
The optimizer is irrelevant to whether it runs in constant space, as ghc without '-O' runs it just fine. The optimizer is only useful for speed, which is not the issue.
Not true! The optimizer can change the asymptotic space consumption of your program. The example of sum is particularly germaine. If we write:
x = foldl (+) 0 [1..n]
this will, as it is evaluated, generate the suspended computation (((....((((0 + 1) + 2) + 3) + ...) + n
This require O(n) space.
I was writing in the context of the yield with Monad.Cont example. The 'it' in 'whether it run in constant space' is the yield example of "length $ take (10^7) zerosInf". Nothing more general. So I agree with your statement, that asymptotic space consumption can change with optimization. The odd thing is that ghc (without -O) compiles and run the example in question, but ghci will fail. So I was wondering if there was an implementation of yield using continuations that would make yield space efficient in ghci. Perhaps I should also check hugs, but I have not used hugs yet. -- Chris
participants (5)
-
Cale Gibbard -
ChrisK -
David Menendez -
Derek Elkins -
Jan-Willem Maessen