Re: [haskell-cafe] Monad and kinds
On 9/4/08, John Dorsey [EMAIL PROTECTED] wrote: I'm no master either, but I'd argue that if we promise new programmers that they don't need to care about strictness, we thereby ensure that default laziness is treacherous. A year or two ago, ISTR that *most* of the newbie-generated traffic in the cafe was about atrocious performance of naive programs due to strict/lazy concerns. I think it was scaring people away. I think it's debatable what the various causality relationships might be here. Adding strictness can improve asymptotic space performance, as an example. Is there a reason to think this won't always be true? Honest question, since I don't know nearly enough about strictness analysis to guess how good it'll be some day. Adding strictness can also worsen asymptotic space (and time) performance. That's one reason why we use a lazy language at all. Strictness analysis is an approximation to the problem of determining what parts of a program can be evaluated strictly without changing their meaning, because if we had a perfect solution to that problem, we could solve the halting problem. Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt There are no difficult problems, just unfortunate notations. -- Alfonso Gracia-Saz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Tim, A year or two ago, ISTR that *most* of the newbie-generated traffic in the cafe was about atrocious performance of naive programs due to strict/lazy concerns. I think it was scaring people away. I think it's debatable what the various causality relationships might be here. Certainly... Adding strictness can improve asymptotic space performance, as an example. Is there a reason to think this won't always be true? Honest question, since I don't know nearly enough about strictness analysis to guess how good it'll be some day. Adding strictness can also worsen asymptotic space (and time) performance. That's one reason why we use a lazy language at all. Strictness analysis is an approximation to the problem of determining what parts of a program can be evaluated strictly without changing their meaning, because if we had a perfect solution to that problem, we could solve the halting problem. No argument. I was responding to your comment that ... IMO, arguing that programmers should care at all amounts to conceding that default laziness is treacherous. ... which sounds like you're arguing against programmers giving due attention to lazy/strict choices. I was suggesting that there is good reason to think that we should pay attention to it; that it's a necessary part of learning Haskell; and that it will likely remain so. Newbies should be encouraged to think and experiment more with laziness and strictness. Regards, John (pondering an IDE mode for visualizing strictness properties) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Jake Mcarthur wrote: On Sep 4, 2008, at 9:52 PM, Tim Chevalier wrote: I'm no master, but I've never encountered a situation where strictness annotations would be useful as documentation, nor can I imagine one. I'm no master either, but how about these simple examples? data Stream a = Cons !a (Stream a) data Vector3 a = Vector3 !a !a !a The compiler will certainly be able to infer the strictness itself in most uses, so obviously the purpose for these annotations is not for optimization, but I still would find these annotations useful. As far as I am aware this statement is false. I do not believe the compiler infers strictness in common uses of either of these cases, and I have seen space blowups / stack blowups because of it. I use the rule of thumb : simple 'scalar' field components should be strict. Scalar is an ill-defined term but typically means non-recursive data types, like Int and Bool. The most natural exception to this rule is the 'memoizing constructor' idiom. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Jules Bean [EMAIL PROTECTED] writes: On Sep 4, 2008, at 10:19 AM, Tim Chevalier wrote: The master programmer does not add strictness annotations, for she has not yet run the profiler. The compiler will certainly be able to infer the strictness itself As far as I am aware this statement is false. The master programmer does not add strictness annotations, she improves the strictness analyser. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Thu, 2008-09-04 at 08:19 -0700, Tim Chevalier wrote: On 9/3/08, wren ng thornton [EMAIL PROTECTED] wrote: If you want the datatype to be strict in state and rec, then you should add strictness annotations to those fields directly: data Query state rec = Query !state !rec The novice programmer scatters strictness annotations to and fro like dust in the wind. The average programmer understands that annotating a field's strictness injudiciously is like discarding the finger pointing at the moon when you might still need it to scratch yourself. The master programmer does not add strictness annotations, for she has not yet run the profiler. This attitude is wrong. Many potentially significant performance problems can easily be spotted and solved during construction without affecting the readability of the code, problems that would be much harder to diagnose at the end running a profiler. This is especially crucial for library code. The users of the library may be the ones that find the easily resolved space leak your profiling didn't reveal and now they can't do anything about it until a new version is released e.g. Data.Map.insertWith. A performance problem that renders your code unusable is a bug and catching it early or not making it in the first place is much better than catching it late. A (highly related) analogy would be telling Scheme programmers (or Haskell programmers for that matter) not to use to tail recursive code until a profiler tells them to and transforming to a tail recursive style is much more intrusive than adding a strictness annotation. Highly competent Haskell programmers add strictness annotations relatively systematically. The details of mixing eager and lazy code is one of the significant contributions to the pragmatics of programming lazy functional languages have made. At another extreme, things like Chris Okasaki's data structures rely on a specific balance of eagerness and laziness. Also, it is easier (as in not impossible) to turn a strict in the elements data structure into a lazy one than the other way around. Eager by default or lazy by default are both have (actually dual) pitfalls that are best solved by a laziness or strictness annotation respectively. There is no need to walk into those pitfalls with your eyes wide open. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Fri, Sep 5, 2008 at 7:23 PM, Derek Elkins [EMAIL PROTECTED] wrote: This attitude is wrong. Many potentially significant performance problems can easily be spotted and solved during construction without affecting the readability of the code, problems that would be much harder to diagnose at the end running a profiler. This is especially crucial for library code. The users of the library may be the ones that find the easily resolved space leak your profiling didn't reveal and now they can't do anything about it until a new version is released e.g. Data.Map.insertWith. A performance problem that renders your code unusable is a bug and catching it early or not making it in the first place is much better than catching it late. Library writers don't write applications that use their code as part of the testing process? A (highly related) analogy would be telling Scheme programmers (or Haskell programmers for that matter) not to use to tail recursive code until a profiler tells them to and transforming to a tail recursive style is much more intrusive than adding a strictness annotation. Tail recursion isn't always a win in Haskell. I'm not much in touch with the Scheme world, so can't speak to that. Highly competent Haskell programmers add strictness annotations relatively systematically. The details of mixing eager and lazy code is one of the significant contributions to the pragmatics of programming lazy functional languages have made. At another extreme, things like Chris Okasaki's data structures rely on a specific balance of eagerness and laziness. Also, it is easier (as in not impossible) to turn a strict in the elements data structure into a lazy one than the other way around. Eager by default or lazy by default are both have (actually dual) pitfalls that are best solved by a laziness or strictness annotation respectively. There is no need to walk into those pitfalls with your eyes wide open. That may be, but are the holes that one falls into due to unexpected laziness and the ones that one falls into due to unexpected strictness equally numerous? Are they equally deep? Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt Just enough: Obama/Biden '08. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Fri, 2008-09-05 at 20:11 -0700, Tim Chevalier wrote: On Fri, Sep 5, 2008 at 7:23 PM, Derek Elkins [EMAIL PROTECTED] wrote: This attitude is wrong. Many potentially significant performance problems can easily be spotted and solved during construction without affecting the readability of the code, problems that would be much harder to diagnose at the end running a profiler. This is especially crucial for library code. The users of the library may be the ones that find the easily resolved space leak your profiling didn't reveal and now they can't do anything about it until a new version is released e.g. Data.Map.insertWith. A performance problem that renders your code unusable is a bug and catching it early or not making it in the first place is much better than catching it late. Library writers don't write applications that use their code as part of the testing process? They don't use their libraries in every conceivable way. A (highly related) analogy would be telling Scheme programmers (or Haskell programmers for that matter) not to use to tail recursive code until a profiler tells them to and transforming to a tail recursive style is much more intrusive than adding a strictness annotation. Tail recursion isn't always a win in Haskell. I'm very well aware of that. Due to the extremely close relationship with when to tail recursion and when to use laziness, your original statement almost obligates you to also believe that masters don't write tail recursive code until after profiling. I'm not much in touch with the Scheme world, so can't speak to that. Stick in any strict functional language or any other strict language (preferably higher order, but that isn't really important) that also supports tail call optimization. Highly competent Haskell programmers add strictness annotations relatively systematically. The details of mixing eager and lazy code is one of the significant contributions to the pragmatics of programming lazy functional languages have made. At another extreme, things like Chris Okasaki's data structures rely on a specific balance of eagerness and laziness. Also, it is easier (as in not impossible) to turn a strict in the elements data structure into a lazy one than the other way around. Eager by default or lazy by default are both have (actually dual) pitfalls that are best solved by a laziness or strictness annotation respectively. There is no need to walk into those pitfalls with your eyes wide open. That may be, but are the holes that one falls into due to unexpected laziness and the ones that one falls into due to unexpected strictness equally numerous? Are they equally deep? As I said, this particular issue is a duality. For at least a certain class of problems, the ones most relevant here, the holes are equally deep and equally numerous. What is correct in one language is a problem in the other. For examples and more discussion see: http://lambda-the-ultimate.org/node/2273#comment-40156 These last questions, though, are both flawed and irrelevant. They are flawed because the issue isn't which is the default: having both available -at all- makes you vulnerable to the pitfalls of both. Here's a good example: compose = foldr (.) id or should it be compose = foldl' (.) id maybe something else? The fact that Haskell has both strict and non-strict functions makes neither of these implementations correct. It is irrelevant because all that needs to be shown is that there exist -any- problem that can easily be identified and fixed with a strictness annotation. The Haskell implementation of factorial in the above has such a bug, it can be fixed with the addition of two characters, $!, I don't need a profiler to tell me this, and for every standard numeric type there will be no change in semantics (where semantics here does not include performance aspects.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On 9/3/08, wren ng thornton [EMAIL PROTECTED] wrote: If you want the datatype to be strict in state and rec, then you should add strictness annotations to those fields directly: data Query state rec = Query !state !rec The novice programmer scatters strictness annotations to and fro like dust in the wind. The average programmer understands that annotating a field's strictness injudiciously is like discarding the finger pointing at the moon when you might still need it to scratch yourself. The master programmer does not add strictness annotations, for she has not yet run the profiler. Cheers, TIm -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt Science fiction is not predictive; it is descriptive. --Ursula K. Le Guin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 4, 2008, at 10:19 AM, Tim Chevalier wrote: The master programmer does not add strictness annotations, for she has not yet run the profiler. My guess would be that a master usually adds strictness annotations as documentation rather than as optimizations. - Jake McArthur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On 9/4/08, Jake Mcarthur [EMAIL PROTECTED] wrote: My guess would be that a master usually adds strictness annotations as documentation rather than as optimizations. I'm no master, but I've never encountered a situation where strictness annotations would be useful as documentation, nor can I imagine one. That's because optimization *is* the only reason why programmers should care about strictness information. IMO, arguing that programmers should care at all amounts to conceding that default laziness is treacherous. Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt Stupidity combined with arrogance and a huge ego will get you a long way. -- Chris Lowe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 4, 2008, at 9:52 PM, Tim Chevalier wrote: I'm no master, but I've never encountered a situation where strictness annotations would be useful as documentation, nor can I imagine one. I'm no master either, but how about these simple examples? data Stream a = Cons !a (Stream a) data Vector3 a = Vector3 !a !a !a The compiler will certainly be able to infer the strictness itself in most uses, so obviously the purpose for these annotations is not for optimization, but I still would find these annotations useful. This is much like explicitly giving the type for a function. It guides the reader of the program, and just happens to also assist the compiler a little bit. That's because optimization *is* the only reason why programmers should care about strictness information. IMO, arguing that programmers should care at all amounts to conceding that default laziness is treacherous. If optimization is the only reason to worry about strictness, then default laziness really _is_ treacherous. Luckily this is not the case. Laziness is not useful without strictness, otherwise there would never be any evaluation. Understanding how to apply laziness and strictness in different situations is critical to writing efficient but meaningful code in Haskell. To quote a blog article[1] I wrote in June, It is simple and idiomatic to use strictness where your program calls for it. In other words, contrary to many complaints, strictness is not a low-level optimization technique. Strictness is a strategy for algorithms. As is always the case, if you change an algorithm, its time and space requirements will change, but it’s a high-level change. A strictness annotation or data structure redesign is not like dropping to C or assembly. The article explains laziness and strictness as I understand it. I could be wrong, but my understanding seems to have served me well so far. - Jake McArthur___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 4, 2008, at 11:23 PM, Jake Mcarthur wrote: To quote a blog article[1] I wrote in June, And of course I would forget to link the article. My bad. [1] http://geekrant.wordpress.com/2008/06/23/misconceptions/ - Jake McArthur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On 9/4/08, Jake Mcarthur [EMAIL PROTECTED] wrote: I'm no master either, but how about these simple examples? data Stream a = Cons !a (Stream a) data Vector3 a = Vector3 !a !a !a The compiler will certainly be able to infer the strictness itself in most uses, so obviously the purpose for these annotations is not for optimization, but I still would find these annotations useful. This is much like explicitly giving the type for a function. It guides the reader of the program, and just happens to also assist the compiler a little bit. But why not write your types like: data Stream a = Cons a Stream a data Vector3 a = Vector3 a a a in a hypothetical call-by-value language where the annotation denotes a lazily evaluated data structure? Does it matter? If it does, then why? If it doesn't, then what would you conclude about whether a language should encourage laziness or strictness? If optimization is the only reason to worry about strictness, then default laziness really _is_ treacherous. Luckily this is not the case. Laziness is not useful without strictness, otherwise there would never be any evaluation. Understanding how to apply laziness and strictness in different situations is critical to writing efficient but meaningful code in Haskell. True, but both laziness and strictness exist in strict languages, as well. What if, as a thought experiment, you tried substituting laziness for strictness in that paragraph of your essay? Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt The Internet wasn't created for mockery, it was created to help researchers at different universities share data sets. -- Homer Simpson ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 4, 2008, at 11:40 PM, Tim Chevalier wrote: But why not write your types like: data Stream a = Cons a Stream a data Vector3 a = Vector3 a a a in a hypothetical call-by-value language where the annotation denotes a lazily evaluated data structure? Does it matter? If it does, then why? If it doesn't, then what would you conclude about whether a language should encourage laziness or strictness? It doesn't matter, and I don't think it says anything about whether we should encourage lazy-by-default or strict-by-default. Two lazy algorithms tend to compose well and result in a lazy algorithm. A lazy algorithm can compose with a strict algorithm in two different ways. One way is for the lazy algorithm to control the strict algorithm, in which case the strict algorithm is either invoked or not invoked, resulting in a lazy algorithm. The other way is for the strict algorithm to control the lazy algorithm, in which case the strict algorithm requests the data it needs from the lazy algorithm as it needs it, resulting in a strict algorithm. Finally, two strict algorithms may also compose, which results in a strict algorithm. No matter how you slice it, none of the above scenarios are necessarily bad. Each of the four permutations of laziness and strictness for two composed algorithms are necessary for different situations. Laziness and strictness work in tandem with each other to construct whole programs. We Haskellers like laziness by default because we find that it encourages us to consider laziness to solve our problems more often than in call-by-need languages, not because it is somehow superior to strictness. That is the strongest argument I can think of to be made in favor of lazy-by-default. both laziness and strictness exist in strict languages, as well. What if, as a thought experiment, you tried substituting laziness for strictness in that paragraph of your essay? I think the same points would apply, honestly. Do you believe they would change in some way? - Jake McArthur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Tim Chevalier wrote: I'm no master, but I've never encountered a situation where strictness annotations would be useful as documentation, nor can I imagine one. That's because optimization *is* the only reason why programmers should care about strictness information. IMO, arguing that programmers should care at all amounts to conceding that default laziness is treacherous. I'm no master either, but I'd argue that if we promise new programmers that they don't need to care about strictness, we thereby ensure that default laziness is treacherous. A year or two ago, ISTR that *most* of the newbie-generated traffic in the cafe was about atrocious performance of naive programs due to strict/lazy concerns. I think it was scaring people away. Adding strictness can improve asymptotic space performance, as an example. Is there a reason to think this won't always be true? Honest question, since I don't know nearly enough about strictness analysis to guess how good it'll be some day. Regards, John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On 9/4/08, Jake Mcarthur [EMAIL PROTECTED] wrote: Two lazy algorithms tend to compose well and result in a lazy algorithm. A lazy algorithm can compose with a strict algorithm in two different ways. One way is for the lazy algorithm to control the strict algorithm, in which case the strict algorithm is either invoked or not invoked, resulting in a lazy algorithm. The other way is for the strict algorithm to control the lazy algorithm, in which case the strict algorithm requests the data it needs from the lazy algorithm as it needs it, resulting in a strict algorithm. Finally, two strict algorithms may also compose, which results in a strict algorithm. No matter how you slice it, none of the above scenarios are necessarily bad. Each of the four permutations of laziness and strictness for two composed algorithms are necessary for different situations. Laziness and strictness work in tandem with each other to construct whole programs. You say lazy algorithms are good because they compose well. In Haskell, does an algorithm that operates on data structures that have strict components have that property? We Haskellers like laziness by default because we find that it encourages us to consider laziness to solve our problems more often than in call-by-need languages, not because it is somehow superior to strictness. That is the strongest argument I can think of to be made in favor of lazy-by-default. So you don't believe that laziness is superior to strictness, or versa; I don't, either. But you do say it's good to be encouraged to use laziness more often. Why? You mention compositionality above as a possible reason, in reply to which, see above. Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt The future is not google-able. -- William Gibson ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 5, 2008, at 12:45 AM, Tim Chevalier wrote: On 9/4/08, Jake Mcarthur [EMAIL PROTECTED] wrote: Two lazy algorithms tend to compose well and result in a lazy algorithm. A lazy algorithm can compose with a strict algorithm in two different ways. One way is for the lazy algorithm to control the strict algorithm, in which case the strict algorithm is either invoked or not invoked, resulting in a lazy algorithm. The other way is for the strict algorithm to control the lazy algorithm, in which case the strict algorithm requests the data it needs from the lazy algorithm as it needs it, resulting in a strict algorithm. Finally, two strict algorithms may also compose, which results in a strict algorithm. No matter how you slice it, none of the above scenarios are necessarily bad. Each of the four permutations of laziness and strictness for two composed algorithms are necessary for different situations. Laziness and strictness work in tandem with each other to construct whole programs. You say lazy algorithms are good because they compose well. In Haskell, does an algorithm that operates on data structures that have strict components have that property? The algorithm itself can still be lazy in that it might not evaluate the strict data structures at all, and thus can still have that property. However, I did not mean to necessarily emphasize the composability of lazy functions over the composability of strict functions. Both, theoretically, can compose equally well. Composition for laziness and strictness just mean slightly different things as they pertain to control flow and data flow. We Haskellers like laziness by default because we find that it encourages us to consider laziness to solve our problems more often than in call-by-need languages, not because it is somehow superior to strictness. That is the strongest argument I can think of to be made in favor of lazy-by-default. So you don't believe that laziness is superior to strictness, or versa; I don't, either. But you do say it's good to be encouraged to use laziness more often. Why? You mention compositionality above as a possible reason, in reply to which, see above. Mostly because, at least in this part of history, it is easy in many languages to forget about lazy evaluation altogether. I don't think it's a matter of encouraging laziness _over_ strictness, as they are both beneficial, just a matter encouraging the programmer to _think_ in terms of laziness and strictness more often. - Jake McArthur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Ramin wrote: ...no matter how many tutorials I read, I find the only kind of monad I can write is the monad that I copied and pasted from the tutorial... I am writing a mini-database... The query itself is stateful... The query may also make updates to the records. I also thought of trying to re-write my query algorithm to somehow use Control.Monad.State.Strict instead of my own query type, but then I wouldn't get to write my own monad! Just Control.Monad.State should work fine. Daniel Fischer wrote: But this looks very much like an application well suited for the State monad (or a StateT). So why not use that? I agree with Daniel. If you want to learn about the deeper theory of the inner workings of monads, that's great - go ahead, and have fun! But to solve your problem in practice, you don't need that level of knowledge. All you need to know about is get, put, modify, and liftIO. The StateT monad is really simple to use. In general, practical software is higher quality when it uses existing standard libraries. There is no more reason to re-invent the StateT monad than there is to re-invent anything else in the libraries. Among the multitude of monad tutorials out there, I wonder how many of them draw a clear line between what you need to understand to design monads, and what you need to understand just to use them. There's a huge difference in complexity. Like most things, it is best to use monads for a while and get comfortable with them before trying to learn how to design them and build them. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Ramin wrote: Hello, I'm new here, but in the short time I have known Haskell, I can already say it's my favorite computer language. Except for monads, and no matter how many tutorials I read, I find the only kind of monad I can write is the monad that I copied and pasted from the tutorial, i.e. I still don't get it even though I thought I understood the tutorial, and I'm stuck using monads others have already written. My project is this: I am writing a mini-database of sorts. I thought I would make a query a monad, so I could chain multiple queries together using the do notation, and run more complex queries on the list in one shot. The query itself is stateful because it contains information that changes as the database is traversed. The query may also make updates to the records. I got the program to work perfectly using purely functional techniques, but complex queries resulted in that stair-step looking code. So I thought this would be the perfect opportunity to try my hand at monads. The query monad I wrote looks something like this (much simplified): data Query state rec = Query !(state, rec) A minor point but, that strictness annotation doesn't help you very much since tuples are lazy in their arguments. That declaration has the same strictness properties as: data Query state rec = Query state rec The only difference is that your version gives you the free ability to convert from a (Query s r) to a (s,r). The free is in quotes because either there's a cost in indirection to access the state and rec fields, or you've told GHC to optimize the tuple away in which case there's a cost in reconstructing the tuple when demanded.[1] Sometimes there's a reason to use a type like this, but generally it's not what was intended. If you want the datatype to be strict in state and rec, then you should add strictness annotations to those fields directly: data Query state rec = Query !state !rec [1] That is, when a tuple _really_ is demanded. GHC does a good job of replacing tuples with unboxed-tuples when optimizations are turned on. In these cases the code isn't really asking for a tuple so one needn't be reconstructed. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[haskell-cafe] Monad and kinds
Hello, I'm new here, but in the short time I have known Haskell, I can already say it's my favorite computer language. Except for monads, and no matter how many tutorials I read, I find the only kind of monad I can write is the monad that I copied and pasted from the tutorial, i.e. I still don't get it even though I thought I understood the tutorial, and I'm stuck using monads others have already written. My project is this: I am writing a mini-database of sorts. I thought I would make a query a monad, so I could chain multiple queries together using the do notation, and run more complex queries on the list in one shot. The query itself is stateful because it contains information that changes as the database is traversed. The query may also make updates to the records. I got the program to work perfectly using purely functional techniques, but complex queries resulted in that stair-step looking code. So I thought this would be the perfect opportunity to try my hand at monads. The query monad I wrote looks something like this (much simplified): data Query state rec = Query !(state, rec) Where state is the type of state, so a query can contain any information relevant to the search and can be updated as the search progresses. Then, rec is the type of records in the database, which isn't determined inside the database module, so I can't just declare rec to be of any type I choose. But I just cannot write the instance declaration for my Query data type no matter what I try. If I write: instance Monad Query where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC gives an error, Expected kind `* - *', but `Scanlist_ctrl' has kind `* - * - *' . If I try this: instance Monad (Query state) where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC give an error, Occurs check: cannot construct the infinite type: a = (s, a) when trying to generalise the type inferred for `return' . I get the sense I am trying to shove a square peg into a round hole. I was thinking of trying some other things, like implementing the monad in a higher-level module where I knew the type of the records I would be using, but I don't like being told where to implement things. I also thought of trying to re-write my query algorithm to somehow use Control.Monad.State.Strict instead of my own query type, but then I wouldn't get to write my own monad! Though the information given in this e-mail is limited, is there anyone who can clearly see there is something about monads that I just don't get and tell me what it is? Anyone who took the time to read this, I am very appreciative. Ramin Honary ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
On Sep 2, 2008, at 8:34 AM, Ramin wrote: instance Monad Query where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC gives an error, Expected kind `* - *', but `Scanlist_ctrl' has kind `* - * - *' . I believe you understand the problem with the above code, judging from your attempt to fix it below. If I try this: instance Monad (Query state) where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC give an error, Occurs check: cannot construct the infinite type: a = (s, a) when trying to generalise the type inferred for `return' . The problem is your type for the return function. The way you have written it, it would be `return :: (state, rec) - Query state rec`. Perhaps it would be easier to see the problem if we defined `type M = Query MyState`. Then you have `return :: (MyState, rec) - M rec`. Compare this to the type it must be unified with: `return :: a - m a`. The two 'a's don't match! The type you are after is actually `return :: rec - M rec` or `return :: rec - Query state rec`. I hope this helps lead you in the right direction. I'm not giving you the solution because it sounds like you want to solve this for yourself and learn from it. - Jake McArthur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] Monad and kinds
Am Dienstag, 2. September 2008 15:34 schrieb Ramin: Hello, I'm new here, but in the short time I have known Haskell, I can already say it's my favorite computer language. Except for monads, and no matter how many tutorials I read, I find the only kind of monad I can write is the monad that I copied and pasted from the tutorial, i.e. I still don't get it even though I thought I understood the tutorial, and I'm stuck using monads others have already written. Considering some pretty brilliant people have a few years advantage over you, don't expect to find a situation where you need a monad not yet written for a while :) My project is this: I am writing a mini-database of sorts. I thought I would make a query a monad, so I could chain multiple queries together using the do notation, and run more complex queries on the list in one shot. The query itself is stateful because it contains information that changes as the database is traversed. The query may also make updates to the records. I got the program to work perfectly using purely functional techniques, but complex queries resulted in that stair-step looking code. So I thought this would be the perfect opportunity to try my hand at monads. The query monad I wrote looks something like this (much simplified): data Query state rec = Query !(state, rec) Where state is the type of state, so a query can contain any information relevant to the search and can be updated as the search progresses. Then, rec is the type of records in the database, which isn't determined inside the database module, so I can't just declare rec to be of any type I choose. But I just cannot write the instance declaration for my Query data type no matter what I try. If I write: instance Monad Query where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC gives an error, Expected kind `* - *', but `Scanlist_ctrl' has kind `* - * - *' . If I try this: instance Monad (Query state) where return (initState, someRecord) = Query (initState, someRecord) {- code for (=) -} GHC give an error, Occurs check: cannot construct the infinite type: a = (s, a) when trying to generalise the type inferred for `return' . The type of return is (Monad m = a - m a). If m = (Query state), the type of return becomes (rec - Query state rec) and (return a) must be Query (something of type state, a). Now, if you try return (initState, someRecord) = Query (initState, someRecord), the (initState, someRecord) on the left has type a, and the someRecord on the right has the same type. From the left hand side follows a = (state, rec), hence someRecord has type rec. But from the right hand side, someRecord must have type a = (state, rec), so we find rec = (state, rec). That of course is impossible. I get the sense I am trying to shove a square peg into a round hole. I was thinking of trying some other things, like implementing the monad in a higher-level module where I knew the type of the records I would be using, but I don't like being told where to implement things. I also thought of trying to re-write my query algorithm to somehow use Control.Monad.State.Strict instead of my own query type, but then I wouldn't get to write my own monad! But this looks very much like an application well suited for the State monad (or a StateT). So why not use that? Or you could write your own specialised version without looking at the existing code, so you could at least familiarise yourself a little more with monads. Though the information given in this e-mail is limited, is there anyone who can clearly see there is something about monads that I just don't get and tell me what it is? Anyone who took the time to read this, I am very appreciative. Ramin Honary A monad is a type constructor of kind (* - *), that is, it takes one type as argument and returns some other type. Your Query takes two types as argument and makes one new type from that, so Query has kind (* - * - *) and cannot possibly be a monad. What could be a monad is (Query a) which has kind (* - *). However, the only halfway meaningful return you can define then is return someRecord = Query (undefined, someRecord), which doesn't look particularly useful. And (=) then can't make use of the state either, it would have to be one of Query (s,r) = f = f r or Query (s,r) = f = let Query (_,r1) = f r in Query (s,r1) or something completely meaningless. HTH, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe