12 ms·
Do I really want to be using a language where memoize is a PhD-level topic?
- greenlblue 16y agoThis argument comes up against haskell over and over again and I think it is because it has some merit. Type level hackery and monad wizardry are great but it just feels like a whole bunch of smart people showing off about how clever they can be with avoiding state and pushing it all into some high level categorical constructs.
- masklinn 16y ago> 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.
- klodolph 16y agoYou 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.
- masklinn 16y ago> 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.
- klodolph 16y agoThe 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.)
- masklinn 16y ago> 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.
- yason 16y agoI've criticized Haskell many times, and being criticized many times of that. You see, I would love to love Haskell but in practice the language just always turns out to be an overly intellectual exercise. Real world programs need to manage state, preferably in a very controlled way, but the bottom line is that they need to do that in some obvious and easy way. It doesn't help if you explain me that you really don't need to explicitly store state anywhere, that you can just use monads to carry it over from computation to computation. Monads are an interesting abstraction per se but I don't want to use such heavy-weight artillery to make a mere assignment, to write a pointer to memory. I want my language to put some effort in protecting myself from the hazards of unintended concurrency but when I want to do it, the language must obey. That said, Clojure is just perfect. For now, Clojure is my Blub.
- klodolph 16y agoIt sounds like Haskell just isn't your style, but you're saying that Haskell is bad for "real-world" programming. And it sounds like you've never really used Haskell seriously (just a guess, most Haskellers I've met get over their monad fixation within a few months, yet you describe them as "artillery"). If you like Clojure so much, why not go champion that instead of complaining about Haskell? Besides, if you use "how easy is it to implement 'memoize'" as a benchmark then you'll always end up choosing a Lisp.
- swannodette 16y agoSupporting Haskell and complaining about Haskell are both valid activities. There's plenty to complain about Clojure. However, the post does point out quite succinctly that while Haskell features might be incredible for simplifying many kinds of problems, it's shocking how many simple problems become staggeringly complex in Haskell.
- plinkplonk 16y ago"while $Language features might be incredible for simplifying many kinds of problems, it's shocking how many simple problems become staggeringly complex in $Language." Replace "$Language" with almost any computer language in existence and that statement is true (given appropriately chosen values of "simple problems" and "staggeringly complex"). So it reduces to, "For any given language some things are simple and others complex. For other languages what is simple and complex differ". Not saying much, really.
- jrockway 16y agoThe description you give of "type-level hackery" and "monad wizardry" leads me to believe that you don't really understand what's going on. This is dangerous, because you are expecting these things to be complicated, but they are actually so simple that you've probably already invented them in your own computer programs. The Haskell community merely gives names to ideas you already know about. This isn't "smart people showing off about how clever they can be", it's people giving names to things that they use everyday. The problem people have with monads is that the word "Monad" does not describe something they're used to dealing with. A computer programmer is used to concrete things like lists, trees, functions, compilers; things you could hold in your hand (or at least draw on a whiteboard), poke at, and observe. Monads can't be understood in this way, because they are not anything concrete; "Monad" is a word to describe concrete things that, individually, are all very different. It's like explaining the concept of "Green" to someone by showing them an apple, a tennis ball, and some grass clippings. They will never understand "Green", because you can't understand what Green is by seeing three examples of them. Green is a color, not some sort of weird tennis-ball-apple-grass-clipping hybrid. Monads are the same way. List is a Monad. Reader is a Monad. State is a Monad. But when you look at these things and try to generalize, you might not see the parts that are the same, because the parts that are the same that make them all monads are hard to see. I think the hard part is that you hear about what defines a monad ("return" and "bind" or "return", "fmap", and "join"), and don't see how some dual or triple like that helps you write computer programs. Each set of functions is so different from the other sets that the fact that they are all called "return" and "bind" doesn't seem to matter. And that's exactly right; at some level, it doesn't matter. You use a List as a monad to combine computations that return multiple values, and you use Cont to write your programs in a continuation-passing style. Very different. Nothing similar at all, really. On the concrete level. The similarity does matter at a higher level, though; noticing similarities means you can write parts of your program in advance, and just tweak those parts for each specific case. An example is liftM2; it abstracts away the tedium of using a calling a two-arg function with monad-like semantics. If there were no similarities between List and Maybe, you'd have to write something like this: liftList2 f xs ys = concat $ (\x -> concat $ (\y -> [f x y]) `map` ys) `map` xs -- this doesn't compile; I want to use more descriptive words than the Data.Maybe API does :) liftMaybe2 f x y = if has x then extract x -> \x' if has y then extract y -> \y' makeMaybe f x' y' else Nothing else Nothing (Here's how to use the functions, in case you aren't sure: liftList2 (,) [1,2] [3,4] ==> [(1,3),(1,4),(2,3),(2,4)] liftList2 (,) [] [1..infinity] ==> [] liftMaybe2 (,) (Just 10) (Just 20) ==> Just (10, 20) liftMaybe2 (,) Nothing (Just "oh hai") ==> Nothing .) These seem very similar. There is the same sort of nesting in both structures, we seem to be saying the same thing twice in both functions. We seem to be applying functions to values "inside" each of these things. Maybe we can abstract those things away somehow, and make the two functions look a little more similar: newList x = [x] fmapList xs f = f `map` xs -- joinList xs = concat xs liftList2 f xs ys = joinList $ fmapList xs $ \x -> joinList $ fmapList ys $ \y -> newList $ f x y -- hey, the code looks nicer already! newMaybe x = Just x fmapMaybe Nothing _ = Nothing fmapMaybe (Just x) f = Just $ f x joinMaybe Nothing = Nothing joinMaybe (Just x) = x liftMaybe2 f x y = joinMaybe $ fmapMaybe x $ \x' -> joinMaybe $ fmapMaybe y $ \y' -> newMaybe $ f x' y' Now that we've given List and Maybe some common terminology, it's very hard not to see how these lift2 functions are nearly identical. We just need to do some refactoring, and then we can use the same definition for both! class Monad m where new :: a -> m a fmap :: m a -> (a -> b) -> m b join :: m (m a) -> m a instance Monad [] where -- haskell98 spells List as [] new = newList fmap = fmapList join = joinList instance Monad Maybe where new = newMaybe fmap = fmapMaybe join = joinMaybe liftM2 f x y = join $ fmap x $ \x' -> join $ fmap y $ \y' -> new $ f x' y' And there you go, that's what a Monad is. It's just refactoring, so we have less code to maintain! That's what any programmer would do, not just super-smart PhDs. You do the same thing every day!
- WorkerBee 16y agotopic is a dud link - it takes me to a login page.
- plinkplonk 16y agohere it is so you don't have to log in. " On Mon, Jul 19, 2010 at 4:34 PM, Jared <tri...@gmail.com> wrote: > I am curious; for the people with Haskell experience why did you decide to use Clojure? I am asking this because Haskell and Clojure seem to solve similar types of problems. When would you want to use Haskell instead of Clojure and visa-versa? [Mark Engelberg replies] I think stateful things are too hard to do in Haskell, and they are an important part of most real-world programs. Clojure's blend of persistent data structures with a variety of reference-type objects that can contain them feels much more pragmatic to me. Also, I'm just happier working in a dynamically-typed language. As a side note, years ago, I wanted to write something in Haskell that worked like Clojure's memoize (which is implemented in a half-dozen or so lines of code in Clojure's core), and asked about it on the Haskell mailing list. I was pointed to a PhD dissertation on the topic of how to write memoize in Haskell. All I could think was, "Do I really want to be using a language where memoize is a PhD-level topic?" "
- jacquesm 16y agoIt may that Haskell will never be a mainstream language, but concepts from Haskell will find their way in to other languages, and that's good enough. Not every language has to be a mainstream web-centric enterprise level application oriented (buzzwords enough like that ?) success in order to be successful by some other measure. Haskell has always been research oriented (avoid success at all cost), and if that's the goal then that's fine.
- ekidd 16y agoNot as my _only_ programming language, no. But in general, why not? I value programming languages for what they can teach me. Haskell does make state slightly difficult. (If you need it, just use the IO monad, already. It doesn't bite.) But Haskell makes certain other things easy, things which are extraordinarily difficult in almost any other programming language. For most of my professional life, I've been paid to program in Common Lisp, Scheme, Dylan, etc. Macros, to me, are an ordinary and natural part of programming. But after a while, macros become boring: 99% of them are just a thin syntactic wrapper over something I already know. In Haskell, you don't build higher-order abstractions using macros. Instead, you build your higher-order abstractions using math. And math is almost entirely stateless, lazy and functional. You are forced to think in terms of combinators, abstract algebras, algebraic optimizations, and, yes, category theory. Category theory is the closest link between the lambda calculus and mathematical logic, for example, allowing you to transform some very exotic programming paradigms into actual code. So, yes, Haskell is hard, and it's an ongoing research project. You will spend a lot of time reading papers. (And frankly, you don't want to maintain somebody else's code if you haven't read the same papers.) But some of those papers and theses have blown my mind more in a single weekend than some entire years of hacking in Lisp. Haskell is not the most practical language I know. (State is not the biggest problem for me, but rather the lack of subtyping.) But Haskell is the language I'd be saddest to forget, and the language which has stretched my mind the most.
- jakevoytko 16y agoThere is a vast gulf between learning and using. The original poster obviously enjoys learning new things: he posts on the Clojure mailing list, and hints that he has learned bits and pieces of Haskell. That places him early in the adoption curve. But when you want a language to get things done (one you can "use"), work from a comfort zone - start with a steady base, and branch out to unfamiliar topics. Some people are comfortable finding and reading academic papers as part of their workflow, and others aren't. That's their preference. Other parts of your time should be spent the opposite way: start at the unfamiliar, and make it familiar. But it's not pragmatic to always work like this.
- fogus 16y agoThere is (has always been?) an interesting formula for writing academic C.S. papers: define the most constrained environment imaginable and then do mundane things in it. Haskell is a very beautiful language in a very pure sense and it is the perfect garden for C.S. papers. Likewise, it's an incredibly fertile garden for language features and programming techniques. Is it hard? In some ways perhaps, but to me Javascript's notion of logical truthiness is extremely difficult to hold in my head. It's all relative I suppose.
- WilliamLP 16y ago> Javascript's notion of logical truthiness is extremely difficult to hold in my head. So it isn't intuitive to you that an empty object and array should both evaluate to true, but neither are equal to true, the empty array is equal to false, and the empty object is neither equal to true _or_ false?
- donw 16y agoI've heard of duck-typing, and static-typing, but this is the first time I've heard of Schrödinger-typing...
- gtani 16y agoYeah, Appendix A Crockford's "Good Parts" (could be Appendix B, I can't remember. The book's so small I can't find it.
- sesqu 16y ago> Boolean([]) true > []==false true > [] == ![] true How the hell does that work? Aren't all non-booleans implicitly cast? edit: rephrased
- chc 16y agoIt's because the == operator converts its arguments to be of the same type, and it does so in a rather unintuitive way. This makes it both inefficient and frequently baffling. You pretty much always want === instead, which does not allow comparisons between different types.
- klodolph 16y agoA couple years back I read a blog post with someone complaining about how hard it was to implement the traditional Lisp "map" / "mapcar" function. Specifically, one that took N lists and a single function with N arguments. The author was totally right, too. I could implement this generalized "map" function in Haskell, but it required defining an extra type class which is a little extreme. Of course, the real problem is that people who are new to Haskell expect to sit down and solve problems in the same way they've been solving problems all along. This author was used to the "map" function from Lisp, and wasn't thinking about whether it was necessary, or whether Haskell had a different way of doing things. Here's what the "mapN" function does: > mapN (+1) [1,2] [2,3] > mapN (+) [1,2] [5,8] [6,10] The reason that we don't want to use "mapN" in Haskell is because of the following problem: > mapN (+) [1,2] ??? The result is either "[Int] -> [Int]" or "[Int -> Int]", with no clue as to which is correct. This is why Haskell has "zipWith", "zipWith3", ... Not as pedantry, but because the alternative is ambiguous. (You can use Control.Applicative + ZipList, but that's a tad verbose). My conclusion is that Haskell's differences are what throw people off -- programmers have to relearn how to do things they thought they had figured out for good years ago. (In this case, "everything is curried" means "varargs requires type classes"). It's FINE if you don't want to learn to do things differently and I won't think less of you, I respect your choices for what you do with your precious free time, and I understand that you might want stuff just to work now without learning anything, just please stop stereotyping the Haskellers as a bunch of ivory tower PhDs. I'm not even done with my Bachelor's.
- llimllib 16y agoIf 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.
- 16y ago
- loup-vaillant 16y ago"PhD" may be a scary, Haskell's theses are not. Most academic paper I've read about it are quite readable (I don't have a PhD). The only serious prerequisite for a competent programmer is an introductory course on ML or Haskell.
- skm 16y agoActually, 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.
- skm 16y agoHaskell 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).
- yaroslavvb 16y agoWell, that looks easy...so why are people saying that writing memoization in Haskell is PhD-thesis level task?
- 16y ago
- bpyne 16y agoI'd like to look at a different facet of the issue. My employer mostly implements COTS; our vendors drive our technology choices. The vendors of our two most critical systems decided on JVM based languages - Java and Groovy - so we're moving in their direction. Java is new to most of my department. Currently people use C, SQL, and PL/SQL. I started with Java in 1998: it's not very exciting for me anymore. I'd like to use languages with greater abstraction capabilities. Despite being a really attractive language, Clojure is a tough sell because of its Lisp-like syntax: being a JVM-based language I can probably still get it in house for small apps. Haskell, however, is non-JVM and has unique features by comparison with Java. This combination make it impossible to make an argument for despite all the goodness that it has. Unfortunately for me, it's relegated to the category of a language I'll play with periodically and someday hopefully use in industry.
- cageface 16y agoHave you looked at Scala? It's sort of like a Haskell for the JVM. It's very easy to integrate Scala into a Java project and to gradually learn Scala if you have a Java background.
- bpyne 16y agoThanks for the reply. Yes I have. I didn't want to mention it in my original response to avoid taking the topic away from Haskell and Clojure.
- dons 16y agoLong and detailed discussion, including original participants, on Reddit, http://www.reddit.com/r/programming/comments/crgxs/do_i_really_want_to_be_using_a_language_where/ http://www.reddit.com/r/programming/comments/crgxs/do_i_real... My take away: * The Haskell culture is to take questions seriously * In doing so, the literature will be cited where appropriate * Some people get turned off by research papers In this case, the guy asked a fairly profound question, and received a long, friendly answer, which included references to the literature. Also, it plays on a stereotype, hence all the upvotes.
- swannodette 16y agoRich Hickey about this thread from the ML - Everyone, please refrain from language wars. Haskell is a tremendously ambitious and inspiring language, for which I have the highest respect. There is zero point in bashing it (or its users) in this forum.
- jrockway 16y agoBut Haskell users picked the wrong religion! God won't like us anymore if we don't bash all other languages! (And is it really "bash" when you accuse the users of being too smart?)