Probably a trivial thing for people knowing Haskell
I've written just a few programs in Haskell one in a comparison for a task I had "nearly daily". The code analyzes Apache logs and picks some certain stuff from it and after that calculates a bit around with it. Here's the code module Main where import System import System.IO import System.Directory import System.IO.Error import Text.Regex import Control.Monad regexp = mkRegex ("([0-9]+) Windows ex") main = do files <- show_dir "[0-9].*" (sum,count) <- run_on_all_files (0,0) files let dd = (fromIntegral (sum::Integer))/ (fromIntegral (count::Int)) in putStr("Download = " ++ show sum ++ " in " ++ show count ++ " days are " ++ show dd ++ " downloads/day\n") run_on_all_files (a,b) [] = return (a,b) run_on_all_files (a,b) (x:xs) = do (s,c) <- run_on(a,b) x run_on_all_files (s,c) xs run_on (a,b) file_name = do handle <- openFile file_name ReadMode (sum,count) <- for_each_line (a,b) handle hClose handle return ((sum,count)) for_each_line (sum,count) handle = do l <- try (hGetLine handle) case l of Left err | isEOFError err -> return(sum,count) | otherwise -> ioError err Right line -> do let (nsum, ncount) = check_line line sum count for_each_line (nsum,ncount) handle check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count) show_dir regmatch = do files <- getDirectoryContents "." let reg = mkRegex regmatch in return(filter (\file_name -> let fm = matchRegex reg file_name in case fm of Just strs -> True Nothing -> False) files) The point is this code works if there are just say a few files files to check. But it trashes my machine with around 1751 files. It sucks memory as wild and so it does not run as I think it should. I think I've overseen something which is bad written. Would you mind to tell me where I did "extraordinarily" bad. With best regards Friedrich
H mm.. The totals in "sum" and "count" are not computed until printed. This is too lazy. You start with '0' and (+) things to it, but never examine or force the value, so man many (+) thunks are built up in memory. If you use bang patterns then the change can be made here, to !sum !count:
check_line line !sum !count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
This will force evaluation before every check_line call.
Friedrich wrote:
I've written just a few programs in Haskell one in a comparison for a task I had "nearly daily".
The first thing I notice is that this is clearly a direct translation from something like Perl. Thats understandable, but I'd suggest rewriting it with something like this (untested, uncompiled code) -- Concatenate all the files into one big string. File reading is lazy, so this won't take all the memory. getAllFiles :: [String] -> IO String getAllFiles paths = do contents <- mapM getFile paths return $ concat contents Then use "lines" to split the result into individual lines and process them using "filter", "map" and "foldr". Because file reading is lazy, each line is only read when it is to be processed, and then gets reaped by the garbage collector. So it all runs in constant memory. (By the way, putting in the top level type declarations helps a lot when you make a mistake.) One thing you are doing right is keeping a (sum, count) pair. A gotcha with Haskell is to compute an average of a list of numbers like this: mean :: [Double] -> Double mean xs = sum xs / fromIntegral (length xs) The problem with this is that it has to traverse the list twice, which means that the whole list has to be held in memory. So instead you have to write something like: mean xs = let (total, count) = foldr (\x (t, c) -> (t + x, c+1)) (0.0, 0) xs in total / fromIntegral count This is a pain, but it does only traverse the list once. See how you get on. Paul.
The code analyzes Apache logs and picks some certain stuff from it and after that calculates a bit around with it.
Here's the code module Main where import System import System.IO import System.Directory import System.IO.Error import Text.Regex import Control.Monad
regexp = mkRegex ("([0-9]+) Windows ex")
main = do files <- show_dir "[0-9].*" (sum,count) <- run_on_all_files (0,0) files let dd = (fromIntegral (sum::Integer))/ (fromIntegral (count::Int)) in putStr("Download = " ++ show sum ++ " in " ++ show count ++ " days are " ++ show dd ++ " downloads/day\n")
run_on_all_files (a,b) [] = return (a,b) run_on_all_files (a,b) (x:xs) = do (s,c) <- run_on(a,b) x run_on_all_files (s,c) xs
run_on (a,b) file_name = do handle <- openFile file_name ReadMode (sum,count) <- for_each_line (a,b) handle hClose handle return ((sum,count))
for_each_line (sum,count) handle = do l <- try (hGetLine handle) case l of Left err | isEOFError err -> return(sum,count) | otherwise -> ioError err Right line -> do let (nsum, ncount) = check_line line sum count for_each_line (nsum,ncount) handle
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
show_dir regmatch = do files <- getDirectoryContents "." let reg = mkRegex regmatch in return(filter (\file_name -> let fm = matchRegex reg file_name in case fm of Just strs -> True Nothing -> False) files)
The point is this code works if there are just say a few files files to check. But it trashes my machine with around 1751 files.
It sucks memory as wild and so it does not run as I think it should.
I think I've overseen something which is bad written. Would you mind to tell me where I did "extraordinarily" bad.
With best regards Friedrich
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Paul Johnson <paul@cogito.org.uk> writes:
Friedrich wrote:
I've written just a few programs in Haskell one in a comparison for a task I had "nearly daily".
The first thing I notice is that this is clearly a direct translation
From something like Perl. Thats understandable, but I'd suggest rewriting it with something like this (untested, uncompiled code) Quite a good match, however it was Bash and Awk. I implemente the same in C, Ocaml, Ruby, Tcl/Tk, Haskell, Smallltalk, Java, Common Lisp and IIRC C# ;-)
-- Concatenate all the files into one big string. File reading is lazy, so this won't take all the memory. getAllFiles :: [String] -> IO String getAllFiles paths = do contents <- mapM getFile paths return $ concat contents
Then use "lines" to split the result into individual lines and process them using "filter", "map" and "foldr". Because file reading is lazy, each line is only read when it is to be processed, and then gets reaped by the garbage collector. So it all runs in constant memory.
Would you mind to elaborate a bit about it. What's so terrible to open one file after the other, reading it line by line and close the file thereafter. Of course it need memory during that but after the closing of the file the memory could be "freed". So what especially makes so much use of memory?
(By the way, putting in the top level type declarations helps a lot when you make a mistake.)
Well I have my problems with that. Probably it comes from using Languages like Ruby and my special dislike of "typing things" comes especially from Java, C++ (well C is not "innocent" in that regard also. Regards Friedrich -- Q-Software Solutions GmbH; Sitz: Bruchsal; Registergericht: Mannheim Registriernummer: HRB232138; Geschaeftsfuehrer: Friedrich Dominicus
On 2008 Oct 19, at 2:26, Friedrich wrote:
Paul Johnson <paul@cogito.org.uk> writes:
(By the way, putting in the top level type declarations helps a lot when you make a mistake.) Well I have my problems with that. Probably it comes from using Languages like Ruby and my special dislike of "typing things" comes especially from Java, C++ (well C is not "innocent" in that regard also.
Learn to love types: one of the neat things about Haskell is that if you can write down the type of a function then you have usually done 90% of the work of writing the code for it. Another is that in general, if you can't express the type of a function, it means you haven't thought through what you're trying to do. The relationship between types and proofs is especially obvious in Haskell. And proofs aren't merely mathematical entities, they're expressions of what you want to accomplish: if you can type your program, you have a high likelihood not only that it will compile, but that it will do what you intend. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
On 2008 Oct 19, at 2:26, Friedrich wrote:
Paul Johnson <paul@cogito.org.uk> writes:
(By the way, putting in the top level type declarations helps a lot when you make a mistake.) Well I have my problems with that. Probably it comes from using Languages like Ruby and my special dislike of "typing things" comes especially from Java, C++ (well C is not "innocent" in that regard also.
Learn to love types: one of the neat things about Haskell is that if you can write down the type of a function then you have usually done 90% of the work of writing the code for it. Well I disagree. But that's another story.
Another is that in general, if you can't express the type of a function, it means you haven't thought through what you're trying to do.
No that's not true. The use implies that. However I'm not advice resistant and will see if I use types. But IMHO that's should be job of the environment to figure out correctly and most of the time Haskell does "guess" right. And I surely can ask for the types.
The relationship between types and proofs is especially obvious in Haskell. And proofs aren't merely mathematical entities, they're expressions of what you want to accomplish: if you can type your program, you have a high likelihood not only that it will compile, but that it will do what you intend. Well I could argue with the types in C and would not come along very far. In the TCP/IP stuff one can see what you have to do, sooner or later there is a cast... So I "betray" the type system... Or put more friendly and make me a "programming" hero. Hey compiler I know you got it but I'm right ;-)
Unfortunatly this "beeing right" often is wishful thinking... -- Q-Software Solutions GmbH; Sitz: Bruchsal; Registergericht: Mannheim Registriernummer: HRB232138; Geschaeftsfuehrer: Friedrich Dominicus
On 2008 Oct 19, at 11:24, Friedrich wrote:
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
The relationship between types and proofs is especially obvious in Haskell. And proofs aren't merely mathematical entities, they're expressions of what you want to accomplish: if you can type your program, you have a high likelihood not only that it will compile, but that it will do what you intend. Well I could argue with the types in C and would not come along very far. In the TCP/IP stuff one can see what you have to do, sooner or
From a Haskell standpoint, C and Java are virtually untyped. If you want to see types => programs in action, play around with the @free and @djinn commands in lambdabot (a Haskell bot that lives on FreeNode). @free treats a type as a theorem and produces a "proof" of it in Haskell code; @djinn takes a function declaration (type -> type) and generates the "obvious" code suggested by the declaration. (@djinn is sadly somewhat limited; it doesn't handle recursive types, so e.g. lists don't work too well.) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
I think it might be more appropriate to move this discussion to haskell-cafe. On 19 okt 2008, at 17:24, Friedrich wrote:
Learn to love types: one of the neat things about Haskell is that if you can write down the type of a function then you have usually done 90% of the work of writing the code for it. Well I disagree. But that's another story.
Well, it's definitely not true when you're starting out with Haskell. The thing is: once you start to think in types it does work like this. You just think: what do I need as my input and what's my output. That's what you write down as your type and you're almost done! It's very similar to test-driven development; the point with TDD is not so much about making sure your program is correct: the big win (for me) is that it helps you think about the design of your program. The same holds for types.
Another is that in general, if you can't express the type of a function, it means you haven't thought through what you're trying to do.
No that's not true. The use implies that. However I'm not advice resistant and will see if I use types. But IMHO that's should be job of the environment to figure out correctly and most of the time Haskell does "guess" right. And I surely can ask for the types.
I agree. However, sometimes, when things get really complex, you can't figure out a way to write down the code. That's when it can be handy to start out from the types and slowly work towards the definition. At first, you'll think that types are there to make your life harder. After a while, you'll start to love them and to be honest: I feel quite uncomfortable programming in an untyped language these days ;). -chris
Friedrich wrote:
Paul Johnson writes:
-- Concatenate all the files into one big string. File reading is lazy, so this won't take all the memory. getAllFiles :: [String] -> IO String getAllFiles paths = do contents <- mapM getFile paths return $ concat contents
Then use "lines" to split the result into individual lines and process them using "filter", "map" and "foldr". Because file reading is lazy, each line is only read when it is to be processed, and then gets reaped by the garbage collector. So it all runs in constant memory.
Would you mind to elaborate a bit about it. What's so terrible to open one file after the other, reading it line by line and close the file thereafter.
It's not beautiful. Here's a more idiomatic version {-# LANGUAGE BangPatterns #-} module Main where import Control.Monad import System.Directory import Text.Regex import Data.List import Data.Maybe main = do files <- filter_reg "[0-9].*" `liftM` getDirectoryContents "." (sum,count) <- sumcount `liftM` mapM run_file files let dd = fromIntegral sum / fromIntegral count putStrLn $ "Download = " ++ show sum ++ " in " ++ show count ++ " days are " ++ show dd ++ " downloads/day" sumcount :: [(Integer,Int)] -> (Integer,Int) sumcount = foldl' (\(!s,!c) (ds,dc) -> (s+ds,c+dc)) (0,0) run_file name = (sumcount . map check_line . lines) `liftM` readFile' name readFile' name = unsafeInterleaveIO $ openFile name ReadMode >>= hGetContents regexp = mkRegex "([0-9]+) Windows ex" check_line line = case matchRegex regexp line of Just (s:_) -> (read s,1) Nothing -> (0,0) filter_reg pat = let reg = mkRegex pat in filter $ isJust . matchRegex reg It's much shorter and should run in constant memory as well. Regards, apfelmus
the posted codes runs in constant memory, so yes that make it possible that the stuff runs. That's really nice. Howerver the time is drastically bad Even the ruby solution need just check_downloads/check_downloads.rb . 1,25s user 0,06s system 99% cpu 1,322 total Here's the ruby code #!/usr/bin/ruby sum = 0; count = 0; if (ARGV[0]) then Dir.chdir(ARGV[0]) else Dir.chdir("Mail/Administration") end Dir["[0-9]*"].each { |file | fh = File.open(file) while line = fh.gets if line =~ /(\d+) Windows executable/ num = $1.to_i #log.printf("file_name = %s, num = %d\n", file, num); sum += num count += 1 end end fh.close } printf("%d downloads in %d days = %.2f downlaods/day", sum, count, Float(sum)/count) but the haskell solution: ./chk_dwlds 17,71s user 0,11s system 99% cpu 17,836 total Ruby is surely not the speed king of scripting languages, but what Haskell delivers is "way worse".... Howerver at least it doesn not crash any longer.... Regards Friedrich
Friedrich <frido@q-software-solutions.de> writes:
Even the ruby solution need just check_downloads/check_downloads.rb . 1,25s user 0,06s system 99% cpu 1,322 total [...] but the haskell solution: ./chk_dwlds 17,71s user 0,11s system 99% cpu 17,836 total
I'm very surprised to see this. Did you profile it to see what takes so long? -k -- If I haven't seen further, it is by standing in the footprints of giants
Well I never have tried to profile here's my first try. I compiled with ghc --make -O -prof -auto-all chk_dwlds.hs I've run the program with: ./chk_dwlds \+RTS -p \-RTS and got this .prof file Tue Oct 21 15:01 2008 Time and Allocation Profiling Report (Final) chk_dwlds +RTS -p -RTS total time = 19.62 secs (981 ticks @ 20 ms) total alloc = 19,090,366,024 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc run_file Main 67.2 96.5 check_line Main 31.5 2.5 sumcount Main 1.3 1.0 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.0 100.0 100.0 main Main 238 1 0.0 0.0 100.0 100.0 sumcount Main 242 1 0.0 0.0 0.0 0.0 run_file Main 241 1764 67.2 96.5 100.0 100.0 check_line Main 244 1944781 31.5 2.5 31.5 2.5 sumcount Main 243 1764 1.3 1.0 1.3 1.0 main Main 247 0 0.0 0.0 0.0 0.0 filter_reg Main 248 0 0.0 0.0 0.0 0.0 CAF Main 232 10 0.0 0.0 0.0 0.0 check_line Main 246 2 0.0 0.0 0.0 0.0 regexp Main 245 1 0.0 0.0 0.0 0.0 main Main 239 0 0.0 0.0 0.0 0.0 filter_reg Main 240 2 0.0 0.0 0.0 0.0 CAF Text.Read.Lex 209 8 0.0 0.0 0.0 0.0 CAF GHC.Read 204 1 0.0 0.0 0.0 0.0 CAF GHC.Float 203 3 0.0 0.0 0.0 0.0 CAF GHC.Int 198 1 0.0 0.0 0.0 0.0 CAF GHC.Handle 184 7 0.0 0.0 0.0 0.0 CAF System.Posix.Internals 168 7 0.0 0.0 0.0 0.0 CAF System.Directory 125 1 0.0 0.0 0.0 0.0 Regards Friedrich
participants (7)
-
apfelmus -
Brandon S. Allbery KF8NH -
Chris Eidhof -
Chris Kuklewicz -
Friedrich -
Ketil Malde -
Paul Johnson