News for hackers. Stuff that matters.
Re:Do I really want to be using a language where memoize is ... by skm on Tuesday July 20, 2010 @09:43AM (#1532008)
Actually, arrays in Haskell are automatically memoized and lazily evaluated. So in most practical situations you get memoization for free.

For example, imagine you need to calculate a function f(n) for various values of n (let's say for n ranging from 0 to N). You simply define an array memo_f such that memo_f!n = f(n). ('!' is the array selection operator in Haskell).

Because Haskell evaluates lazily (i.e. not until it absolutely has to), it simply stores a link to the definition of the function for each array element. But once a particular array element is used, that link is replaced by the calculated answer.

I'll post some actual code to demonstrate this in a minute, just in case anyone's interested.

Re:Do I really want to be using a language where memoize is ... by skm on Tuesday July 20, 2010 @09:57AM (#1532050)
Haskell code: (explanation below)

    import Data.Array
    
    f :: Integer -> Integer
    f n = sum [0..n]
    
    largeNumber = round 2e6 :: Integer
    
    memo_f :: Array Integer Integer
    memo_f = listArray (0,largeNumber) [ (f n) | n <- [0..largeNumber] ] 
    
    
    main = do
        putStrLn (show (memo_f!largeNumber))     -- slow
        putStrLn (show (memo_f!(largeNumber-1))) -- slow
        putStrLn (show (memo_f!(largeNumber)))   -- fast
        putStrLn (show (memo_f!(largeNumber-1))) -- fast
        putStrLn (show (memo_f!(largeNumber-2))) -- slow
        putStrLn (show (memo_f!(largeNumber-3))) -- slow
        putStrLn (show (memo_f!(largeNumber)))   -- fast
        putStrLn (show (memo_f!(largeNumber-2))) -- fast
        putStrLn (show (memo_f!(largeNumber-4))) -- slow
        putStrLn (show (memo_f!(largeNumber-5))) -- slow


When I run this, I see nothing for about 3 seconds (that's the time spent setting up the array). Then the numbers commented '-- slow' take about 1/3 second to print, while the numbers commented '--fast' print instantaneously, because they were calculated previously. (I'm on a recent macbook air, in case anyone's curious about the timings). Obviously to calculate the entire array of values would take far too long (like a week or so).
Re:Do I really want to be using a language where memoize is ... by yaroslavvb on Tuesday July 20, 2010 @01:54PM (#1532841)
Well, that looks easy...so why are people saying that writing memoization in Haskell is PhD-thesis level task?
Re:Do I really want to be using a language where memoize is ... by silentbicycle on Tuesday July 20, 2010 @02:32PM (#1532988)
Some people seem to think "a task described in a phD thesis" implies "a phD-level task". "Oh, crap, dude! This expects me to read a phD thesis! I'd better wait until somebody on reddit summarizes a blog post about a blog post about it."

By that logic, implementing Lisp is "a phD-level task", too. (http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf) (http://www.cs.indiana.edu/~dyb/papers/3imp.pdf) (http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AITR...) *

* The third is actually a masters thesis, but whatever.

Re:Do I really want to be using a language where memoize is ... by jrockway on Tuesday July 20, 2010 @07:57PM (#1533868)
Because memoization is best implemented in the compiler and runtime, and the person on the Clojure list wanted to implement it in his application.
Re:Do I really want to be using a language where memoize is ... by silentbicycle on Tuesday July 20, 2010 @11:30PM (#1534256)
I've seen people get exasperated trying to implement "if" in Prolog, too. The whole language is already an 'if' / pattern matching engine!

("How do you implement lazy evaluation in Haskell? No, like, in an application...")

Re:Do I really want to be using a language where memoize is ... by jrockway on Wednesday July 21, 2010 @01:59AM (#1534486)
Yeah, lazy evaluation can be surprising (in a good way). Once you get in the mindset of thinking "this is going to be hard", you start programming Haskell like you would C, and while it works, you feel stupid when you realize you just rewrote the Haskell compiler. Poorly.

(Personally, I have done this a number of times. I remember writing some dependency evaluation system, with a central data structure that looked something like:

   data Dependency a e = Thunk (e -> a) | Resolved a
with a bunch of code to turn a set of Thunks into Resolved when necessary.

But of course, Haskell always does this anyway!)

I was also surprised when I was on Windows and needed the "head" utility to look at the first line of a file, but didn't have it installed. Since I had a ghci session going, I just wrote:

   readFile "foo.csv" >>= putStrLn . unlines . take 10 . lines
Half-expecting it to error out because the file didn't fit into memory. Nope! Problem solved!

(And yes, I know unsafeInterleaveIO is evil.)

Re:Do I really want to be using a language where memoize is ... by skm on Tuesday July 20, 2010 @03:30PM (#1533194)
I suspect because writing memoization means controlling memoization, and controlling memoization in Haskell means either hacking the compiler, or dealing with state, and state means monads, and nobody likes monads. (Except those people who love monads, of course).