Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-15 Thread David Virebayre
2011/4/14 Sebastian Fischer fisc...@nii.ac.jp The advantage of this complicated definition is that you get a memoized version of the `fibonacci` function simply by using `fixmemo` instead of `fix`: Wow. I think something about 'fix' just made sense thanks to your post, though I had read a

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-15 Thread Sebastian Fischer
On Thu, Apr 14, 2011 at 8:02 PM, Luke Palmer lrpal...@gmail.com wrote: For this problem, it is too slow to memoize everything; you have to use a bounded memo table. That's why I use a combinator-based memo approach as opposed to the type-directed approach used in eg. MemoTrie. The memo table

[Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Dmitri O.Kondratiev
3n+1 is the first, warm-up problem at Programming Chalenges site: http://www.programming-challenges.com/pg.php?page=downloadproblemprobid=110101format=html (This problem illustrates Collatz conjecture: http://en.wikipedia.org/wiki/3n_%2B_1#Program_to_calculate_Collatz_sequences ) As long as the

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Felipe Almeida Lessa
This is very similar to the Problem 14 on Project Euler [1]. Should you really want a nice solution in Haskell, and noting that this is a big spoiler, there are some on the wiki [2]. But I highly recommend you to try coding your own solutions before looking at the site =). Cheers! [1]

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Steven Keuchel
Hi Dmitri, As a reference you might want to take a look at the Project Euler problem #14 and the corresponding dubious entry in the HaskellWiki: http://www.haskell.org/haskellwiki/Euler_problems/11_to_20#Problem_14 . *** Question: I wonder how to implement cache for this problem in Haskell? At

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Dmitri O.Kondratiev
Thanks, Felipe! Sure I will try to code solution myself. Doing it all by yourself is the main fun of everything, isn't it? I was just asking about the *idea* of implementing cache in Haskell, in general, not just in this case only. On Thu, Apr 14, 2011 at 3:11 PM, Felipe Almeida Lessa

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Ryan Ingram
So if we were to emulate your Java solution, we'd do import Data.Array cacheSize :: Int cacheSize = 65536 table :: Array Int Integer table = listArray (1,cacheSize) (1 : map go [2..cacheSize]) where go n | even n = 1 + lookup (n `div` 2) | otherwise = 1 + lookup (3 * n + 1)

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Dmitri O.Kondratiev
Thanks, everybody! Your feedback is a great food for my mind (as Lewis Carroll once wrote :) When asking how to implement cache in Haskell I was hopping that there exists some solution without using Data.Array, more functional approach, if I may say so ... I must be wrong, though (need more time

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Christian Maeder
Am 14.04.2011 12:29, schrieb Dmitri O.Kondratiev: 3n+1 is the first, warm-up problem at Programming Chalenges site: http://www.programming-challenges.com/pg.php?page=downloadproblemprobid=110101format=html http://www.programming-challenges.com/pg.php?page=downloadproblemprobid=110101format=html

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Sebastian Fischer
Hi Dimitri, When asking how to implement cache in Haskell I was hopping that there exists some solution without using Data.Array, more functional approach, if I may say so  ... Steven's second solution is purely functional. It uses so-called tries to cache results instead of mutable arrays.

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Luke Palmer
On Thu, Apr 14, 2011 at 4:29 AM, Dmitri O.Kondratiev doko...@gmail.comwrote: 3n+1 is the first, warm-up problem at Programming Chalenges site: http://www.programming-challenges.com/pg.php?page=downloadproblemprobid=110101format=html (This problem illustrates Collatz conjecture:

Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem

2011-04-14 Thread Eduard Sergeev
Hi Dmitri, *** Question: I wonder how to implement cache for this problem in Haskell? At the moment, I am not so much interested in the speed of the code, as in nice implementation. Yet another option for memoization implementation: to use monad-memo package [1] which provides memoization for