- Haskell-Cafe - Haskell.org

help with Haskell performance
by Gokul P. Nair 11 Nov '09

11 Nov '09

Hi all, The task I'm trying to accomplish: Given a log file containing several lines of white space delimited entries like this: [Sat Oct 24 08:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist [Sat Oct 24 08:12:37 2009] [error] GET /url2 HTTP/1.0]: Requested URI does not exist [Sat Oct 24 08:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist [Sat Oct 24 12:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist filter lines that match the string " 08:", extract the 6th, 7th and 8th words from that line, group all lines that have the the same resulting string, do a count on them and sort the result in descending order of counts and print it out. So in the example above we'd end up with an output like this: ("GET /url1 HTTP/1.1]:", 2) ("GET /url2 HTTP/1.0]:", 1) Seems pretty straightforward, so I wrote a simple perl script to achieve this task (see the bottom of this email). The input file is 335 MB in size and contains about 2 million log line entires in it. The perl script does a pretty decent job and finishes in about 3 seconds. Now the interesting part. I decided to implememt this in Haskell (being my favorite language and all) and ended up with the following code: --- begin haskell code --- import Text.Regex.Posix ( (=~) ) import qualified Data.List as List import qualified Data.Map as Map import qualified Data.ByteString.Lazy.Char8 as LB main = do contents <- LB.readFile "log_file" putStr . unlines . map ( show . (\(x, y) -> ((LB.unpack x), y)) ) . -- create a Map grouping & counting matching tokens and sort based on the counts List.sortBy (\(_, x) (_, y) -> y `compare` x) . Map.toList . Map.fromListWith (+) . filtertokens . LB.lines $ contents where filtertokens = foldr (\x acc -> if (f x) then ((g x) : acc) else acc) [] -- filter lines starting with " 08:" where f = (=~ " 08:") . LB.unpack -- extract tokens 6, 7 & 8 and create an association list like so ("GET /url2 HTTP/1.0]:", 1) g line = flip (,) 1 . LB.unwords . map (xs !!) $ [6, 7, 8] where xs = LB.words line --- end haskell code --- This haskell implementation takes a whopping 27 seconds to complete! About 9 times slower than the perl version! I'm using ghc 6.10.4, compiling with -O2 and even went to the extent of fusing an adjacent map and filter using a foldr like so: map f (filter g) => foldr ( if g x then f x ... ), fusing adjacents maps etc. Still the same result. I really hope I'm missing some obvious optimization that's making it so slow compared to the perl version, hence this email soliciting feedback. Thanks in advance. P.S. For reference, here's my corresponding perl implementation: --- start perl code --- #!/usr/bin/perl use strict; use warnings FATAL => 'all'; my %urls; open(FILE, '<', $ARGV[0]); while(<FILE>) { if (/ 08:/) { my @words = split; my $key = join(" ", ($words[6], $words[7], $words[8])); if (exists $urls{$key}) { $urls{$key}++ } else { $urls{$key} = 1 } } } for (sort { $urls{$b} <=> $urls{$a} } keys %urls) { print "($_, $urls{$_})\n" } --- end perl code ---

6 7

Re: [Haskell-cafe] Help to solve simple problem !
by Eduard Sergeev 11 Nov '09

11 Nov '09

Aneto wrote: > > compress :: Eq a => [a] -> [(a, Int)] > If you have string "AAABCCC" it transforms it to : {A, 3} {B,1} {C,3} > Basically you need to "group" equal elements of the list first and then transform every group (which is a list of equal elements) to the tuple of (first_element , the_ length_of_the_group). All necessary functions can be found in Prelude and Data.List: import Data.List compress :: Eq a => [a] -> [(a, Int)] compress xs = map (\g -> (head g, length g)) (group xs) PS You can express it somehow nicer with arrows thought: import Data.List import Control.Arrow compress :: Eq a => [a] -> [(a, Int)] compress = map (head &&& length) <<< group -- View this message in context: http://old.nabble.com/Help-to-solve-simple-problem-%21-tp26249028p26294356.… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

1 0

Cabal HackORama -- how to handle par and pseq on stable platforms
by John D. Ramsdell 10 Nov '09

10 Nov '09

