4 ms·

If you want to suggest that the main problem is people "trying to solve problems in the same way they've been solving problems all along", then you should have

If you want to suggest that the main problem is people "trying to solve problems in the same way they've been solving problems all along", then you should have an answer for how you implement memoization "the haskell way". If not, your "conclusion that Haskell's differences are what throw people off" is incorrect. I don't think the author of the email is "stereotyping the Haskellers as a bunch of ivory tower PhDs", he's relating a story that's actually true of finding out that a basic technique he wanted to implement was most easily implemented by following the technique in a PhD thesis.

astine 16y ago
Now, I could be very wrong, but it is my understanding that Lazy Evaluation will provide the main benefits of memoization, without any action on the part of the programmer.
- jongraehl 16y ago
  That's not generally true, although you can make it work out that way in some cases (I think threads mean that some work may be duplicated).
  - klodolph 16y ago
    Be careful lest thou misunderstand the GHC runtime, which is fairly subtle. In Haskell, the semantics are unchanged if the runtime evaluates a particular thunk multiple times. Haskell is fairly unique in this regard. For exactly this reason, Haskell threads do not need to synchronize when evaluating thunks in multicore environments. Synchronization has a cost, and that cost can exceed the cost of duplicate evaluation. It's a trade off.
- klodolph 16y ago
  True, that. For some functions, memoization in Haskell is dead easy. Like "fibs", which is generally a poor example function but it illustrates a technique you can use for dynamic programming in Haskell that doesn't work in strict languages: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Now, I don't know if this technique works for the function you're interested in. If you want something more general, you can do soemthing like: memoize :: Ord a => (a -> b) -> IO (a -> b) memoize f = do ref <- newIORef Map.empty return $ \x -> unsafePerformIO $ do m <- liftM (Map.lookup x) (readIORef ref) case m of Just y -> return y Nothing -> let y = f x in do modifyIORef ref (M.insert x y) return y That's just off the top of my head (probably has syntax errors, never mind the type checker), and it has a number of drawbacks. For one, the map will get larger and larger -- you could use a LRU purging scheme but that's more work than I'm doing today. It doesn't support polymorphic functions, this could be fixed with some extra care but because of the way "memoize" would have to work you'll need to know a decent amount about the Haskell type system. There, I responded to llimllib's ultimatum that somehow my conclusion was incorrect if I didn't personally know how to implement a memoization function. Can I have a cookie? That rant at the end of my post above was me venting frustrations, on a lot of Haskell forums I see people posting about how much they think Haskell is not the language for them and I think, "If it's not for you, can you go to a forum that's not about Haskell?"
johngunderman 16y ago
I had this discussion once, and was presented with the following options: Ideally, lazy evaluation will automatically memoize all your computations. Haskell's 'thunk' system does this in part. However, doing full memoization on most functions will result in huge memory bloat. Which brings us to the essential trade off of memory vs. cpu time. By default, GHC will conserve memory and memoize only when it is obvious that you want values cached. If you want memoization, there are a few things you can do. 1) Add 'let' clauses to your function bodies. GHC will automatically memoize these. 2) Add certain compiler flags for automatic memoization (I don't know what these are, but I know they exist) 3) do it "semi-manually" by generating closures. I'm sure there are other options, but these three are relatively simple to implement without even needing a memoize function (Though I'm sure one can be written).

astine 16y ago

Now, I could be very wrong, but it is my understanding that Lazy Evaluation will provide the main benefits of memoization, without any action on the part of the programmer.

jongraehl 16y ago
That's not generally true, although you can make it work out that way in some cases (I think threads mean that some work may be duplicated).
- klodolph 16y ago
  Be careful lest thou misunderstand the GHC runtime, which is fairly subtle. In Haskell, the semantics are unchanged if the runtime evaluates a particular thunk multiple times. Haskell is fairly unique in this regard. For exactly this reason, Haskell threads do not need to synchronize when evaluating thunks in multicore environments. Synchronization has a cost, and that cost can exceed the cost of duplicate evaluation. It's a trade off.
klodolph 16y ago
True, that. For some functions, memoization in Haskell is dead easy. Like "fibs", which is generally a poor example function but it illustrates a technique you can use for dynamic programming in Haskell that doesn't work in strict languages: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Now, I don't know if this technique works for the function you're interested in. If you want something more general, you can do soemthing like: memoize :: Ord a => (a -> b) -> IO (a -> b) memoize f = do ref <- newIORef Map.empty return $ \x -> unsafePerformIO $ do m <- liftM (Map.lookup x) (readIORef ref) case m of Just y -> return y Nothing -> let y = f x in do modifyIORef ref (M.insert x y) return y That's just off the top of my head (probably has syntax errors, never mind the type checker), and it has a number of drawbacks. For one, the map will get larger and larger -- you could use a LRU purging scheme but that's more work than I'm doing today. It doesn't support polymorphic functions, this could be fixed with some extra care but because of the way "memoize" would have to work you'll need to know a decent amount about the Haskell type system. There, I responded to llimllib's ultimatum that somehow my conclusion was incorrect if I didn't personally know how to implement a memoization function. Can I have a cookie? That rant at the end of my post above was me venting frustrations, on a lot of Haskell forums I see people posting about how much they think Haskell is not the language for them and I think, "If it's not for you, can you go to a forum that's not about Haskell?"

johngunderman 16y ago

I had this discussion once, and was presented with the following options: Ideally, lazy evaluation will automatically memoize all your computations. Haskell's 'thunk' system does this in part. However, doing full memoization on most functions will result in huge memory bloat. Which brings us to the essential trade off of memory vs. cpu time. By default, GHC will conserve memory and memoize only when it is obvious that you want values cached. If you want memoization, there are a few things you can do. 1) Add 'let' clauses to your function bodies. GHC will automatically memoize these. 2) Add certain compiler flags for automatic memoization (I don't know what these are, but I know they exist) 3) do it "semi-manually" by generating closures. I'm sure there are other options, but these three are relatively simple to implement without even needing a memoize function (Though I'm sure one can be written).