Lighthouse has a new layout. Prefer the old one? Return to the old layout, and switch back any time from the link at the top of each page.

Need better representation for sets

#12

My initial implementation for CSPM sets used Haskell's “set-like” list functions (nub, union, etc). This works fine for constructing lists that don't contain duplicates, but the resulting lists are still unordered, so other operations (like equality) don't work out of the box. I need to either write functions that implement these operations on set-like lists, or choose a new implementation data structure for sets.

Reported by Douglas Creager · August 26th, 2008 @ 11:47 PM

State: resolved
Milestone: none
Assigned to: Douglas Creager Douglas Creager

Activity

  1. Douglas Creager
    Douglas Creager

    (from [667366c6ebf41bc7b5ba2d6923339de02bbc56c9]) New implementation of sets

    This patch introduces a new implementation for sets. It's based on the Data.Set standard library, augmented to also allow open ranges. This implementation gives a canonical representation for every set, making equality comparisons easy. Unfortunately, this representation might not work out completely, since the only infinite sets that are directly supported are open ranges. The powerset of an open range, for instance, causes a stack overflow, since we eventually try to create a Data.Set instance of the result. This requires reading in the entire powerset, which, of course, borks.

    Lighthouse: [#12 Need better representation for sets] http://github.com/dcreager/hst/c...

    September 6th, 2008 @ 11:58 PM

  2. Douglas Creager
    Douglas Creager
    • State changed from new to resolved

    (from [86b9163741d52e3212bc93f57b7660a06e6deacf]) Infinite sets

    This patch introduces another new implementation for sets, which supports any infinite set. (The previous implementation only supported open ranges.) A set is now defined by a “loader list”. The loader list can be infinite, and can contain duplicates. Sets can be accessed in one of two ways. The toSet function turns the set into an instance of the standard Data.Se t type. As such, it only works on finite sets. The toList function, on the other hand, returns the elements as a lazy list. It therefore supports infinite sets. As elements are extracted from the loader list, they are added to a “storage set”; the result is that the toList function returns the original loader list, with duplicates removed.

    Lighthouse: [#12 Need better representation for sets state:resolved] http://github.com/dcreager/hst/c...

    September 9th, 2008 @ 03:28 PM

Please Sign in or create a free account to add a new ticket.

With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.