I am writing a Cabal file for an application that uses par and pseq. I want to support both modern distributions of GHC and the version that comes with Ubuntu Hardy Heron, a Long Term Support version of Ubuntu that will be retired in April 2011. It provides GHC 6.8.2 with Cabal 1.2.3.0 and no parallel package. You might be interested in my solution to supporting both releases. I did the obvious in my Cabal file. A defined a flag as follows: -- Disable with -f-par option during configuration. Flag Par Description: Enable use of the parallel construct par Default: True The description of the executable includes: if flag(par) Cpp-Options: -DHAVE_PAR GHC-Options: -threaded Build-Depends: parallel The C preprocessor is used to toggle between a parallel version of map and the usual one. #if defined HAVE_PAR parMap :: (a -> b) -> [a] -> [b] parMap _ [] = [] parMap f (x:xs) = par y (pseq ys (y:ys)) where y = f x ys = parMap f xs #else parMap :: (a -> b) -> [a] -> [b] parMap = map #endif Here is what makes this cabal file sweet. Cabal 1,2,3.0 supports flags, but ignores the Default specification. It assumes the default value of every flag is False. Thus, for both modern versions of GHC and the one on Hardy Heron, no user supplied flags are required during configuration. John

1 0

Re: [Haskell-cafe] Help to solve simple problem !
by Ezra Lalonde 10 Nov '09

10 Nov '09

The following program should work: =======compress.hs============= toList :: (Eq a) => [a] -> [[a]] toList [] = [] toList x = start : toList end where (start, end) = span (==(head x)) x toTuple :: [a] -> (a, Int) toTuple x = (head x, length x) compress :: Eq a => [a] -> [(a, Int)] compress x = map toTuple $ toList x ============================= The important thing to understand here, is the "span" function from the Prelude, and apply it recursively. *Main> span (=='A') "AAABCC" ("AAA","BCC") *Main> span (=='h') "hhhaskell" ("hhh","askell") I've used a function "toList" to separate each part of the string into a separate element of a list: *Main> toList "AAABCC" ["AAA","B","CC"] *Main> toList "EEEZZZRRAAAA!!" ["EEE","ZZZ","RR","AAAA","!!"] >From there, "toTuple" takes the first letter of the string, and puts it with its length in a tuple: *Main> toTuple "EEE" ('E',3) *Main> toTuple "EEEEE" ('E',5) Because of how it's defined, we also get the following: *Main> toTuple "Ezra" ('E',4) But that won't matter if we only use it after "toList", as in "compress". Also, I've used your type signature for my solution, not your example output; if you want it to be displayed like that, you'll have to write your own function for printing. This solution is probably not optimal, but it's a start. Hope that helps, Ezra Aneto wrote: > > Hi ! I am beginner in Haskell and have problems with this problem: > compress :: Eq a => [a] -> [(a, Int)] > If you have string "AAABCCC" it transforms it to : {A, 3} {B,1} {C,3} > > Could you help me with it ? > Thank you in advance ! > -- View this message in context: http://old.nabble.com/Help-to-solve-simple-problem-%21-tp26249028p26292205.… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

1 0

ICFP 2010: Call for papers
by Wouter Swierstra 10 Nov '09

10 Nov '09

