Preliminary Design of Edison: A Library of Efficient Data Structures

1997-07-20 Thread Chris Okasaki
I am in the process of designing and implementing a library of efficient data structures tentatively named Edison. However, before I get too deep in the implementation I wanted to solicit feedback from the Haskell community on the preliminary design of the library. I have sketched the general

Re: Heap Sort

1997-10-04 Thread Chris Okasaki
[EMAIL PROTECTED] wrote: Here is my version: [...] On 21 Sep , Chris Dornan wrote: When would a heap sort be preferable to a merge sort? a) When you want to explain the imperative heapsort But the heapsort you give is nothing like the standard imperative heapsort! Yes, it uses a

Re: heap sort or the wonder of abstraction

1997-10-08 Thread Chris Okasaki
--167E2781446B Content-Type: text/plain; charset="us-ascii" Ralf Hinze wrote: Practitioners are probably surprised to learn that `pairingSort' is the algorithm of choice for sorting. Any objections to this recommendation? I was surprised to see that it performs so well: sorting

First CFP: WAAAPL'99 (Workshop on Algorithmic Aspects of Advanced Programming Languages)

1998-11-10 Thread Chris Okasaki
ptember 29 and morning of September 30, 1999 Submission details: Prospective authors should submit papers of up to 12 pages to Chris Okasaki ([EMAIL PROTECTED]) on or before June 16, 1999. Papers should be formatted in Postcript for USLetter paper. Accepted papers will be published in an

Re: STL Like Library For Haskell

1999-04-28 Thread Chris Okasaki
Simon Peyton-Jones wrote: Chris Okasaki is working on just such a thing. He'll be ready soon... Lest this be taken too literally however, let me clarify. I am working on the "Containers" part of the "Containers and Algorithms" that Kevin asked about. I am *not*

Edison

1999-05-21 Thread Chris Okasaki
I am pleased to make the first public release of Edison, a library of data structures for Haskell. See http://www.cs.columbia.edu/~cdo/edison/ for details. Many thanks to Ralf Hinze for solving the makefile problems that had been plaguing me for many months! Chris Okasaki

Re: Kind Question

1999-05-26 Thread Chris Okasaki
Lennart Augustsson wrote: But what can such a type be used for? This particular example is not very useful, but there are examples where higher kinds are used. Chris Okasaki have some for representing square matrices. Here's a simpler example. Consider the type of non-empty, multiway

WAAAPL proceedings available

1999-09-16 Thread Chris Okasaki
The program and links to invidual papers are at http://www.cs.columbia.edu/~cdo/waaapl-prog.html The proceedings will also be available shortly as a Columbia University technical report. Enjoy, Chris Okasaki

CFP: Special Issue of JFP on Algorithmic Aspects of Functional Programming Languages

1999-10-07 Thread Chris Okasaki
for submissions is February 16, 2000. Chris Okasaki [EMAIL PROTECTED]

Second CFP: Special Issue of JFP on Algorithmic Aspects of Functional Programming Languages

1999-12-15 Thread Chris Okasaki
for submissions is February 16, 2000. Chris Okasaki [EMAIL PROTECTED]

Re: Haskell 98: partition; and take,drop,splitAt

2000-01-24 Thread Chris Okasaki
Simon Peyton-Jones wrote: Take and drop ~ Jan Kort points out that a) (take n xs) and (drop n xs) are defined for n length xs In that case they do something reasonable and useful (take gives back xs, drop gives the empy list) b) They are both also defined if the

Re: drop take [was: fixing typos in Haskell-98]

2000-01-25 Thread Chris Okasaki
I'm with the option (B): negatives are just outside the domain of takedrop, and should give you an error message. For the people that share this sentiment, can you please explain why ints that are too big should not similarly give an error? I can see both being ok, or both being errors. I

Re: drop take [was: fixing typos in Haskell-98]

2000-01-25 Thread Chris Okasaki
I'm with Jon Fairbairn on this. Negative arguments are an error because the domain of take and drop is the naturals. The problem is that we use Int to represent naturals. -- P Yep, this is exactly the same argument we had about this a year or two ago, Phil. My attitude about the "implicit

newtypes

2000-03-16 Thread Chris Okasaki
The Haskell report says that in newtype T = C t T uses the same representation as t, and so coercions between the two can be implemented without execution time overhead. Furthermore, the report says that "unlike type synonyms, newtype may be used to define recursive types." How are these

coercing newtypes

2000-04-17 Thread Chris Okasaki
Many of you have run across the problem with newtypes that, although it is very cheap to coerce between the newtype and the base type, it can be very expensive to coerce between, say, a list of the newtype and a list of the base type. Stephanie Weirich and I are working on a proposal for the

Re: doubly linked list

2000-04-27 Thread Chris Okasaki
I wonder if it is possible to simulate a doubly linked list in Haskell. Depends on what you mean. - Using mutable state in a monad you can implement a doubly linked list directly. - If you store all the nodes of the doubly linked list in an array and simulate the pointers with

Re: doubly linked lists

2000-04-28 Thread Chris Okasaki
The implementation that uses laziness to get true backpointers seems to have caught everybody's imagination. Several people have hinted at the big weakness of this implementation, but lest any beginners reading this thread be misled, let me just state that weakness explicitly -- it takes O(n)

Re: Library conventions

2000-06-23 Thread Chris Okasaki
These suffixes are doing namespace management, avoiding name clashes between different things that you want to call empty. But Haskell already has a perfectly good language mechanism for doing this -- the module system! Why is emptyX preferable to X.empty? The latter convention is

Re: Library conventions

2000-06-24 Thread Chris Okasaki
Edison uses update :: Seq s = Int - a - s a - s a adjust :: Seq s = (a - a) - Int - s a - s a for what my guidelines could give setElem:: Seq s = s a - Int - a - s a updateElem :: Seq s = s a - Int - (a - a) - s a Not that I don't like partial application, but Edison's order

Re: Library conventions

2000-06-24 Thread Chris Okasaki
Seems that it would get simpler if association maps were expressed as collections of key:=value pairs (with Eq,Ord instances ignoring the value component). Association maps would have extra functions, but they could be always treated as appropriate collections of such pairs. Is this idea

bug or feature?

1999-12-16 Thread Chris Okasaki
(I'm using GHC 4.04 patchlevel 1...) Suppose I have a type involving higher kinds such as data H f a = H (f a) and now suppose I want to define equality on this type. I *cannot* say instance Eq (f a) = Eq (H f a) where H x == H y = x == y because I get an error message Illegal

Re: Bug in Edison Makefile

1999-12-21 Thread Chris Okasaki
Simon Marlow wrote: When you call `make all' from the edison subdir, the compiler and the flags change magically and dependencies seem to be broken: You shouldn't try building in the edison subdir; the Makefile in fptools/hslibs/data is designed to reach into edison and build the required

Re: RFC: Overloaded arrays

2000-03-29 Thread Chris Okasaki
Simon Marlow wrote: class HasBounds a = IArray a e where (!) :: Ix ix = a ix e - ix - e array :: Ix ix = (ix,ix) - [(ix,e)] - a ix e class (Monad m, HasBounds a) = MArray a e m where read:: Ix ix = a ix e - ix - m e

Re: RFC: Overloaded arrays

2000-03-29 Thread Chris Okasaki
Simon Marlow wrote: Actually, I'm slightly concerned about your use of small arrays: the static (one-off) cost of allocating an array is quite high compared to eg. tuples or records. Are arrays the only solution here? You're right of course that arrays are quite expensive, but it is not