- Haskell-Cafe - Haskell.org

Sets
by Mark T.B. Carroll 02 Jan '03

02 Jan '03

Am I right in thinking that sets of sets don't really work with GHC's Data.Set because "Set a" things aren't instances of Ord? How should I do sets of sets with it? (e.g. Set.mkSet [Set.unitSet 1] gives "No instance for (Ord (Set a))") -- Mark

3 2

Lazy streams and unsafeInterleaveIO
by Jyrinx 02 Jan '03

02 Jan '03

As an experiment for a bigger project, I cooked up a simple program: It asks for integers interactively, and after each input, it spits out the running total. The wrinkle is that the function for calculating the total should be a non-monadic stream function (that is, type [Integer] -> [Integer] so that runningTotals [1,2,3,4,5] == [1,3,6,10,15]). The task is then to write a function to return a stream of integers, grabbing them from IO-land lazily (a la getContents). My first attempts had it not displaying a running total until all input (terminated by an input of 0) had finished, at which point it spit out all the totals (i.e. it wasn't an interactive program anymore). I poked around in the docs and on the Web for a while, and found out about unsafeInterleaveIO, which solved the problem neatly (after I modified runningTotals to be less eager, as it was reading ahead by an extra integer each time). I ended up with the attached code (for GHC 5.04.2). My question is this: Is there a more elegant (i.e. non-"unsafe") way to do this? I vaguely recall from the Hudak book (which I unfortunately don't have convenient at the moment) that he used a channel for something like this (the interactive graphics stuff), but IIRC his system would be overkill for my application (including the bigger project). It doesn't seem like it should need any black magic, and concurrency (which channels need, right?) doesn't appear worth the hassle. Really, my desire comes down to a simple, safe, single-threaded way to write a function to generate a lazy stream. Is there such? Luke Maurer jyrinx_list(a)mindspring.com -- running-total -- Haskell program that takes integers as input, outputting a running total -- after each input -- Demonstrates use of lazy streams module Main where import IO import System.IO.Unsafe import Monad runningTotals :: [Integer] -> [Integer] runningTotals [] = [] runningTotals (x:xs) = rt' 0 (x:xs) where rt' tot (x:xs) = (tot+x) `seq` (tot+x):(rt' (tot+x) xs) rt' _ [] = [] -- Note that runningTotals does what appears to be a stateful calculation when -- numbers are read one at a time; however, lazy streams allow this to be a -- pure function. Haskell is cool. inputNumbers :: IO [Integer] inputNumbers = do x <- putStr "? " >> readLn if x == 0 then return [] else do xs <- (unsafeInterleaveIO inputNumbers) return (x:xs) main = do numbers <- inputNumbers mapM_ (putStrLn . (flip shows) "") (runningTotals numbers)

6 11

call china 6.2¢ www.callez.com
by promotion＠callez.com 31 Dec '02

31 Dec '02

1 0

RE: AW: slide: useful function?
by Mark Carroll 27 Dec '02

27 Dec '02

On Mon, 2 Dec 2002, David Bergman wrote: (snip) > Till then, we "Haskellers" will probably continue expressing our > patterns either directly in Haskell or using highly formal language, > with terms such as "catamorphisms". > > The virtue, and weakness, of traditional design patterns is their > vagueness and informal character, making them (1) comprehensible to the > 90% of the developer community not familiar with category theory but (2) (snip) If there are any good ways in which non-mathematicians can get to grips with these terms from category theory, they would be well worth promoting. For example, despite having a good computer science degree (in which I was at least introduced to FP, proof, etc. and even learned to draw the dual graph of hypercubes) I'm really not equipped to understand catamorphisms in terms of algebras and homomorphisms, and don't currently have time to take the math degree I fear I'd need in order to do so. Last time I was looking at category theory books I think I came to the conclusion that Lawvere and Schanuel cover things kindly but Pierce seemed to get the syllabus right, so the "right" book wasn't quite out there. My understanding of monads is already a matter of record. Does anyone know of a friendly text that might help new Haskellers to understand functors, etc. and what they mean for program design? I'm not averse to the formal language per se if it can be easily acquired; right now, I worry that I'm using Haskell suboptimally because, not only do I not know the terminology well, but I fear that I'm not even cognisant of the concepts that these terms represent. In a nutshell: if these category theory concepts indeed have an important impact in Haskell land, how to introduce them to working Haskell programmers well enough that they can use them in engineering software that's at least half as good as it could be? (I'm making the assumption here that it would be good for Haskell to be much more widely used - it shouldn't solely be for researchers.) -- Mark

3 2

RE: Record of STRefs better than STRef to a Record?
by Simon Marlow 27 Dec '02

27 Dec '02

> If I use an STRef to a record, will a new record be created > each time I want > to update a single field? Or can I expect GHC to optimize it > and have the field of the record updated in place? You'll get a new record for each update. This might not be so bad though, depending on the number of fields in your record. > Right now I'm using a record of STRefs, like: > data E s = E{ > refi :: STRef s Int, > refc :: STRef s Char > } > > but it can get a little messy, since thread s propagates to > every datatype that uses the record type in it's definition. Here's another trick if you use this route: data E s = E{ refi :: !STRef s Int, refc :: !STRef s Char } and compile with -funbox-strict-fields. This will eliminate the boxing of the STRefs. Cheers, Simon

4 4

ABD G��menlik/Green Card 2003 y�l� kay�tlar�m�z ba�lam��t�r...
by G��MENL�K/ABD 27 Dec '02

27 Dec '02

1 0

RE: Parsing date and time specifications
by Simon Marlow 26 Dec '02

26 Dec '02

> I was probably a bit quick on the trigger there. Sorry! > > It't been a while since I tried using CalendarTime and friends; I did > have some difficulty making things fit, and eventually gave up the > whole thing. My impression (which may well be a wrong one) was that > others also had trouble adapting the library to their uses, too, and > that the Time library was one of the less successful ones. That may well be true, and I've heard others suggest that the library is inconvenient. I'm trying to get at whether that is due to current bugs in the implementation, or whether the design is fundamentally broken. > Looking at it now, possible criticisms could arise from the data types > containing redundancy and non-uniqueness: e.g. one can easily > construct non-consistent CalendarTimes, Ok, I don't consider that to be a problem. The toClockTime operation should fail if the CalendarTime is inconsistent. Non-uniqueness isn't a problem: you can convert to a ClockTime which is unique. I think of the CalendarTime as a slightly more tractable representation of a date/time string; lots of date strings don't make sense either (eg. "31 February"). > and there are multiple ways > to represent the same interval as TimeDiff -- in fact, two TimeDiffs > may or may not be equal, depending on what CalendarTime they apply > to. (The 'deriving' of Eq makes this a moot point, perhaps, but > seems to make equality rather non-intuitive) I think this is the wrong way to look at it: two TimeDiffs should be equal if and only if all their components are respectively equal (i.e. the deriving Eq meaning). This is different from saying that "the effect of adding this TimeDiff is the same as adding this other TimeDiff", which depends entirely on what you're adding it to. So this cannot lead to a sensible meaning for Eq on TimeDiff. Ah - I've just realised one problem with the design. If you have a TimeDiff with multiple non-zero components (eg. one hour and one second), then the order in which you add them makes a difference, and this order isn't specified by the spec. That's probably why TimeExts has only single-unit differences. And another thing: it should be specified that diffClockTimes gives a TimeDiff in units of seconds & picoseconds, because these are the only forms of TimeDiff that have the same meaning independent of what ClockTime they are added to. > It seems that TimeDiffs perform two functions; deltas for ClockTimes > (in the functions) and intervals of calendar times (specification of > the data type), and I'm not sure it's a good idea to mix those. I think TimeDiffs are deltas for ClockTimes only. Why do you say they are intervals of calendar times too? If we were to have an operation which adds a TimeDiff to a CalendarTime, then its meaning should be the same as converting the CalendarTime to a ClockTime, adding the TimeDiff, and converting back to a CalendarTime again. > Oh well. I'm not using Time at the moment, so its not an issue that > will ruin my holiday for me :-) me either :) Cheers, Simon

2 1

Re: Interpret haskell within haskell.
by Christopher Milton 26 Dec '02

26 Dec '02

--- David Sankel <camio(a)yahoo.com> wrote: > I was wondering if there is any project that aims to > interpret haskell within haskell. http://www.haskell.org/implementations.html <quote type="partial"> GHC, the Glasgow Haskell Compiler The Glasgow Haskell compiler is a full implementation of Haskell. It is itself written in Haskell and is designed to act as a substrate for the research work of others. The source code is freely available. It produces fast code. </quote> The GHC interpreter is ghci. (It's not as slow anymore.) http://www.haskell.org/ghc/ The other Haskell interpreters also load and interpret users' Haskell source code, as well. If you have defined functions in "myprog.hs": :load myprog.hs then the functions defined in the file are available, or else you'll get error message(s) about problems found parsing "myprog.hs". __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com

9 9

Space explosion
by Jyrinx 26 Dec '02

26 Dec '02

I'm tinkering with a little program I wrote a while back to generate probability distributions and averages for rolling various kinds and quanitities of dice and applying various rules (for instance, roll four six-sided dice, drop the lowest, and add the other three). I'm trying to optimize the thing, and I've run into a space leak. I've found that, if I tell it to roll four 20-sided dice and add, it finishes in under a second and heap usage peaks at under 2MB (not sterling, but not catastrophic); but if I make it five 20-sided dice, it runs out of stack space after thrashing for a while (and getting partway through the final output); for six dice, it thrashes into oblivion. (Running WinXP with 256MB memory.) What puzzles me is that, according to GHC's heap-usage-by-call-center graph, the hog isn't the code that generates every single outcome of rolling the dice (and we're talking about four 20-sided dice here ...), whose heap usage is constant (go GHC! :-) ), but the one that turns the list of outcomes (for instance, [2,3,3,4,4,4 ... 7,7,7,7,7,7 ... 11,11,12] for adding two 6-sided dice) into a probability distribution (like [(2,1),(3,2),(4,3) ... (7,6) ... (11,2),(12,1)]). It is this: > -- Specs contains the options for the simulation; rollBounds simply finds the lowest and highest possible rolls > -- type RollValue = Int > -- type RollValueDist = Array RollValue Int > probDist :: Specs -> [RollValue] -> RollValueDist > probDist specs rolls = > accumArray (+) 0 (rollBounds specs) [(r, 1) | r <- rolls] It should be doing an in-place array update as it evaluates the comprehension, but apparently something's being kept in memory longer than it has an excuse for. I tried another, more hand-coded version, to get rid of the mid-calculation comprehension and some possible overhead: > probDist specs = > foldl update orig > where orig = array bounds [(r, 0) | r <- range bounds] > update dist r = dist // [(r, 1 + dist!r)] > bounds = rollBounds specs But this one was even worse. I've sprinkled $! around quite liberally, to no avail; also, I'm compiling with -O, and I've tried various RTS options with no radical change in behavior. What's going on here? The array constructed has to be big, but not *that* big (77 Ints for four 20-sided) ... Is there an inherent inefficiency with GHC's arrays when used like this? I can't come up with a better algorithm - making a zeroed array with an element for each outcome, then adding 1 to the element for each outcome as it is read in seems straightforward enough. (Would a FiniteMap be any better? I'm not sure how ...) Thanks for any help ... I'm starting to get the hang of Haskell, but some of these semantic subtleties are driving me nutty ... Luke Maurer jyrinx_list(a)mindspring.com

1 0

Re: Interpret haskell within haskell.
by oleg＠pobox.com 24 Dec '02

24 Dec '02

Lauri Alanko wrote on Dec 22: > The magic is _here_: > (begin (define a 5) (eval '(set! a (+ a 1)) (interaction-environment)) a) > ==> 6 > Here (interaction-enviroment) is a run-time representation of the > compile-time environment. It makes possible two-way interaction between the > stages. Essentially, first-class environments are all the magic you need to > implement eval. I'm sorry to act as a Grinch, but there is no magic. First, according to R5RS, (interaction-environment) is not a first-class environment. R5RS says (Section 6.5): > [[optional procedure]] (interaction-environment) > This procedure returns a specifier for the environment that contains > implementation-defined bindings, typically a superset of those listed > in the report. The intent is that this procedure will return the > environment in which the implementation would evaluate expressions > dynamically typed by the user. There is nothing there about interaction between phases. And in fact, this interaction does not work. If you put the following code (module aaa) (begin (define a 5) (eval '(set! a (+ a 1)) (interaction-environment)) (display a) (newline)) into a file, _compile_ that file using Bigloo, and run the resulting a.out, you will see a message *** ERROR:bigloo:eval: Unbound variable -- a Nowhere the Scheme report talks about first-class environments. Please note that the result of (interaction-environment) is a _specifier_ for an environment. Some Scheme systems do provide first-class environments. For example, MIT Scheme has a form 'the-environment'. It comes at a price. In a post "Re: why isn't the environment explicit ?" on comp.lang.scheme on Mar 15, 2001, Joe Marshall wrote: > > Since you can (sort of) regard call/cc as making continuations > > explicit, why aren't environments explict ? > In MIT Scheme, they are. The special form (the-environment) returns > the current environment as a first-class object. > However. > The difficulty with using such a form is that it destroys any > possibility of compiler optimization. If you compile code with a > (the-environment) form in it (in MIT Scheme), the compiler essentially > throws up its hands and inserts code to call the interpreter. There is no Santa either.

1 0