===================================================================== Call for Papers ICFP 2010: International Conference on Functional Programming Baltimore, Maryland, 27 -- 29 September 2010 http://www.icfpconference.org/icfp2010 ===================================================================== Important Dates (at 14:00 UTC) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Submission: 2 April 2010 Author response: 24 -- 25 May 2010 Notification: 7 June 2010 Final papers due: 12 July 2010 Scope ~~~~~ ICFP 2010 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects or concurrency. Particular topics of interest include * Language Design: type systems; concurrency and distribution; modules; components and composition; metaprogramming; relations to object-oriented or logic programming; interoperability * Implementation: abstract machines; compilation; compile-time and run-time optimization; memory management; multi-threading; exploiting parallel hardware; interfaces to foreign functions, services, components or low-level machine resources * Software-Development Techniques: algorithms and data structures; design patterns; specification; verification; validation; proof assistants; debugging; testing; tracing; profiling * Foundations: formal semantics; lambda calculus; rewriting; type theory; monads; continuations; control; state; effects * Transformation and Analysis: abstract interpretation; partial evaluation; program transformation; program calculation; program proof * Applications and Domain-Specific Languages: symbolic computing; formal-methods tools; artificial intelligence; systems programming; distributed-systems and web programming; hardware design; databases; XML processing; scientific and numerical computing; graphical user interfaces; multimedia programming; scripting; system administration; security; education * Functional Pearls: elegant, instructive, and fun essays on functional programming The conference also solicits Experience Reports, which are short papers that provide evidence that functional programming really works or describe obstacles that have kept it from working in a particular application. Abbreviated instructions for authors ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ By 2 April 2010, 14:00 UTC, submit an abstract of at most 300 words and a full paper of at most 12 pages (6 pages for an Experience Report), including bibliography and figures. The deadline will be strictly enforced and papers exceeding the page limits will be summarily rejected. Authors have the option to attach supplementary material to a submission, on the understanding that reviewers may choose not to look at it. A submission will be evaluated according to its relevance, correctness, significance, originality, and clarity. It should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, explaining why it is significant, and comparing it with previous work. The technical content should be accessible to a broad audience. Functional Pearls and Experience Reports are separate categories of papers that need not report original research results and must be marked as such at the time of submission. Detailed guidelines on both categories are on the conference web site. Each submission must adhere to SIGPLAN's republication policy, as explained on the web at http://www.acm.org/sigplan/republicationpolicy.htm. Proceedings will be published by ACM Press. Authors of accepted submissions are expected to transfer the copyright to the ACM. Presentations will be videotaped and released online if the presenter consents by signing an additional permission form at the time of the presentation. Formatting: Submissions must be in PDF format printable in black and white on US Letter sized paper and interpretable by Ghostscript. If this requirement is a hardship, make contact with the program chair at least one week before the deadline. Papers must adhere to the standard ACM conference format: two columns, nine-point font on a ten-point baseline, with columns 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). A suitable document template for LATEX is available from SIGPLAN at http://www.acm.org/sigs/sigplan/authorInformation.htm. Submission: Submissions will be accepted electronically at a URL to be named later. Improved versions of a paper may be submitted at any point before the submission deadline using the same web interface. Author response: Authors will have a 48-hour period, starting at 14:00 UTC on 24 May 2010, to read and respond to reviews. Special Journal Issue: There will be a special issue of the Journal of Functional Programming with papers from ICFP 2010. The program committee will invite the authors of select accepted papers to submit a journal version to this issue. Organization ~~~~~~~~~~~~ Conference Chair Paul Hudak, Yale University Program Chair Stephanie Weirich, University of Pennsylvania Program Committee: Umut Acar, Max Planck Institute for Software Systems Zena Ariola, University of Oregon James Cheney, University of Edinburgh Peter Dybjer, Chalmers University of Technology Robert Bruce Findler, Northwestern University Andy Gill, Kansas University Fritz Henglein, University of Copenhagen Michael Hicks, University of Maryland, College Park Patricia Johann, University of Strathclyde Andres Löh, Utrecht University Simon L. Peyton Jones, Microsoft Research Didier Rémy, INRIA Paris-Rocquencourt John Reppy, University of Chicago Manuel Serrano, INRIA Sophia-Antipolis Matthieu Sozeau, Harvard University

1 0

Calling all Haskellers in Huntsville, Alabama, or surrounding areas!
by Jake McArthur 10 Nov '09

10 Nov '09

Shae Errisson, myself, Greg Bacon, and some other locals who I think might not have as big a presence online are starting a user's group in Huntsville, AL. Please join the Google group / mailing list [1] if you are interested! [1] http://groups.google.com/group/alabamahaskell - Jake McArthur

1 0

pattern match failure as control structure
by Dan Mead 10 Nov '09

10 Nov '09

hey all, is there something special about pattern match exceptions? i'm attempting to catch pattern match failures to use as control for a production system. so i want to be able to do something like catch (head []) (\e -> print "that theres pattern fail!" ) any suggestions?

3 4

Sending patches to ghc related repositories
by Maurício CA 10 Nov '09

10 Nov '09

Hi, all, I just tried to send a patch to a ghc tool. I see in hackage that the maintainer e-mail is 'cvs-fptools(a)haskell.org' (package is hsc2hs). I tried sending darcs patch to this e-mail, but it's refused as it's not on that server allowed e-mails table. The patch isn't really important, just a documentation typo, but I'm curious about what is the proper way to do it. Thanks, Maurício

1 0

is proof by testing possible?
by muad 10 Nov '09

10 Nov '09

Is it possible to prove correctness of a functions by testing it? I think the tests would have to be constructed by inspecting the shape of the function definition. -- View this message in context: http://www.nabble.com/is-proof-by-testing-possible--tp25860155p25860155.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

15 31

filter using foldr point-free?
by damodar kulkarni 10 Nov '09

10 Nov '09

Hi, We can define filter using foldr as under: filter1 p = foldr (\x xs -> (if (p x) then (x:xs) else xs)) [] Can we define filter using foldr but in pointfree style? Thanks -DM

2 1