[Haskell-cafe] OCaml list sees abysmal Language Shootout results
I just saw this on the OCaml list (in a posting by Rafael 'Dido' Sevilla [EMAIL PROTECTED] in the Observations on OCaml vs. Haskell thread). I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? --KW 8-) http://caml.inria.fr/archives/200409/msg00485.html 2. Haskell strings are lists of characters It's annoying that strings aren't normally processed this way in OCaml, and even more annoying that (^) or (::) cannot be used in pattern matching over strings. I like Haskell's approach. The list concatenation operator is the same as the string concatenation operator in Haskell. This is something of an efficiency/elegance tradeoff. Making strings act like lists means potentially boxing *every character in the string*. In other words, it's potentially a very expensive way of doing business. Paul Graham was mulling over this kind of tradeoff in his design of Arc, as I recall. Another language that does this type of thing is Erlang, and both languages seem to be significantly slower than OCaml in string handling, at least as far as this site goes: http://shootout.alioth.debian.org/ For the word count benchmark OCaml scores 0.1850 seconds, while GHC is a dismal last place at 105.2110 seconds! Even the bytecode ocaml is an order of magnitude faster. The word frequency benchmark also shows this kind of poor string handling performance for Haskell, with OCaml scoring 0.5669 seconds, while GHC scores a truly dismal 6.4540, more than an order of magnitude slower, and even the bytecode ocaml is faster at 4.2644 seconds. All in all, it would appear that Haskell's approach has been expensive in terms of performance, if the benchmarks are to be taken at face value. Such are the tradeoffs language designers have to make. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
Keith Wansbrough [EMAIL PROTECTED] writes: I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? With code like this, I'm not surprised! main = do file - getContents putStrLn $ show (length $ lines file) ++ ++ show (length $ words file) ++ ++ show (length file) Space-leak or what? Regards, Malcolm ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
On Tue, Sep 28, 2004 at 10:46:14AM +0100, Keith Wansbrough wrote: I just saw this on the OCaml list (in a posting by Rafael 'Dido' Sevilla [EMAIL PROTECTED] in the Observations on OCaml vs. Haskell thread). I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? No wonder it is so slow, this program looks as a result of some ,,as slow as possible'' contest ;) main = do file - getContents putStrLn $ show (length $ lines file) ++ ++ show (length $ words file) ++ ++ show (length file) Best regards, Tom -- .signature: Too many levels of symbolic links ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
On Tue, Sep 28, 2004 at 12:01:11PM +0200, Tomasz Zielonka wrote: On Tue, Sep 28, 2004 at 10:46:14AM +0100, Keith Wansbrough wrote: I just saw this on the OCaml list (in a posting by Rafael 'Dido' Sevilla [EMAIL PROTECTED] in the Observations on OCaml vs. Haskell thread). I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? No wonder it is so slow, this program looks as a result of some ,,as slow as possible'' contest ;) It took me half an hour to make a version which is 41 times faster on a 5MB file. It should be possible to make it even 2-3 times faster than this. Best regards, Tom -- .signature: Too many levels of symbolic links ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
On Tue, Sep 28, 2004 at 12:49:52PM +0200, Tomasz Zielonka wrote: On Tue, Sep 28, 2004 at 12:01:11PM +0200, Tomasz Zielonka wrote: On Tue, Sep 28, 2004 at 10:46:14AM +0100, Keith Wansbrough wrote: I just saw this on the OCaml list (in a posting by Rafael 'Dido' Sevilla [EMAIL PROTECTED] in the Observations on OCaml vs. Haskell thread). I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? No wonder it is so slow, this program looks as a result of some ,,as slow as possible'' contest ;) It took me half an hour to make a version which is 41 times faster on a 5MB file. It should be possible to make it even 2-3 times faster than this. Changed readArray to unsafeRead, and it is 47 times faster now. I must say I am pleasantly surprised that GHC managed to unbox everything there was to unbox without much annotations. For 5MB file the program allocated only 192KB in the heap. Especially optimisation of higher-level constructs like 'fmap (toEnun . fromEnum) ...' is very nice. Code attached. Feel free to improve it. Best regards, Tom -- .signature: Too many levels of symbolic links import System.IO import Data.Array.IO import Data.Array.Base (unsafeRead) import Data.Word import Char import List wc :: Handle - IO (Int, Int, Int) wc h = do buf - newArray_ (0, bufSize - 1) :: IO (IOUArray Int Word8) let wcLoop :: Char - Int - Int - Int - Int - Int - IO (Int, Int, Int) wcLoop prev nl nw nc i n | prev `seq` nl `seq` nw `seq` nc `seq` i `seq` n `seq` False = undefined | i == n = do n' - hGetArray h buf bufSize if n' == 0 then return (nl, nw, nc) else wcLoop prev nl nw nc 0 n' | otherwise = do c - fmap (toEnum . fromEnum) (unsafeRead buf i) wcLoop c (nl + if c == '\n' then 1 else 0) (nw + if not (isSpace c) isSpace prev then 1 else 0) (nc + 1) (i + 1) n wcLoop ' ' 0 0 0 0 0 where bufSize :: Int bufSize = 8192 main = do (nl, nw, nc) - wc stdin putStrLn $ concat $ intersperse $ map show [nl, nw, nc] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
On Tue, 28 Sep 2004, Tomasz Zielonka wrote: Changed readArray to unsafeRead, and it is 47 times faster now. I must say I am pleasantly surprised that GHC managed to unbox everything there was to unbox without much annotations. For 5MB file the program allocated only 192KB in the heap. Especially optimisation of higher-level constructs like 'fmap (toEnun . fromEnum) ...' is very nice. Now I like to see an implementation which is both elegant and fast ... :-) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Strings - why [Char] is not nice
[ haskell newbie alert ] On 2004-09-20, Henning Thielemann [EMAIL PROTECTED] wrote: On Mon, 20 Sep 2004, Einar Karttunen wrote: Size Handling large amounts of text as haskell strings is currently not possible as the representation (list of chars) is very inefficient. Efficiency is always a reason to mess everything. But the inefficiency Well put. applies to lists of every data type, so why optimizing only Strings, why not optimizing Lists in general, or better all similar data structures, as Python has an interesting approach. Strings are not implemented as lists of characters, but they are an object of a generic type (I forget what it's called; iterable maybe) that can be accessed like a list. (Lists, of course, are also objects of that type.) I assume typeclasses could lead to the same situation in OCaml. It's not a list, but it looks and acts like a list... But anyway, having strings as lists of chars leads to some things that are convenient: * (++) is both a list and a string concatenation operator * Pattern matching works well with strings (that's my #1 gripe about strings in OCaml) * Thanks to the laziness of Haskell lists, things such as lines are possible -- eliminating the hassle of loops/recursion to read file data or the ugliness of reading an entire file at once. These are significant advantages to me. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Strings - why [Char] is not nice
Can this not be handled in a nicer way by the compiler? What if the compiler tried to allocate the lists in chunks? For example when dealing with strings, why cant the compiler allocate the string as a fixed length unit, terminated with a link to the next unit. (IE allow the atoms in the list to be variable size). In this way functions which return blocks of data (for example reading a file in 8k buffers) can be treated just like reading a normal list. This would not only save memory, but would make IO more efficient, whilst retaining a Haskell-like style of coding. Keean. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optmiization of recursion
Hello, As I'm investigating Haskell, it's occured to me that most of the Haskell tutorials out there have omitted something that was quite prominent in the OCaml material I had read: making functions properly tail-recursive. The OCaml compiler was able to optimize tail-recursive functions such that they could be compiled using a loop. This would achieve two main benefits: performance due to not needing to allocate/deallocate stack frames, and the ability to work on very large lists since each recursive call did not consume extra stack space. So I have several questions about Haskell: 1. Do Haskell interpreters/compilers perform similar optimizations? 2. If the answer to 1 is No, then am I correct in saying that my ability to handle very large lists in recursive functions is limited by the maximum stack size on my system? 3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? 4. Is a reference available documenting which Prelude/standard functions are properly tail-recursive (and thus suitable for very large lists) and which are not? (OCaml system docs generally specify when a function is not tail-recursive... for instance, one of foldr/foldl is and the other isn't.) 5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? Thanks! ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optmiization of recursion
John Goerzen [EMAIL PROTECTED] writes: The OCaml compiler was able to optimize tail-recursive functions such that they could be compiled using a loop. This would achieve two main benefits: performance due to not needing to allocate/deallocate stack frames, and the ability to work on very large lists since each recursive call did not consume extra stack space. So I have several questions about Haskell: 1. Do Haskell interpreters/compilers perform similar optimizations? Yes. 3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? Similarly to OCaml. Except that a non-tail-recursive function doesn't necessarily use a large amount of stack, because of laziness. For example map doesn't process the whole list at once; it immediately returns a cons cell which, when its tail is evaluated, causes map to proceed further. 4. Is a reference available documenting which Prelude/standard functions are properly tail-recursive (and thus suitable for very large lists) and which are not? I don't think so. It should be safe to assume that functions have time/space properties like their sources in the Haskell report, but I'm not sure if there are exceptions. But as I said, non-tail recursion is not necessarily a problem. Most functions are suitable for large lists even if they are not tail recursive; when they use O(N) memory, it's on the heap rather than on the stack and it's unavoidable. (OCaml system docs generally specify when a function is not tail-recursive... for instance, one of foldr/foldl is and the other isn't.) This is a tricky issue. In OCaml and similar languages foldl runs in constant stack space, assuming the function given uses a constant stack space, while foldr must traverse the whole list before it begins any work and it uses O(N) stack space. In Haskell foldr is efficient if the given function is lazy in its second argument, or if it enters its second argument in *its* tail position, and O(N) if it does something after evaluation of its second argument. And it's mixed if the function behaves differently on different times, depending on its first argument for example. OTOH foldl is tail-recursive, but the loop only builds a thunk of size O(N), which then uses O(N) of stack if the folded function does some computation after entering its first argument, or better otherwise. *But* if the compiler is able to inline it and statically determine that the folded function is always strict (GHC usually does this but other implementations don't), it can transform the code accordingly such that it doesn't use O(N) stack. Some implementations also provide foldl', which is a strict variant of foldl: it artificially makes the folded function strict (by using seq) and has this seq use inlined, so it will always be as efficient as the folded function permits, but for weird functions it may evaluate something that foldl would not evaluate at all. I wish foldl' was in standard Haskell, because it's usually the same as foldl but doesn't rely on sophisticated compiler optimizations to be efficient. -- __( Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optmiization of recursion
hello, John Goerzen wrote: Hello, As I'm investigating Haskell, it's occured to me that most of the Haskell tutorials out there have omitted something that was quite prominent in the OCaml material I had read: making functions properly tail-recursive. The OCaml compiler was able to optimize tail-recursive functions such that they could be compiled using a loop. This would achieve two main benefits: performance due to not needing to allocate/deallocate stack frames, and the ability to work on very large lists since each recursive call did not consume extra stack space. So I have several questions about Haskell: 1. Do Haskell interpreters/compilers perform similar optimizations? yes they do. most functional language compilers do this sort of thing. 2. If the answer to 1 is No, then am I correct in saying that my ability to handle very large lists in recursive functions is limited by the maximum stack size on my system? if they answer was no, perhaps that would be the case, but with lazyness things get weird. may experience is that it is somehow a lot easier for me to run out of space when writing ML programs (this could be because i probably think in Haskell). the reason is that in ML sometimes things get evaluated, when in haskell you would simply acllocate a closure on the heap. OTOH there are a few classical cases in haskell where you run out of space even if you have a tail recursive function: e.g. sum n [] = n sum n (y:ys) = sum (n + y) ys the reason for this that the n+y expression never gets evaluated until the very end, so you create many suspensions in memory. 3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? yes, in a tail recursive call you can reuse your stack frame, so the call becomes simply a jump (i.e. you get a loop). 4. Is a reference available documenting which Prelude/standard functions are properly tail-recursive (and thus suitable for very large lists) and which are not? (OCaml system docs generally specify when a function is not tail-recursive... for instance, one of foldr/foldl is and the other isn't.) i am not sure if there is such a thing, but one can often guess. for the record, foldl is the tail recursive one (it captures the pattern of traversing a list with an acumulator) while foldr is not. 5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? i'd imagine these would be much the same as in o'caml. a common functional programming pattern when you get tail recursion is to rewrite a function using an accumulator (i.e. a bit of local state). hope this helps -iavpr ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optmiization of recursion
On Tuesday 28 September 2004 01:54 am, Iavor S. Diatchki wrote: OTOH there are a few classical cases in haskell where you run out of space even if you have a tail recursive function: e.g. sum n [] = n sum n (y:ys) = sum (n + y) ys the reason for this that the n+y expression never gets evaluated until the very end, so you create many suspensions in memory. Eep. So that seems like being stuck between a rock and a hard place. (Thanks for mentioning it, btw) If I instead wrote: sum [] = 0 sum (x:xs) = x + sum(xs) then I have the same problem. What is the proper way to solve this little problem then? Would foldl suffer from the same issue? 5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? i'd imagine these would be much the same as in o'caml. a common functional programming pattern when you get tail recursion is to rewrite a function using an accumulator (i.e. a bit of local state). Yup, I have done just that in OCaml. I find it more tasteful to hide the accumulator from the caller. To write the sum, I might do this (forgive me if this is not valid Haskell, I'm still new to this) sum x = let sum2 n [] = n in let sum2 n (y:ys) = sum (n + y) ys in sum2 0 x Or, in OCaml: let sum x = let rec sum2 n y = match y with [] - n | x:xs - sum2 (n + x) xs in sum2 0 x;; ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization of recursion
Hi, I am also looking for this kind of information in general, however I have done some investigations that answer some of you questions. I posted a question on this kind of optimisation recently [1], but it kept unanswered. On Tue, 28 Sep 2004 18:10:11 + (UTC), John Goerzen [EMAIL PROTECTED] wrote: Hello, As I'm investigating Haskell, it's occured to me that most of the Haskell tutorials out there have omitted something that was quite prominent in the OCaml material I had read: making functions properly tail-recursive. The OCaml compiler was able to optimize tail-recursive functions such that they could be compiled using a loop. This would achieve two main benefits: performance due to not needing to allocate/deallocate stack frames, and the ability to work on very large lists since each recursive call did not consume extra stack space. So I have several questions about Haskell: 1. Do Haskell interpreters/compilers perform similar optimizations? ghc does it with one of -O -O1 -O2 switches. hugs doesn't seam to do it since [2] says that foldl (\n _ - n + 1) 0 [1..10] causes a stack overflow. 2. If the answer to 1 is No, then am I correct in saying that my ability to handle very large lists in recursive functions is limited by the maximum stack size on my system? Not really, on the stacksize you give the RTS, however you are limited by the memory anyway. See ghc +RTS --help 3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? As far as I know it is crucial for loop optimisation since without tail recursion there is theoretically no way of transforming the code to an iteration. (without a stack of any kind). 4. Is a reference available documenting which Prelude/standard functions are properly tail-recursive (and thus suitable for very large lists) and which are not? (OCaml system docs generally specify when a function is not tail-recursive... for instance, one of foldr/foldl is and the other isn't.) To my knowledge it is missing. foldl is tail recursive and foldr isn't. 5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? See [3]. [1] http://www.haskell.org//pipermail/haskell/2004-September/014533.html [2] http://cvs.haskell.org/Hugs/pages/bugsandfeatures.htm [3] http://haskell.org/hawiki/TailRecursive?action=highlightvalue=tail+recursion Georg ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optmiization of recursion
John Goerzen [EMAIL PROTECTED] writes: If I instead wrote: sum [] = 0 sum (x:xs) = x + sum(xs) then I have the same problem. What is the proper way to solve this little problem then? sum n [] = n sum n (x:xs) = (sum $! n + x) xs It's unfortunate that it requires $! or seq, but it's the only *reliable* way (not relying on optimizing compilers). That's why I would prefer to have foldl' in the standard. It's too easy to forget about it. It should be encouraged in these accumulator loop patterns. Yup, I have done just that in OCaml. I find it more tasteful to hide the accumulator from the caller. To write the sum, I might do this (forgive me if this is not valid Haskell, I'm still new to this) sum x = let sum2 n [] = n in let sum2 n (y:ys) = sum (n + y) ys in sum2 0 x The first in and second let should be removed. For my language Kogut I invented a loop syntax which would look like this if it was available in Haskell (loop and again are keywords): sum l = loop (l, 0) of (x:xs, n) - again (xs, x + n) ([], n) - n or maybe like this (unfortunately it would be inconsistent with case which uses a single expression only): sum l = loop l 0 of (x:xs) n - again xs (x + n) [] n - n This suffers from the same laziness problem as foldl, $! or seq should be used. -- __( Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Silly I/O question
I'm trying to write a program that will copy an arbitrarily large text file to a destination, and duplicate it 100 times. Thus: ./myprog Input Output would be the same as running: cat Input Output# once cat Input Output # 99 times My first attempt was this: import IO main = disp 100 disp 0 = return () disp n = do c - getContents putStr c hSeek stdin AbsoluteSeek 0 disp (n-1) That failed, though, because getContents closes the file after it's been completely read (ugh -- why?). So then I tried to work on various options around hGetLine and hPutStrLn. But I couldn't figure out a way to make this either properly tail-recursive while handling the exception, or to avoid polling for EOF each time through the function. I also don't want to store the entire file in memory -- the idea is to seek back to the beginning for each iteration. I'm assuming that stdin is a seekable fd. I checked the wiki for a pattern here but didn't see any. Suggestions? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optmiization of recursion
On Tuesday 28 Sep 2004 8:17 pm, John Goerzen wrote: On Tuesday 28 September 2004 01:54 am, Iavor S. Diatchki wrote: OTOH there are a few classical cases in haskell where you run out of space even if you have a tail recursive function: e.g. sum n [] = n sum n (y:ys) = sum (n + y) ys the reason for this that the n+y expression never gets evaluated until the very end, so you create many suspensions in memory. Eep. So that seems like being stuck between a rock and a hard place. (Thanks for mentioning it, btw) You can fix this kind of problem with seq sum n [] = n sum n (y:ys) = let n' = n + y in n' `seq` sum n' ys But AFAIK this should be unnecessary in this case with ghc (and others probably) because sum is strict in it's first argument and the strictness analyser should detect this and avoid pointless laziness. You probably need to compile with -O to get this to happen though. But in cases where the function isn't strict (or you're not sure, or you're not sure about the compilers ability to infer strictness) you can get rid of unwanted laziness for sure using seq. Using $! is an alternative. Regards -- Adrian Hey ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Silly I/O question
John Goerzen writes: That failed, though, because getContents closes the file after it's been completely read (ugh -- why?). getContents reads from standard input: you can't seek on that stream. Just think of cat file | cat. The second invocation reads from a pipe, not from a file on disk. To accomplish your goal, you could read the file _once_ with getContents, and just print it multiple times, like this: printTimes :: Int - String - IO () printTimes n msg = sequence_ (replicate n (putStr msg)) printTimes' :: Int - String - IO () printTimes' n msg = putStr (concat (replicate n msg)) This means, unfortunately, that you'll have to keep the whole file in memory, but if you want to read from standard input, there is no way around that. You could read the contents once, write it to a temporary file, and then copy it multiple times from there. Then you could do it in blocks. But that's probably not what you want to do. But I couldn't figure out a way to make this either properly tail-recursive while handling the exception, or to avoid polling for EOF each time through the function. You might want to write a function that copies the file _once_ and then just call that function several times. Like in the examples above. I don't think you need explicit recursion at all. Hope this is helpful. Peter ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Silly I/O question
On 2004-09-28, Peter Simons [EMAIL PROTECTED] wrote: John Goerzen writes: That failed, though, because getContents closes the file after it's been completely read (ugh -- why?). You could read the contents once, write it to a temporary file, and then copy it multiple times from there. Then you could do it in blocks. But that's probably not what you want to do. That just moves the problem :-) If I assume that stdin is redirected, it is seekable, and I could do the same there. But the block I/O in Haskell makes no sense to me (how do I allocate a Ptr type block thingy)? But I couldn't figure out a way to make this either properly tail-recursive while handling the exception, or to avoid polling for EOF each time through the function. You might want to write a function that copies the file _once_ and then just call that function several times. Like in the examples above. I don't think you need explicit recursion at all. If I load it into memory, yes. Otherwise, it seems not so easy. Hope this is helpful. Yes, thanks for the insight. FWIW, this is working for me: import IO main = disp 100 disp 0 = return () disp n = let copy x = do eof - isEOF if eof then return () else do line - getLine putStrLn line (copy 0) in do copy 0 hSeek stdin AbsoluteSeek 0 disp (n-1) but it seems wasteful to poll isEOF so much. -- John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Silly I/O question
On 2004-09-28 at 21:19- John Goerzen wrote: On 2004-09-28, Peter Simons [EMAIL PROTECTED] wrote: John Goerzen writes: FWIW, this is working for me: import IO main = disp 100 disp 0 = return () disp n = let copy x = do eof - isEOF if eof then return () else do line - getLine putStrLn line (copy 0) in do copy 0 hSeek stdin AbsoluteSeek 0 disp (n-1) but it seems wasteful to poll isEOF so much. Why do you say that? The condition has to be tested for, whether you do it by polling or waiting for an error to be thrown For my 2¢, I think I prefere this sort of thing to look like this: import IO number_of_copies = 100 main = mapM_ contentsToStdOut $ replicate number_of_copies stdin contentsToStdOut hdl = do line_by_line hdl hSeek hdl AbsoluteSeek 0 line_by_line hdl = foldIO (const putStrLn) () hGetLine hdl foldIO process_item initial_state io_operation handle = process initial_state where process state = do eof - hIsEOF handle if eof then return state else do item - io_operation handle new_item - process_item state item process $ new_item and some version of foldIO should probably be in a library somewhere. If you really don't like polling, you can write this: contentsToStdOut hdl = do t - try $ line_by_line hdl hSeek hdl AbsoluteSeek 0 case t of Right () - error this never happens Left e - if isEOFError e then return () else ioError e with line_by_line hdl = do line - hGetLine hdl putStrLn line line_by_line hdl Note that all of these are incorrect because hGetLine doesn't tell you whether there was a newline at the end of file. -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization of recursion
1. Do Haskell interpreters/compilers perform [tail call optimization]? Georg Martius wrote: ghc does it with one of -O -O1 -O2 switches. hugs doesn't seam to do it since [2] says that foldl (\n _ - n + 1) 0 [1..10] causes a stack overflow. All Haskell compilers (including Hugs) perform tail call optimizations. That is, tail calls are compiled as jumps (or equivalent). This is absolutely necessary (and, incidentally, easy) because the only way to write a loop in Haskell is to write a recursive function. If recursive functions consumed more and more stack space with each iteration, it wouldn't be possible to write programs that ran for any length of time or did anything interesting. The problem Georg describes is _not_ due to how tail calls are implemented. It is a property of lazy evaluation that you have to learn about just as someone used to Haskell has to learn not to write the equivalent of [0..] in OCaml. (For those who don't know Haskell, [0..] denotes the infinite list of natural numbers and would quickly exhaust your memory if you tried to use it in a strict language.) -- Alastair Reid ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC and OS X (10.4) [SOLVED]
Thanks to a lot of help from Gregory Wright, it is now possible to
install ghc 6.2.1 on Tiger - it takes quite a bit of fiddling before
it will work, but there is a way. The package available at
Haskell.org will not work, however the darwin ports version will given
that gcc 3.1 is installed on the system - this however is not the
easiest thing in the world to make work. You can however get it
installed by downloading XCode 1.5 from apple developer connection,
going into the packages directory on that disk image, moving the
gcc3.1 package onto your hard disk and editing it's contents slightly.
Do show package contents on the installer, and go into
Contents/Resources, then edit VolumeCheck with your favourite text
editor, edit line 28 to say
if (CheckVersion($SYSTEM_VERS, 10.5, ProductVersion, =)) {
The package should now install happily on tiger, you can then use port
install ghc to install ghc and it's dependancies.
Hope this helps anyone digging in the archives for a solution.
Tom Davie
On Thu, 2 Sep 2004 22:59:59 -0400, Gregory Wright [EMAIL PROTECTED] wrote:
Hi Tom,
You might try building ghc using darwinports
(darwinports.opendarwin.org).
It works under both Jaguar and Panther. I maintain the port, and would
be
interested in your experience on 10.4-beta. (The darwinports version
doesn't
use /Library/Frameworks, instead it keeps everything in a unix-style
lib/
hierarchy.)
The downside is that it takes a few hours to build.
Best Wishes,
Greg Wright
On Sep 2, 2004, at 5:06 PM, Tom Davie wrote:
Hi,
I've been attempting to use GHC on a beta copy of Mac OS X 10.4,
I've been attmepting to use the panther version of the install
package, but have hit a problem with tinkering with it - I get the
following error when I attempt to run ghc:
Verenia:~/Documents/Development/XBridgeAI tatd100$ ghc
dyld: Library not found:
HaskellSupport.framework/Versions/A/HaskellSupport
Referenced from: /usr/local/lib/ghc-6.2.1/ghc-6.2.1
Reason: file not found
Trace/BPT trap
The framework is present in /Library/Frameworks, and
/Library/Frameworks is in dyld's framework search path.
Any Mac/Haskell gurus able to help I would much appreciate it.
Thanks
Tom Davie
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Silly I/O question
On Tuesday 28 September 2004 22:19, John Goerzen wrote: [program that calls isEOF once per line deleted] but it seems wasteful to poll isEOF so much. I think all Haskell implementations have a buffering layer between the Haskell level and the operating system. So, calls to hGetLine, hIsEOF, etc. don't make (expensive) calls to the operating system but, instead, make (cheap) function calls to the I/O library to examine the state of the buffer for that file. In other words, calling isEOF is pretty cheap. That said, if you want to write a cat-like program which is as fast as Unix cat, you should not process data a character at a time or a line at a time but, rather, read fixed size blocks. Ideally the block size would match what the OS can provide efficiently and you would avoid introducing additional layers of buffering. You would also avoid converting from the external representation (a sequence of bytes in memory) to some internal representation (a linked list of characters, an array of unboxed values, or whatever) since you will waste a lot of time in conversion. -- Alastair Reid ps It sounds like you're trying to learn Haskell by writing programs with lots of I/O in them. This isn't really playing to Haskell's strengths and forces you to learn some tricky stuff (and, if chasing performance, learn some murky, non-portable libraries) before you learn what Haskell is really good for. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Silly I/O question
On 2004-09-28, Alastair Reid [EMAIL PROTECTED] wrote: On Tuesday 28 September 2004 22:19, John Goerzen wrote: That said, if you want to write a cat-like program which is as fast as Unix cat, you should not process data a character at a time or a line at a time but, rather, read fixed size blocks. Ideally the block size would match what Right. However, the way to do that is not really apparent from the docs. ps It sounds like you're trying to learn Haskell by writing programs with lots of I/O in them. This isn't really playing to Haskell's strengths and forces you to learn some tricky stuff (and, if chasing performance, learn some murky, non-portable libraries) before you learn what Haskell is really good for. I appreciate the wisdom, Alastair, and understand what you're saying. Partly you are seeing these I/O-related questions because I've figured out other things without help :-) At the same time, I'm not new to functional programming, nor to lazy evaluation (though it has been some time since I've worked with it extensively), and have been spending a lot of time with OCaml recently. It strikes me as very similar to Haskell in several ways. Most of the programs I write are I/O intensive. I/O is the most, well, different thing about Haskell when compared to my prior experiences. I have no problem framing tasks recursively, for instance. One of the things I do when I learn a new language is to try to probe where its weaknesses are. I'm not saying I/O is a weakness in Haskell; just that it was a cause for concern after the shootout results on Alioth. (BTW, I, having known Haskell for a few hours, did manage to speed up one of them by a factor of three while still using only one line of code, so things may not be so bad g) The fact that so many Haskell tutorials save I/O for many chapters down, or even don't bother to cover it at all, is a cause for concern for a hacker-type like me. No, I'm not going to bother with murky low-level hackish libraries for I/O. I just want to understand the strengths and limitations of the existing system. OCaml's system is blazingly fast. But Haskell's is, well, beautiful. I like that. I/O is very critical to a lot of different applications. I think maybe Haskell is shortchanged in that department sometimes, and just suffers from some under-documentation. (Hal Daume III's Yet Another Haskell Tutorial had a great down-to-earth coverage of it that was accessible and easy to follow.) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Silly I/O question
John Goerzen writes: One of the things I do when I learn a new language is to try to probe where its weaknesses are. Please, when meeting new women in your life, don't do so. Otherwise you won't live long enough in order to appreciate your new knowledge... Jerzy Karczmarczuk ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] k-th floorRoot
Hi. floorRootDef, floorRoot :: Integer - Integer - Integer floorRootDef k n | k=1 n=1 = last (takeWhile (\x-x^k=n) [1..]) floorRoot k n | k=1 n=1 = h n where h x = let y=((k-1)*x+n`div`x^(k-1))`div`k in if yx then h y else x (Oddly enough, you get an iteration formula for the _floor_ of the k-th root just by putting _floor_ brackets around every quotient in Newton's iteration formula for the k-th root.) Exercise: Transform floorRootDef into floorRoot by extensional-equality-preserving steps. I don't know how to do this. To conventionally prove the correctness of floorRoot, it suffices to show for all integers k=1, n=1, x=1, y:=[((k-1)*x+[n/x^(k-1)])/k], r:=[n^(1/k)] ([] denoting floor): (1) r=y(so r=x is preserved in the iteration) and (2) x=y -- x=r(so r=x=r when the break condition is met). Using a=[b] -- a=b for all integers a and reals b, (2) is straightforward and (1) is equivalent to k*r-(k-1)*x = n/x^(k-1), which by r^k=n can be sharpened to (3) k*(r-x)+x = r^k/x^(k-1), which is true by induction over k if (3) implies k*(r-x)+x + r-x = r^k/x^(k-1) * r/x, which indeed by (3) can be sharpened to k*(r-x)+r = (k*(r-x)+x)*r/x, equivalently (multiply by x and collect terms) 0 = k*(r-x)^2, done. -- [EMAIL PROTECTED] SDF-EU Public Access UNIX System - http://sdf-eu.org ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Strings - why [Char] is not nice
G'day all. Quoting John Goerzen [EMAIL PROTECTED]: * (++) is both a list and a string concatenation operator This could easily be handle by a typeclass. * Pattern matching works well with strings (that's my #1 gripe about strings in OCaml) * Thanks to the laziness of Haskell lists, things such as lines are possible -- eliminating the hassle of loops/recursion to read file data or the ugliness of reading an entire file at once. These are good arguments for making Strings, however they're implemented, _convertable_ to lazy lists. Much like all of the other containers which Haskell currently implements. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
