Re: [Haskell-cafe] Library function for map+append
Dusan Kolar ko...@fit.vutbr.cz writes: Dlists maybe good it all the app is written using them. Probably not good idea to switch to them in the middle of project... I know it is lazy, but I don't think it is able to eliminate operations, is it? At least intuitively, the map f list takes n*C ticks (C is for application of f and list creation, n is the list length, f is of no importance, it is always the same, but list probably must be created due to ++). Then, (++) take n*K ticks (K for list creation - I want to write out the list at the end, so that it is created). In my case (mapapp), it is n*CK, where CK stands for f and list creation... the CK is very similar to C... Thus, I should save the n*K, or at least its large portion... shouldn't I? If not, how the compiler can eliminate the operations? IMHO, the best way to reason about functional programs is via equational reasoning. So let's consider straightforward definitions for map and (++): map f [] = [] map f (x:xs) = f x : map f xs (++) [] l = l (++) (x:xs) l = x : (xs ++ l) Now let's see what happens with (map f x) ++ y doing case analysis and simplification with the above equations: (map f []) ++ y = [] ++ y = y (map f (x:xs)) ++ y = (f x : map f xs) ++ y = f x : (map f xs ++ y) So: (map f []) ++ y = y (map f (x : xs)) ++ y = f x : (map f xs ++ y) Now consider trivial definition for mapapp: mapapp f x y = (map f x) ++ y. Substituting this backwards into the above equations, we get: mapapp f [] y = y mapapp f (x : xs) y = f x : (mapapp f x xs) which is exactly the definition you've listed. Of course, a Haskell implementation is not *required* to do such transformations, but unless you really observe the difference in performance, it's more or less safe to assume there would be no intermediate list creation/destruction. -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
Clemens Fruhwirth clem...@endorphin.org writes: 2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Can't think of something like that either but at least we can make it shorter and less readable ;) mapapp f xs tail = foldr ((:) . f) tail xs Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Yes, that is less efficient because ++ has to create N new cons cells if list has length N. No, it does not *have to*. Fruhwirth Clemens http://clemens.endorphin.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: DDC compiler and effects; better than Haskell?
John A. De Goes j...@n-brain.net writes: On Aug 15, 2009, at 6:36 AM, Jason Dusek wrote: 2009/08/14 John A. De Goes j...@n-brain.net: Hmmm, my point (perhaps I wasn't clear), is that different effects have different commutability properties. In the case of a file system, you can commute two sequential reads from two different files. I think this is a bad example -- it's not something that's safe in general and discredits your idea. How would the compiler even know that two files are not actually the same file? I don't think the file system is the best example. However, I do think it's a reasonable one. Let's say the type of the function getFilesInDir is annotated in such a way as to tell the effect system that every file in the returned array is unique. Further, let's say the type of the function makeNewTempFile is annotated in such a way as to tell the effect system that the function will succeed in creating a new temp file with a name unique from any other existing file. Sorry, but this example is ridiculuous. While file *names* in this case might be reasonably assumed to be unique, the *files* themselves may not. Any modern filesystem does support file aliasing, and usually several forms thereof. And what does makeNewTempFile function do? Does it create a new file like POSIX mktemp() and return its name, or does it rather behave as POSIX mkstemp()? The first case is a well known security hole, and the second case does not, as it seems to me, fit well into the rest of your reasoning. However, let's consider further file system tree traversal. In some cases you might not care, whether some of the directories you descend into are actually the same directory, so your proposed optimization would be `safe'. However, in other cases sequential traversal would work, while a parallelized version would not, unless special additional measures are taken. E.g. consider a case of a build system. It traverses a source tree, finds sources files and if corresponding object files are non-existent or outdated, does something to regenerate them. Now if you have a directory that's actually a link to another directory, and you do sequential traversal, everything is fine: you descend into the directory the first time, build everything there and when you descend into it the second time, there's just nothing to do. If you do parallel traversal, you may well end up in the situation where two threads check simultaneously for an object file, discover it's outdated and run two build processes simultaneously, with the most likely effect of corrupted object file. Then if you write a recursive function that loops through all files in a directory, and for each file, it parses and compiles the file into a new temp file, then a sufficiently sophisticated compiler should be able to safely transform the recursion into parallel parsing and compilation -- in a way that's provably correct, assuming the original program was correct. The promise of a language with a purely functional part and a powerful effect system for everything else is very great. And very important in the massively concurrent world we are entering. Well, yes -- which sounds like, there are no guarantees in general. Something that works half the time leaves you with two responsibilities -- the old responsibility of the work you did when you didn't have it and the new responsibility of knowing when it applies and when it doesn't. In the other thread, I brought up the example of buffering reads. Library authors make the decision to buffer for one reason: because if some other program is messing with the data, you're screwed no matter what. And yeah, they might be screwing with the data in just the way you need it to be screwed with, (Sebastian), in which case my advice is use C and hope for the best. :-) Regards, John A. De Goes N-Brain, Inc. The Evolution of Collaboration http://www.n-brain.net|877-376-2724 x 101 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: DDC compiler and effects; better than Haskell?
John A. De Goes j...@n-brain.net writes: I forgot about links. In that case, consider: getUniqueFilesInDirRecursive. Attacking irrelevant details in an argument is often called a strawman attack. Such attacks are pointless because they do not address the real substance of the issue. My example is easily modified to avoid the issues you raise. Consider the fact that many file-based operations _can and are parallelized manually by developers_. The challenge for next generation language and effect system designers is to figure out _how_ such operations can be automatically parallelized, given sufficient constraints, high-level constructs, and a powerful effect system. Saying, I don't know exactly how it will look, is quite a bit different from saying It can't be done. I claim the former. Regards, I am sorry, but it's not about details, but about the essence. My point was that there are a lot of subtle issues when we're dealing with (e.g.) a file system in a real-world manner. I have no doubt that it is possible to develop a sound logical system that would cover them and then encode it as a part of the type system of a language. That will probably lead to compile-time detection of a wider class of errors. But the problem is that one (IMHO) cannot deal with these subtleties in a generic manner. That is, there are things that may be done in parallel, and there are things that may not -- and it depends on the actual task you want to perform. So basically instead of manually parallelizing something, you'll (IMHO) end up writing complex type annotations so that a compiler could parallelize it on its own behalf. As somebody who have a certain experience with formal methods, I doubt that the latter will ever be simplier than the former. John A. De Goes N-Brain, Inc. The Evolution of Collaboration http://www.n-brain.net|877-376-2724 x 101 On Aug 16, 2009, at 12:38 AM, Artem V. Andreev wrote: John A. De Goes j...@n-brain.net writes: On Aug 15, 2009, at 6:36 AM, Jason Dusek wrote: 2009/08/14 John A. De Goes j...@n-brain.net: Hmmm, my point (perhaps I wasn't clear), is that different effects have different commutability properties. In the case of a file system, you can commute two sequential reads from two different files. I think this is a bad example -- it's not something that's safe in general and discredits your idea. How would the compiler even know that two files are not actually the same file? I don't think the file system is the best example. However, I do think it's a reasonable one. Let's say the type of the function getFilesInDir is annotated in such a way as to tell the effect system that every file in the returned array is unique. Further, let's say the type of the function makeNewTempFile is annotated in such a way as to tell the effect system that the function will succeed in creating a new temp file with a name unique from any other existing file. Sorry, but this example is ridiculuous. While file *names* in this case might be reasonably assumed to be unique, the *files* themselves may not. Any modern filesystem does support file aliasing, and usually several forms thereof. And what does makeNewTempFile function do? Does it create a new file like POSIX mktemp() and return its name, or does it rather behave as POSIX mkstemp()? The first case is a well known security hole, and the second case does not, as it seems to me, fit well into the rest of your reasoning. However, let's consider further file system tree traversal. In some cases you might not care, whether some of the directories you descend into are actually the same directory, so your proposed optimization would be `safe'. However, in other cases sequential traversal would work, while a parallelized version would not, unless special additional measures are taken. E.g. consider a case of a build system. It traverses a source tree, finds sources files and if corresponding object files are non-existent or outdated, does something to regenerate them. Now if you have a directory that's actually a link to another directory, and you do sequential traversal, everything is fine: you descend into the directory the first time, build everything there and when you descend into it the second time, there's just nothing to do. If you do parallel traversal, you may well end up in the situation where two threads check simultaneously for an object file, discover it's outdated and run two build processes simultaneously, with the most likely effect of corrupted object file. Then if you write a recursive function that loops through all files in a directory, and for each file, it parses and compiles the file into a new temp file, then a sufficiently sophisticated compiler should be able to safely transform the recursion into parallel parsing and compilation
Re: [Haskell-cafe] FW: Haskell
Simon Peyton-Jones [EMAIL PROTECTED] writes: Dear Haskell Cafe members Here's an open-ended question about Haskell vs Scheme. Don't forget to cc Douglas in your replies; he may not be on this list (yet)! Simon -Original Message- From: D. Gregor [mailto:[EMAIL PROTECTED] Sent: 30 March 2008 07:58 To: Simon Peyton-Jones Subject: Haskell Hello, In your most humble opinion, what's the difference between Haskell and Scheme? What does Haskell achieve that Scheme does not? Is the choice less to do with the language, and more to do with the compiler? Haskell is a pure functional programming language; whereas Scheme is a functional language, does the word pure set Haskell that much apart from Scheme? I enjoy Haskell. I enjoy reading your papers on parallelism using Haskell. How can one answer the question--why choose Haskell over Scheme? In my most humble of opinions, the comparison between Haskell and Scheme is just methodologically incorrect. What I mean is that these are actually different kinds of entities, despite they both are called programming languages. In particular, Scheme is nothing but a minimal core of a programming language -- despite it being Turing complete, one can hardly write any serious, real-world program in pure Scheme, as defined by IEEE or whatever. So Scheme is, to my mind, what is it called -- a scheme, which different implementors supply with various handy additions. And we do not have any leading Scheme implementation that would count as a de facto definition of a real Scheme language. Thus we conclude that the term Scheme denotes not a programming language, but rather a family of programming languages. On the other hand, Haskell, as defined by The Report (well, plus FFI addendum) is a true solid real-world language which can actually be used for real-world programming as it is. And we do have a dominating implementation as well, etc etc. Thus: a methodologically correct comparison should be done either between two implementations (Bigloo vs GHC, or MIT Scheme vs Hugs or Stalin vs Jhc or whatever you like) or on the level of PL families and then we'd have Scheme versus Haskell+Helium+Clean+maybe even Miranda+whatever else. In the latter case we'd have two choices again: comparing upper bounds or lower bounds, that is, comparing sets of features provided by any representative of a class or by *all* representatives. Needless to say that the outcome would differ drastically depending on which way we take. -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: The programming language market
[EMAIL PROTECTED] writes: Tim Chevalier/Paul Johnson about cheap computers, expensive programmers This is true only if talking to people in high-income nations. Even in low-income nations, its only false in the short term. If you have skilled programmers with computers and Internet connections then their wages inflate to the world norm. IIRC India is seeing 20%/year wage inflation... It's true that India seems to be going in that direction, but personally I don't feel I have the background or temerity to suggest that it will definitely happen for the rest of the world. The issue is less related to the actual income, but to the global politics, sometimes doctrinal. Not always the invisible hand of market may easily change things, and if a given nation/country has historical strong views on the power of the people, the evolution is different than at your place. India doesn't seem to boast that they are numerous and powerful. Chinese do... We shall see. You may perhaps remember (which you won't, because you are too young) the glorious times when computers became a reality even in Soviet Union. They had at that time plenty of really good mathematicians. But the totalitarian view of the science, plus the nationalistic proudness, made them (the rulers not the scientists...) think and say that with so many good people, there is no need to develop the programming automated tools. They neglected the programming languages. Russia and their satellites became a kind of desert here not only because of economical problems... Not wishing to refute your general point, I can only note that U.S.S.R did have its own school of computer science in general, and of developing programming language implementations in particular. There were Fortran and Algol compilers, there is Refal, after all, which is a purely Soviet invention (and which, for that matter, is still being taught in several Russian universities). So in this particular respect you are definitely wrong. -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: The programming language market (was Re: [Haskell-cafe] Why functional programming matters
[EMAIL PROTECTED] writes: And, PLEASE, Artem V. Andreev, before you say plainly again that I am definitely wrong. I didn't invent what I say, and I hope nobody can accuse me of any inimical thoughts against Russians. I had not the slightest intention to accuse you of anything. Nor did I want to defend how U.S.S.R treated scientists and all that. But I really wonder where you get it from that in U.S.S.R computer science was treated in any way *differently* from any other branches of science? Hardware engineering -- yep, that was a kind of disaster. Which of course cannot but have absolutely negative impact on programming as well as theoretical computer science. But I have never heard that U.S.S.R authorities banned any kind of software development as such, on the ground that there were enough mathematicians around... Do you think that I haven't heard about A.P. Yershov? ACM still cites him, his papers on the system ALPHA (JACM 1966), programming of arith. ops. (CACM 1958), etc. Some other names deserve mentioning as well. But what the system did, cannot be defended. This School of computer science gave some theory to the humanity. But no, or almost no software, sorry. That's of course true. But that does not mean that no software were being developped; that only means the software did not cross the borders... -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
