News for hackers. Stuff that matters.
Re:Do I really want to be using a language where memoize is ... by masklinn on Tuesday July 20, 2010 @06:57AM (#1531683)
> This argument comes up against haskell over and over again and I think it is because it has some merit.

Yes and no. As with many other things, there's a tradeoff between Haskell's purity and referential transparency and side-effecting constructs such as storing stuff in a local cache, which is what memoization does. You can't litter printfs or cache calls throughout your pure functions either, "for some reason". It makes sense that's it's a pain to do in a (non-IO/state) haskell function, because those are very much about mixing side-effects into the code.

A better solution would probably be to integrate memoization at the runtime level, with some compiler hints maybe. That way it becomes an implementation detail not an imperative side-effect, and the world is pure again.

Anyway yeah, if you can't bear with Haskell's constraints you can just use something else, such as MLs (in order not to give up static type safety). Whoop the fucking do.

Re:Do I really want to be using a language where memoize is ... by klodolph on Tuesday July 20, 2010 @07:57AM (#1531775)
You can litter printfs in your code, you'll just get a lot of hate if you do it in library code that you share. It's fine when debugging to write a "debug printf" function using "unsafePerformIO". Yes, it mixes side effects into pure code, but that's fine for debugging purposes.

    -- totally OK! go ahead! it won't crash or anything!
    debugPrint :: String -> a -> a
    debugPrint s x = unsafePerformIO (putStrLn s >> return x)
You could also implement a memoization function using "unsafePerformIO". No, you won't get a visit from the FP purity police for doing so, it's perfectly fine. Why? Using "unsafePerformIO" in a function does NOT mean that that function is impure. It merely means that the compiler will not inform you whether the function is pure or impure -- the compiler's safety checks are bypassed when you use the function.

Here's how I'd type the memoize function:

    memoize :: Ord a => (a -> b) -> IO (a -> b)
Notice how it gives you a pure function out. No need to do stuff at the runtime level, or write compiler hints. It just works. If you want to memoize some nasty function:

    -- Totally fine! Unless nastyFunction is polymorphic...
    nastyFunction :: Paper -> PublishedBook
    nastyFunctionMemoized = unsafePerformIO (memoize nastyFunction)
If you're new to Haskell, don't write memoize yourself if you want a version that works with polymorphic functions as that requires some more advanced techniques. Most people who need a memoized function don't need a polymorphic one though.
Re:Do I really want to be using a language where memoize is ... by yummyfajitas on Tuesday July 20, 2010 @08:08AM (#1531795)
You could also just use Debug.Trace.trace.

http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4...

Re:Do I really want to be using a language where memoize is ... by masklinn on Tuesday July 20, 2010 @08:07AM (#1531790)
> You can litter printfs in your code, you'll just get a lot of hate if you do it in library code that you share. It's fine when debugging to write a "debug printf" function using "unsafePerformIO".

Well obviously but I considered we were ignoring such "hacks" as unsafePerformIO. If you introduce it, then all of that is trivial to do so the discussion has no reason to be.

Re:Do I really want to be using a language where memoize is ... by klodolph on Tuesday July 20, 2010 @08:35AM (#1531832)
The function "unsafePerformIO" is not a hack, it is the tool that allows you to write safe functions with the correct, pure type signature even though the compiler cannot prove that the function is safe.

For example, suppose you write "memoize" without using "unsafePerformIO". Here's the resulting type signature:

    badMemoize :: Ord a => (a -> b) -> IO (a -> IO b)
The resulting output has type "a -> IO b", but it doesn't actually do IO and it has no side effects! It's a normal, pure, referentially transparent function, and it shouldn't be in the IO Monad. The correct signature is "a -> b", just like the input. The "unsafePerformIO" function is a non-hack used by careful programmers to expose pure interfaces to code that uses impure constructs.

See the FFI tutorials for more examples of using unsafePerformIO.

(Of course, unsafe does mean unsafe... you can easily cause segfaults with that thing, you have to use it correctly.)

Re:Do I really want to be using a language where memoize is ... by masklinn on Tuesday July 20, 2010 @11:24AM (#1532311)
> The function "unsafePerformIO" is not a hack, it is the tool that allows you to write safe functions with the correct, pure type signature even though the compiler cannot prove that the function is safe.

It is a hack, since it subverts the type system. It allows you to write safe functions with a pure (and potentially lying) type signature, but it also has no problem letting you create completely unsafe and broken functions.

> The resulting output has type "a -> IO b", but it doesn't actually do IO and it has no side effects!

Of course it does in its implementation, you do have to fill the memoization cache on a miss don't you?

> The "unsafePerformIO" function is a non-hack used by careful programmers to expose pure interfaces to code that uses impure constructs.

I don't agree with the first part of your declaration. At all.

> Of course, unsafe does mean unsafe... you can easily cause segfaults with that thing, you have to use it correctly.

And that's why it's a hack, just as using bit shifting instead of multiplication or division is a hack as it relies on the implementation details of the language and the hardware infrastructure. Yeah careful programmers can use it to wring out the latest drop of performance out of their software (assuming there is no optimizing compiler on the platform), but it's still a hack.

Re:Do I really want to be using a language where memoize is ... by applicative on Tuesday July 20, 2010 @11:47AM (#1532383)
I don't get this, what is hackish or immoral about this:

http://hackage.haskell.org/packages/archive/bytestring/0.9.0...

which makes as many uses of unsafePerformIO as it exports functions, and the beautiful pure interface that is thereby created:

http://hackage.haskell.org/packages/archive/bytestring/0.9.0...

It seems to me that there is an element of hypocrisy in some of the complaints above; it is as if they were saying:

> In Haskell, it's a nightmare to define a pure function with IO. You have to use that dreadful hack `unsafePerformIO`! In practical languages, by contrast, we are spared this boilerplate, since basically every line is already unsafePerformIO.

Re:Do I really want to be using a language where memoize is ... by masklinn on Tuesday July 20, 2010 @12:39PM (#1532563)
> It seems to me that there is an element of hypocrisy in some of the complaints above; it is as if they were saying

Apart from the "nightmare" part, this statement you made up happens to be factually true. What is your issue with it? It's exactly what happens: in most other langages, every line is indeed unsafePerformIO. Isn't that fact one of the reasons Haskellers give for using haskell in the first place?

Re:Do I really want to be using a language where memoize is ... by jrockway on Tuesday July 20, 2010 @09:08PM (#1534003)
We use Haskell so that 99% of the time, the compiler can prove our program safe. Then, the other 1% of the time, we use our human intuition to decide to "gamble" and disagree with the compiler.

In most languages, 100% of your code is that same gamble.

Re:Do I really want to be using a language where memoize is ... by klodolph on Wednesday July 21, 2010 @07:58AM (#1534945)
I think you don't understand the Haskell runtime.

    let x = [1..]
    in do print (x !! 1000000)
          print (x !! 1000000)
Element #1000000 (counting from zero) of the list "x" is printed out twice. The first time, "x" is a thunk. That thunk is evaluated, and the runtime stores the resulting value back into "x". The second time, "x" is a constructor, so it does not need to be evaluated. You'll see the memory usage spike after the first "print" to account for the million cons cells allocated.

This is no different than the interface provided by the memoization function. What distinguishes pure from impure is not memory access -- memory MUST always be modified in order to perform calculation. I recommend reading the Haskell report section on semantics.

Re:Do I really want to be using a language where memoize is ... by joeyh on Tuesday July 20, 2010 @12:16PM (#1532484)
So is there a memoization library in hackage that uses unsafePerformIO?
Re:Do I really want to be using a language where memoize is ... by applicative on Tuesday July 20, 2010 @01:14PM (#1532687)
Check out the source for, e.g.

http://hackage.haskell.org/package/stringtable-atom

There are a number of generalized memoization libraries. This one

http://hackage.haskell.org/package/data-memocombinators

doesn't use `unsafePeformIO`, but instead imports the Array package. If you check out

http://hackage.haskell.org/packages/archive/array/0.2.0.0/do...

you will find 696 uses of "unsafe" in one module...

http://hackage.haskell.org/package/MemoTrie

by contrast takes a different approach.

Re:Do I really want to be using a language where memoize is ... by joeyh on Tuesday July 20, 2010 @04:12PM (#1533293)
AFAICS, there is no unsafePerformIO in any of the above except for stringtable-atom.

AIUI, it's possible to implement generalized memoization in haskell w/o unsafePerformIO, and both memocombinators and MemTrie do so. I take your point that if necessary, they could have been written to use unsafePerformIO, and as long as the library authors know what they're doing, and are careful, that would be OK.

So, you don't actually need to read CS papers to do memoization in haskell. You just need to know that the libraries that do it have "memo", not "memoize" in their names. This stuff, could, perhaps be easier to find.

Re:Do I really want to be using a language where memoize is ... by applicative on Tuesday July 20, 2010 @09:01PM (#1533990)
You are repeating what I said. I was defending the use of `unsafePerformIO` as a non-'hack', and perhaps I misunderstood you to be thinking otherwise. The memocombinators library uses Array, which uses `unsafePerformIO` and friends almost 700 times in one module. MemTrie takes a different approach, one not using unsafePerformIO; maybe I wasn't clear that was my meaning. In any case, there is little need for a library, at least for the simplest idea of memoization (the ugly Reddit discussion suggests there are many things to be meant.) It is just a case of writing down what is meant, as happens a few times in slightly different ways on the reddit page, off the top of peoples' heads. So for example this one:

    memo :: Eq k => (k -> v) -> k -> v
    memo f = unsafePerformIO $ do
      ref <- newIORef [] :: IO (IORef [(k,v)])  -- make a page for a table
      return $ \k -> unsafePerformIO $ do       -- when f is applied to k
        memotable <- readIORef ref              -- get out the table
        case lookup k memotable of              -- see if k has been done
          Just x -> return x                    -- if it has, we're done!
          Nothing -> do                         -- if it hasn't
            let a = f k                         -- calculate f k
            atomicModifyIORef ref $ \t -> ((k,a):t,()) -- add it to the table before
            return a                            -- returning f k
This is someone's brief treatment, which meets most of the definitions people were using. The clojure procedure is more powerful; as far as I can see, getting something similar in Haskell requires a bit more subtlety.