- Haskell-Cafe - Haskell.org

question about lazy io
by David Roundy 12 Oct '02

12 Oct '02

Hello. I have a problem I ran into when I tried writing a function to use lazy IO . Specifically, I would like to be able to compare two directory trees, and I thought the best way to do this would be to compartmentalize things by writing an IO function to read in a whole directory tree (including the contents of its files) in a lazy manner, and then the code to manipulate this tree could be purely functional and non-monadic. The problem is that while reading a file in with readFile (or openFile followed by hGetContents) is lazy regarding the reading of the actual file data, it leaves the file handle open, and (at least on ghc under linux) quickly exhausts the available file handles. I guess this makes sense, since if the file wasn't opened until it was actually used, a file open error couldn't flag an exception at the appropriate time... I think this is a related question to the thread on config files and pure file reading. Certainly if there was a pure functional file read (i.e. readFileOnce), that would solve my problem. I hate to have to write monadic IO code right into the core of my code. The Haskell 98 Library Report describes the state of a file handle after hGetContents as 'semi-closed', meaning it will close as soon as it is finished with the current read. Is there any way to get the file handle into a 'semi-opened' state, in which it will be opened as soon as it starts getting read? That's what I'd really like. fwiw, here's the code I'd like to use to slurp up a directory and its contents: >slurp dirname = do > isdir <- doesDirectoryExist dirname > if isdir > then do > former_dir <- getCurrentDirectory > fnames <- getDirectoryContents dirname > setCurrentDirectory dirname > sl <- slurp_list $ skip_hidden fnames > setCurrentDirectory former_dir > return $ SlurpDir dirname sl > else do > isfile <- doesFileExist dirname > if isfile > then do > contents <- readFile dirname > return $ SlurpFile dirname (lines contents) > else return $ SlurpFile "Oops" [] > >slurp_list :: [FilePath] -> IO [Slurpy] >slurp_list [] = return [] >slurp_list (f:fs) = do > s <- slurp f > ss <- slurp_list fs > return (s:ss) > >skip_hidden :: [FilePath] -> [FilePath] >skip_hidden [] = [] >skip_hidden (('.':_):fps) = skip_hidden fps >skip_hidden (fp:fps) = fp : skip_hidden fps To restate my question (which I may have forgotten to ask...), is there a good way to do this? The only thing that comes to mind is to use unsafeIO, which sounds scary. (Mostly because I don't think I would really understand the consequences.) -- David Roundy http://civet.berkeley.edu/droundy/

2 1

Dealing with configuration data
by Liyang Hu 11 Oct '02

11 Oct '02

Evening, I'm trying to write a utility that reads in some user preferences from a pre-determined file, does some work, and exits. Sounds simple enough. The problem I'm having is with the preferences: How do I make it available throughout the entire program? (FWIW, most of the work is effectively done inside the IO monad.) I could explicitly pass the record around everywhere, but that seems a trifle inelegant. My current solution is to use a global ('scuse my terminology, I'm not sure that's the right word to use here) variable of type IORef Config obtained through unsafePerformIO. It works, but strikes me as a rather barbaric solution to a seemingly tame enough problem... Intuition tells me I should be able to `embed', if you will, the config record somehow within or alongside the IO state, and retrieve it at will. (Is this what MonadState is for?) However it also tells me that this will /probably/ involve lots of needless lifting and rewriting of the existing code, which makes it even less enticing than passing everything around explicitly. Any opinions or suggestions? Cheers, /Liyang -- .--{ Liyang HU }--{ http://nerv.cx/ }--{ Caius@Cam }--{ ICQ: 39391385 }--. | :: zettai unmei mokusiroku :::: absolute destined apocalypse ::::::::: |

8 17

Re: infinite (fractional) precision
by Ashley Yakeley 11 Oct '02

11 Oct '02

At 2002-10-10 01:29, Ketil Z. Malde wrote: >I realize it's probably far from trivial, e.g. comparing two equal >numbers could easily not terminate, and memory exhaustion would >probably arise in many other cases. I considered doing something very like this for real (computable) numbers, but because I couldn't properly make the type an instance of Eq, I left it. Actually it was worse than that. Suppose I'm adding two numbers, both of which are actually 1, but I don't know that: 1.000000000.... + 0.999999999.... The trouble is, as far as I know with a finite number of digits, the answer might be 1.9999999999937425 or it might be 2.0000000000013565 ...so I can't actually generate any digits at all. So I can't even make the type an instance of my Additive class. Not very useful... -- Ashley Yakeley, Seattle WA

6 6

infinite (fractional) precision
by ketil＠ii.uib.no 10 Oct '02

10 Oct '02

Hi I was just browsing around on comp.arch a bit, and there was this discussion about various ways to represent non-integer numeric values. It seems one could easily (I'll get back to that in a moment) calculate the fractional part of numbers lazily, generating the needed precision, and nothing more. Does any such implementation exist in Haskell? I realize it's probably far from trivial, e.g. comparing two equal numbers could easily not terminate, and memory exhaustion would probably arise in many other cases. So, if such implementations exist, how does one deal with these issues? Is it indeed possible to make this useful in practice? (And if it hasn't been implemented, would anybody be interested if I gave it a try?) -kzm -- If I haven't seen further, it is by standing in the footprints of giants

3 2

need help optimizing a function
by David Roundy 10 Oct '02

10 Oct '02

Hello. If you followed my previous post (which was about a bug in my lcs function), this is still the same code (only now bug-free, it seems). It turns out that my lcs diff function is MUCH slower than GNU diff on some test files (much worse than 1000 time slower!).The test case where its speed was close was IO bound on the output to an xterm (silly me). I've profiled my lcs code, and it is spending about 95% of its time in the "hunt_one_char" function. It also claims to spend 0.0% of its time in my_bs, which does a binary search on the array, and is the only other function that gets called by hunt_one_char (not counting itself). I've told the compiler (ghc) to inline hunt_one_char and my_bs to no avail. I guess maybe it can't or won't inline a recursive function, or maybe that just doesn't gain me anything. My only guess is that for some reason it is making an entirely new copy of the array each time it recurses, but that doesn't make any sense, since the array is getting threaded through, so it should be able to just modify the array in place. But then, I'm not entirely clear as to what the compiler can and cannot do as it optimizes. >>data Threshold a = Thresh Int! [a] >> deriving (Show) >> >>hunt_one_char :: String -> [Int] -> Array Int (Threshold String) -> >> Array Int (Threshold String) >>hunt_one_char c [] th = th >>hunt_one_char c (j:js) th = >> case my_bs (Thresh j [c]) th of >> Nothing -> hunt_one_char c js th >> Just k -> >> case th!(k-1) of >> Thresh _ rest -> >> hunt_one_char c js th//[(k,Thresh j (c:rest))] For what it's worth, the calling function is: >>hunt_internal :: [String] -> [[Int]] -> >> Array Int (Threshold String) -> >> Array Int (Threshold String) >>hunt_internal [] _ th = th >>hunt_internal _ [] th = th >>hunt_internal (c:cs) (m:ms) th = >> hunt_internal cs ms $ hunt_one_char c m th Each string in this list of strings is a line from one of the files (and the [[Int]] is a list of line numbers in the other file that that line matches). The array 'th' has size (1,n) where n is the number of lines in the file. My simplest test case consists of a 20k line file, each line of which is unique and a second file which is simply a permutation of the first (moving the first line to the last), so hunt_one_char should be called exactly once for each line, and it is always called with its second argument having exactly one element. In this test case, according to the ghc profiler, 89.7% of the time is spent in hunt_one_char: individual inherited COST CENTRE MODULE entries %time %alloc %time %alloc hunt_internal Main 20001 0.2 0.0 91.4 95.3 hunt_one_char Main 40000 89.7 95.0 91.1 95.3 my_bs Main 20000 0.2 0.0 1.4 0.3 my_helper_bs Main 307231 1.2 0.3 1.2 0.3 This has me at a loss. It seems like such a simple function... of course, it is called 20k times, which could certainly add up, but while each call of my_bs should take O(log 20k) time, each call of hunt_one_char (apart from its one call to my_bs) should only take O(1), so most of the time should be spent in my_bs unless something is terribly wrong (which must be the case here). If it would help, I'd be happy to send a listing of the complete code, but it's 6.5k so I figured it'd be better not to send it, since it seems unlikely that anyone would want to run it anyways. -- David Roundy http://civet.berkeley.edu/droundy/

5 5

Data structure definitions
by Mark T.B. Carroll 09 Oct '02

09 Oct '02

I have a program that basically has, data Expression = Value Value | EVariable Variable | other stuff ... data Value = VNumber Number | other stuff ... data Variable = Variable { variable_name :: String, variable_time :: Expression } data Number = Number { value :: Double, dimension :: Dimension } newtype VariableCount = VariableCount (Variable, Number) The VNumber and EVariable constructors are ugly, though, so I was wondering if I should be using typeclasses - e.g., class Expression a class Expression a => Value a instance Value Number instance Expression Variable ... but I don't see how to define Variable in such a scheme. Maybe I shouldn't be using typeclasses? (Obviously, I actually have lots more type constructors in Expression and Value - dyadic expressions, booleans, etc. - the above with just numbers and variables is somewhat truncated, but should suffice.) -- Mark

3 3

Expander2
by Prof. Dr. Peter Padawitz 08 Oct '02

08 Oct '02

Expander2: A Formal Methods Presenter and Animator ================================================== Expander2 has been designed as a multi-purpose workbench for interactive logical inference, constraint solving, data flow analysis and other procedures building up proofs or computation sequences. Moreover, several interpreters translate expressions into tailor-made two-dimensional representations that range from trees and term graphs to tables, fractals or other turtle-system-generated pictures. Expander2 has been implemented in O'Haskell}, an extension of Haskell with object-oriented features for reactive programming and a typed interface to Tcl/Tk for developing GUIs. Besides a comfortable GUI the design goals of Expander2 were to integrate testing, proving and visualizing deductive methods, to admit several degrees of interaction and to keep the system open for extensions or adaptations of individual components to changing demands. Proofs and computations performed with Expander2 follow the rules and the semantics of swinging types (ls5-www.cs.uni-dortmund.de/~peter/Swinging.html). Swinging types combine constructor-based visible types with state-based hidden types and have unique (Herbrand) models, which interpret relations as the least or greatest solutions of their axioms. All features of the system and their use are described in the manual ls5-www.cs.uni-dortmund.de/~peter/Expander2/Expander2.html (sorry, this is still a big file, it will be splitted soon; PostScript version: ../Expander2/Expander2.ps.gz). The paper ../Expander2/Chiemsee.ps.gz concentrates on the prover features. Download everything with ../Expander2.tar.gz. Please email comments, bugs, etc. to peter.padawitz(a)udo.edu. Peter

1 0

Re: need help optimizing a function
by Zdenek Dvorak 08 Oct '02

08 Oct '02

Hello, > > p.s., I sense your next question is going to be something like "why > > can't the compiler detect that the array can be updated in place > > instead of copied" and the answer, from what i can tell, is simply > > that it doesn't try. > >And one might argue that it should not try [snip] and the other answer is that the result would not be worth the effort usually. The idea seems nice, but the laziness is where I see the problem; see the following code: do_something::Array Int Int->(Array Int Int, Result) do_something a = (a'',res) where a' = a // [(summon_index, summon_int)] w = a' ! 4 res = do_some_work w a'' = a' // [(summon_other_index, summon_other_int)] Seems like nice candidate for update-in-place? But the problem is, that in general you cannot say when w will be evaluated -- so you simply cannot destroy a' before then. This is also reason why DiffArray (from hslibs) does not have to be very useful, unless you have a good control on when things are evaluated -- it may (and it also happened to me) have quadratic behavior in cases like this. To solve this, '!' would have to produce a new array too; but then you must pass it everywhere and effectively you are doing the work monads would do for you. So in general you must choose -- either your programs will be nice and functional, but you will have to use structures with (some kind of) logarithmic slowdown (FiniteMap, Trie), or some of their parts will be embedded in monads. Zdenek Dvorak _________________________________________________________________ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx

1 0

Graphics output
by Gerhard Navratil 08 Oct '02

08 Oct '02

I would like to write line graphics into a file (e.g. contour lines calculated by a Haskell function) and access the data from standard programs. For the output I need a Library. Since I do not to write the output I would like to know if there is a library writing graphics in a standard format like dxf or PostScript. I have not found anything on the Web so this is my last chance. Thanks in advance! Gerhard ==================================== Gerhard Navratil Teaching- And Research-Assistant Vienna University of Technology, Austria Institute for Geoinformation Gusshausstr. 27-29 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12721 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at

3 2

how to debug?
by David Roundy 07 Oct '02

07 Oct '02

How does one debug in haskell? I have a function that I could swear should behave differently than it does, and after tracking down bugs for many hours, I'm wondering if there's any way to step through the evaluation of a haskell function? The other way I would be debugging in an imperative language would be to sprinkle printfs around. Is there any way to do something like that cleanly in haskell? The only thing I can think of would be to modify every function to accept an additional parameter, which seems like it's more likely to introduce bugs than remove them... For what it's worth I'm using ghc, and the only debugging options it seems to have are for debugging the compiler itself. I would be happy to install and use hugs for debugging if it has some nicer debugging mode. I have already isolated my bug within one function, but that function has somewhat funky recursion, and uses an array (which I'm none too familiar with in haskell), and there aren't any smaller parts that I can see to test. :( -- David Roundy http://civet.berkeley.edu/droundy/

3 3