[Haskell-cafe] Re: On the verge of ... giving up!
[EMAIL PROTECTED] wrote: However, arguably the biggest imperatives for Haskell 98 was to remove features that would confuse undergraduates. [...] People want to write map instead of fmap. We could have come up with an alternative name for the list-version of map and not showed map to newbies. Couldn't the too much overloading for undergrads issue be solved by providing a LearningPrelude and a RealHackersPrelude? :) The condition is that the former exports the same or less functions with the same or less general types than the latter, so that function names are the same and there's no infantilizing. A stronger condition would be that every valid LearningPrelude program should be a valid RealHackersPrelude program. This is probably preferred, but may be tricky due to overloading ambiguities. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
On 10/15/07, apfelmus [EMAIL PROTECTED] wrote: Of course, the solution is to first drop n elements and then take tails instead of dropping n elements every time. map (drop n) . tails = tails . drop n O(m*n) O(m) Nice identity. I'll remember this one. With this, we can write a function that returns the last n elements of a list in O(m) time and O(n) space as lasts :: Int - [a] - [a] lasts n xs = head $ [x | (x,[]) - zip (tails xs) (tails $ drop n xs)] and use it as a drop-in replacement main n = print . sum . map read . lasts n . lines = getContents But that's a a two-liner now heh =). Thanks for your great postings, apfelmus. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
2007/10/15, Felipe Lessa [EMAIL PROTECTED]: On 10/15/07, apfelmus [EMAIL PROTECTED] wrote: Of course, the solution is to first drop n elements and then take tails instead of dropping n elements every time. map (drop n) . tails = tails . drop n O(m*n) O(m) Nice identity. I'll remember this one. With this, we can write a function that returns the last n elements of a list in O(m) time and O(n) space as lasts :: Int - [a] - [a] lasts n xs = head $ [x | (x,[]) - zip (tails xs) (tails $ drop n xs)] and use it as a drop-in replacement main n = print . sum . map read . lasts n . lines = getContents But that's a a two-liner now heh =). If we're talking about (more than one)-liners, isn't this simpler to read? Or is it just me lasts n xs = let (_,remn) = splitAt n xs in go xs remn go lag [] = lag go [] _ = error shouldn't happen go (l:ls) (x:xs) = go ls xs -- Daniil Elovkov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
Felipe Lessa wrote: apfelmus wrote: Of course, the solution is to first drop n elements and then take tails instead of dropping n elements every time. map (drop n) . tails = tails . drop n O(m*n) O(m) Nice identity. I'll remember this one. Oops, please don't because it's wrong :) Data.List let xs = [1..3] Data.List map (drop 2) . tails $ xs [[3],[],[],[]] Data.List tails . drop 2 $ xs [[3],[]] The first one produces some extra empty lists at the end. In other words, the left hand side and the right hand side have different lengths length . map (drop n) . tails = (+1) . length but length . tails . drop n = (\k - 1 + max 0 (k-n)) . length But the wrong version looks much nicer :) Thanks for your great postings, apfelmus. λ(^_^)λ Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
On Oct 15, 2007, at 7:59 , Felipe Lessa wrote:
On 10/15/07, apfelmus [EMAIL PROTECTED] wrote:
lasts :: Int - [a] - [a]
lasts n xs = head $ [x | (x,[]) - zip (tails xs) (tails $ drop
n xs)]
(...)
main n = print . sum . map read . lasts n . lines = getContents
But that's a a two-liner now heh =).
.oO { if you want Perl, you know where to find it... }
--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED]
system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED]
electrical and computer engineering, carnegie mellon universityKF8NH
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
Vimal wrote: I have been trying my best to read about Haskell from the various tutorials available on the internet and blogs. [...] So, I requested my institute to buy Dr. Graham Hutton's book. I would be getting hold of that quite soon, and am willing to start from the beginning. IMHO, the best way to learn Haskell is to learn it from a textbook. That's basically all there is to it :) I mean, the same goes for Theoretical Computer Science, Mathematics, Physics etc. I think that the key properties of a textbook are 1) printed on paper 2) well-written Of course, if a book doesn't have property 2), use another one. An online book satisfying 2) can be made satisfy 1) by printing it out. In other words, anything goes that fulfills 1) and 2). And since reading two textbooks (in parallel) is even better than reading only one, I'd additionally recommend Bird's Introduction to Functional Programming using Haskell. For other books, see also http://haskell.org/haskellwiki/Books_and_tutorials#Textbooks Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
Brian Hurt wrote: I mean, contemplate this trivial exercise for a moment: write a program that reads from stdin a series of numbers (one number per line), and writes out the sum of the last n numbers. This is a trivial problem, and I have no doubt that someone who knows Haskell better than I will reply to this email with a single line of code that does it. Sorry, I can't resist :) main n = print . sum . map read . take n . reverse . lines = getContents I'm not saying that it's impossible to go directly to Haskell, I'm saying that it's just very very hard. [] I'm going to offer an opinion here that's likely to be controversial (in this forum): people new to functional programming shouldn't learn Haskell first. They should start with either Ocaml or SML first. If it makes it easier to accept this argument, you can consider Ocaml and SML as Haskell with training wheels. I don't agree. At least, it was different for myself. Looking at the line of code above, I can't help it, but I perceive Haskell as being the _simplest_ programming language in the whole world. I had no trouble learning it (step by step from a book), maybe because I've happily thrown away everything I (thought I) knew (about programming). The reward was worth it. Why do people want side effects? Purity is soo much simpler. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
apfelmus wrote: I mean, contemplate this trivial exercise for a moment: write a program that reads from stdin a series of numbers (one number per line), and writes out the sum of the last n numbers. This is a trivial problem, and I have no doubt that someone who knows Haskell better than I will reply to this email with a single line of code that does it. Sorry, I can't resist :) main n = print . sum . map read . take n . reverse . lines = getContents Could someone describe succinctly how to compute the space complexity of this program, if there are m lines of input and m n? Many thanks. --PR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
On 10/14/07, Prabhakar Ragde [EMAIL PROTECTED] wrote: main n = print . sum . map read . take n . reverse . lines = getContents Could someone describe succinctly how to compute the space complexity of this program, if there are m lines of input and m n? Many thanks. --PR 'reverse' needs to go to the end of the list to start outputting, so it has to keep all elements in memory somewhere at least in one moment of time. That means that the program has space complexity of O(m) -- the other functions are all O(1) in terms of line count. You may try this version instead: main n = print . sum . map read . head . dropWhile (not . null . drop n) . tails . lines = getContents where I changed (take n . reverse) to (head . dropWhile (not . null . drop n) . tails). Yes, I cheated, I'm using Data.List =). With this version you keep only n lines in memory at any moment, so it has space complexity of O(n). Please anybody correct me if I'm wrong. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
More neatly, we can fully separate IO from computation: h n = interact $ show . sum . map read . take n . reverse . lines Better yet go a small step further and make *composable* combinations of IO pure computation, as in TV (http://haskell.org/haskellwiki/TV). Cheers, - Conal On 10/14/07, apfelmus [EMAIL PROTECTED] wrote: Brian Hurt wrote: I mean, contemplate this trivial exercise for a moment: write a program that reads from stdin a series of numbers (one number per line), and writes out the sum of the last n numbers. This is a trivial problem, and I have no doubt that someone who knows Haskell better than I will reply to this email with a single line of code that does it. Sorry, I can't resist :) main n = print . sum . map read . take n . reverse . lines = getContents I'm not saying that it's impossible to go directly to Haskell, I'm saying that it's just very very hard. [] I'm going to offer an opinion here that's likely to be controversial (in this forum): people new to functional programming shouldn't learn Haskell first. They should start with either Ocaml or SML first. If it makes it easier to accept this argument, you can consider Ocaml and SML as Haskell with training wheels. I don't agree. At least, it was different for myself. Looking at the line of code above, I can't help it, but I perceive Haskell as being the _simplest_ programming language in the whole world. I had no trouble learning it (step by step from a book), maybe because I've happily thrown away everything I (thought I) knew (about programming). The reward was worth it. Why do people want side effects? Purity is soo much simpler. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: On the verge of ... giving up!
Hi main n = print . sum . map read . take n . reverse . lines = getContents Could someone describe succinctly how to compute the space complexity of this program, if there are m lines of input and m n? Many thanks. --PR The space complexity is the size of the file - i.e. of size m. reverse will buffer up all the lines before it gives any back, which is a well known property of reverse. You could rewrite (take n . reverse) as a function that only requires n lines of buffer. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: That's not my experience. I didn't really understand Kalman filters until I read the Wikipedia page. It's better than most of the tutorials out there. While we're off topic, here's a nice introduction to Kalman filters: http://www.cs.unc.edu/~welch/kalman/maybeck.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Inspired by http://www.xkcd.com/327/, I am considering changing my name to Chung-chieh ');DROP TABLE EMPLOYEES;-- Shan to see if anything breaks ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
