Re: [Haskell-cafe] laziness blowup exercise
On Thu, Jul 16, 2009 at 9:57 PM, Ryan Ingramryani.s...@gmail.com wrote: On Thu, Jul 16, 2009 at 8:22 PM, Thomas Hartmantphya...@gmail.com wrote: Is this being worked on? On Thu, Jul 16, 2009 at 12:35 PM, Bas van Dijkv.dijk@gmail.com wrote: I have no idea. Yes. Bolingbroke, Peyton-Jones. Types are calling conventions http://lambda-the-ultimate.org/node/3319 Thanks for the pointer to this interesting paper! However I dont't think that the type system explained in that paper is powerful enough to differentiate between these different iterates: iterate1, iterate2, iterate3, iterate4 :: (a - a) - a - [a] iterate1 f x = x : let nxt = f x in iterate1 f nxt iterate2 f x = let nxt = f x in nxt `seq` x : iterate2 f nxt iterate3 f x = x `seq` x : let nxt = f x in iterate3 f nxt iterate4 f x = x : let nxt = f x in nxt `seq` iterate4 f nxt The type system somehow has to express the growing and shrinking of the stack so that it can statically disallow: iterate1 (+ 1) 0 !! (10^6) :: Int fits in my stack and allow: iterate4 (+ 1) 0 !! (10^6) :: Int fits in my stack Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
Thomas, if you did no know, where to look for `lazy-memory-hole', say in your first example, how would you go about solving that puzzle systematically with a Profiler (or other tools)? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
I don't have a good answer to that, and I unable to reliably solve this type of problem, which is one reason I am posting around on haskell cafe hoping to accumulate wisdom. Here for instance I think I did t = last . take (10^6) $ repeat $ S.empty which doesn't blow up, and by process of elimination figured the process must be in iterate. I then looked at iterate by writing myiterate (could have also copied from hackage prelude) and thought about it until the answer (well, an answer, maybe not the best one) came myiterate f x = x : myiterate f (f x) In general, I feel like I don't do very well solving these types of problems. Am 17. Juli 2009 08:47 schrieb Matthias Görgens matthias.goerg...@googlemail.com: Thomas, if you did no know, where to look for `lazy-memory-hole', say in your first example, how would you go about solving that puzzle systematically with a Profiler (or other tools)? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
I tried using your original code and stuffing it into a profiler. But all I get is a triangle of linearly increasing resource usage, and then it breaks for lack of stack. I guess I am just to ignorant about retainer profiling and such stuff. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Wed, Jul 15, 2009 at 6:35 PM, Ryan Ingramryani.s...@gmail.com wrote: iterate' f x = x `seq` x : iterate' f (f x) seems better; it doesn't evaluate list elements you don't visit. iterate'' f x = x : (iterate'' f $! f x) ...seems the most lazy strict iterate. (Bas wishes for a type system that can express the different strictness properties of these functions...) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
the strict functions seem very nice, will they eventually make their way into http://hackage.haskell.org/packages/archive/Stream/0.3.2/doc/html/Data-Stream.html ? where is Control.Monad.StreamT? couldn't find it. 2009/7/15 Bas van Dijk v.dijk@gmail.com: On Wed, Jul 15, 2009 at 3:02 AM, Thomas Hartmantphya...@gmail.com wrote: Please suggest more of these types of exercises if you have them and maybe we can collect the folk wisdom into a wiki page and/or exercise page for beginners. My 'stream' library[1] also has some examples. Look at the following functions in 'Data.Stream': * mapAccum' * scan' * iterate' * unfold' There are similar examples in 'Control.Monad.StreamT'. [1] http://code.haskell.org/~basvandijk/code/stream/ (Not on Hackage) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
I played with this a bit, and ok, it seems the difference between iterate' and iterate'' is h _ = 2 tit' = head . drop 1 . iterate' h $ undefined tit'' = head . drop 1 . iterate'' h $ undefined (Bas wishes for a type system that can express the different strictness properties of these functions...) Is this being worked on? Could you give some example of type systems that can express differences between functions of along dimension x? Off the top of my head, I guess (?) with dependent types can tell the difference between total and partial functions... partials won't even compile, right? Are there others? Pointers appreciated. ...seems the most lazy strict iterate. could you expand on what you mean by this? 2009/7/16 Bas van Dijk v.dijk@gmail.com: On Wed, Jul 15, 2009 at 6:35 PM, Ryan Ingramryani.s...@gmail.com wrote: iterate' f x = x `seq` x : iterate' f (f x) seems better; it doesn't evaluate list elements you don't visit. iterate'' f x = x : (iterate'' f $! f x) ...seems the most lazy strict iterate. (Bas wishes for a type system that can express the different strictness properties of these functions...) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Thu, Jul 16, 2009 at 7:45 PM, Thomas Hartmantphya...@gmail.com wrote: the strict functions seem very nice, will they eventually make their way into http://hackage.haskell.org/packages/archive/Stream/0.3.2/doc/html/Data-Stream.html Note that there are two stream packages: * 'Stream' by Wouter Swierstra (including some patches by me) which can be found on hackage. * 'stream' (with a lower case 'l') by me which isn't (yet) on hackage. My stream package started as a set of patches against Stream. However the goal Wouter had with Stream was to create a small education-friendly package focusing on simplicity. This is fine. The goal of stream however is to create an industrial-strength package, focusing on functionality and efficiency. Maybe I upload 'stream' to hackage if there's demand for it... where is Control.Monad.StreamT? couldn't find it. http://code.haskell.org/~basvandijk/code/stream/Control/Monad/StreamT.hs regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Thu, Jul 16, 2009 at 8:22 PM, Thomas Hartmantphya...@gmail.com wrote: I played with this a bit, and ok, it seems the difference between iterate' and iterate'' is h _ = 2 tit' = head . drop 1 . iterate' h $ undefined tit'' = head . drop 1 . iterate'' h $ undefined Exactly, iterate' first evaluates 'undefined' which is undefined. iterate'' returns 'undefined : iterate'' h 2'. Which then evaluates to: 'undefined : 2 : iterate'' h 2'. So both iterates are strict in their accumulator. They differ in when they force it. The former is more strict in that it forces its accumulator on entry while the latter is more lazy by first returning the accumulator and later forcing it. (Bas wishes for a type system that can express the different strictness properties of these functions...) Is this being worked on? I have no idea. regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Thu, Jul 16, 2009 at 8:22 PM, Thomas Hartmantphya...@gmail.com wrote: Is this being worked on? On Thu, Jul 16, 2009 at 12:35 PM, Bas van Dijkv.dijk@gmail.com wrote: I have no idea. Yes. Bolingbroke, Peyton-Jones. Types are calling conventions http://lambda-the-ultimate.org/node/3319 -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Wed, Jul 15, 2009 at 3:02 AM, Thomas Hartmantphya...@gmail.com wrote: Please suggest more of these types of exercises if you have them and maybe we can collect the folk wisdom into a wiki page and/or exercise page for beginners. My 'stream' library[1] also has some examples. Look at the following functions in 'Data.Stream': * mapAccum' * scan' * iterate' * unfold' There are similar examples in 'Control.Monad.StreamT'. [1] http://code.haskell.org/~basvandijk/code/stream/ (Not on Hackage) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
On Tue, Jul 14, 2009 at 6:02 PM, Thomas Hartmantphya...@gmail.com wrote: myiterate f x = let nxt = f x in nxt `seq` x : myiterate f nxt iterate' f x = x `seq` x : iterate' f (f x) seems better; it doesn't evaluate list elements you don't visit. let test = 1 : 2 : 3 : undefined in last $ take 4 $ myiterate (test !!) 0 *** Exception: Prelude.undefined let test = 1 : 2 : 3 : undefined in last $ take 4 $ iterate' (test!!) 0 3 -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] laziness blowup exercise
Challenge: change one function in the following pipeline so that t doesn't blow up when executed in ghci. import qualified Data.Set as S t = last . take (10^6) . iterate f $ S.empty f s = S.delete 1 . S.insert 1 $ s Please suggest more of these types of exercises if you have them and maybe we can collect the folk wisdom into a wiki page and/or exercise page for beginners. spoiler for the above problem below :) myiterate f x = let nxt = f x in nxt `seq` x : myiterate f nxt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
