November 2003 - Haskell-Cafe

Subsumption in partially ordered sets
by Graham Klyne 18 Nov '03

18 Nov '03

I have a need for an algorithm to perform "subsumption" on partially ordered sets of values. That is, given a selection of values from a partially ordered set, remove all values from the collection that are less than some other member of the collection. Below is some code I have written, which works, but I'm not sure that it's especially efficient or elegant. Are there any published Haskell libraries that contain something like this? #g -- (The implementation here is based on values of type (Eq a) => [Maybe a], where the partial ordering is defined by function 'pcompare'. Function dropSubsumed (and helpers) is the subsumption calculation. testds1, testds2, testds3, testds4, testds5 are test cases, and all should be True.) [[ -- Type for result of partial order comparison (PNR is no-relationship) data PartOrdering = PLT | PEQ | PGT | PNR deriving (Eq, Show) -- Drop tuples from the supplied list that are subsumed by -- more specific ones. -- dropSubsumed :: (Eq a) => [[Maybe a]] -> [[Maybe a]] dropSubsumed [] = [] dropSubsumed [a] = [a] dropSubsumed (a1:as) = dropSubsumed1 a1 as dropSubsumed1 a1 [] = [a1] dropSubsumed1 a1 (a2:a2s) = case pcompare a1 a2 of PEQ -> dropSubsumed1 a1 a2s PGT -> dropSubsumed1 a1 a2s PLT -> dropSubsumed1 a2 a2s PNR -> dropSubsumed2 [] a1 $ dropSubsumed1 a2 a2s -- Merge new head element into list from which subsumed elements -- have already been removed. The extra (first) parameter is used -- to construct a result in which the order of remaining elements -- is preserved with respect to the original list. dropSubsumed2 a1s a [] = a : revConcat a1s [] dropSubsumed2 a1s a ar@(a2:a2s) = case pcompare a a2 of PEQ -> a : revConcat a1s a2s PGT -> a : revConcat a1s a2s PLT -> revConcat a1s ar PNR -> dropSubsumed2 (a2:a1s) a a2s revConcat :: [a] -> [a] -> [a] revConcat [] a2s = a2s revConcat (a1:a1s) a2s = revConcat a1s (a1:a2s) -- Perform subsumption calculation between a pair of tuples -- A tuple with more information subsumes a one with less but -- consistent information. -- pcompare :: (Eq a) => [Maybe a] -> [Maybe a] -> PartOrdering pcompare a1s a2s = pcompare1 a1s a2s PEQ pcompare1 [] [] po = po pcompare1 (Just _:a1s) (Nothing:a2s) po = if (po == PEQ) || (po==PGT) then pcompare1 a1s a2s PGT else PNR pcompare1 (Nothing:a1s) (Just _:a2s) po = if (po == PEQ) || (po==PLT) then pcompare1 a1s a2s PLT else PNR pcompare1 (a1:a1s) (a2:a2s) po = if a1 == a2 then pcompare1 a1s a2s po else PNR pcompare1 _ _ _ = PNR testds1 = ds1a == ds1b ds1a = dropSubsumed [ [Just 'a',Just 'b',Just 'c'] , [Just 'a',Just 'b',Nothing ] , [Just 'a',Nothing ,Just 'c'] , [Just 'a',Nothing ,Nothing ] , [Nothing ,Just 'b',Just 'c'] , [Nothing ,Just 'b',Nothing ] , [Nothing ,Nothing ,Just 'c'] , [Nothing ,Nothing ,Nothing ] ] ds1b = [ [Just 'a',Just 'b',Just 'c'] ] testds2 = ds2a == ds2b ds2a = dropSubsumed [ [Just 'a',Just 'b',Nothing ] , [Just 'a',Nothing ,Just 'c'] , [Just 'a',Nothing ,Nothing ] , [Nothing ,Just 'b',Just 'c'] , [Nothing ,Just 'b',Nothing ] , [Nothing ,Nothing ,Just 'c'] , [Nothing ,Nothing ,Nothing ] ] ds2b = [ [Just 'a',Just 'b',Nothing ] , [Just 'a',Nothing ,Just 'c'] , [Nothing ,Just 'b',Just 'c'] ] testds3 = ds3a == ds3b ds3a = dropSubsumed [ [Just "a1",Just "b1",Just "c1"] , [Just "a2",Just "b2",Nothing ] , [Just "a3",Nothing ,Just "c3"] , [Just "a4",Nothing ,Nothing ] , [Nothing ,Just "b5",Just "c5"] , [Nothing ,Just "b6",Nothing ] , [Nothing ,Nothing ,Just "c7"] , [Nothing ,Nothing ,Nothing ] ] ds3b = [ [Just "a1",Just "b1",Just "c1"] , [Just "a2",Just "b2",Nothing ] , [Just "a3",Nothing ,Just "c3"] , [Just "a4",Nothing ,Nothing ] , [Nothing ,Just "b5",Just "c5"] , [Nothing ,Just "b6",Nothing ] , [Nothing ,Nothing ,Just "c7"] ] testds4 = ds4a == ds4b ds4a = dropSubsumed [ [Just 1, Just 1 ] , [Just 2, Nothing] , [Nothing,Just 3 ] , [Nothing,Nothing] ] ds4b = [ [Just 1, Just 1 ] , [Just 2, Nothing] , [Nothing,Just 3 ] ] -- Check handling of equal values testds5 = ds5a == ds5b ds5a = dropSubsumed [ [Just 1, Just 1 ] , [Just 2, Nothing] , [Nothing,Just 3 ] , [Nothing,Nothing] , [Just 1, Just 1 ] , [Just 2, Nothing] , [Nothing,Just 3 ] ] ds5b = [ [Just 1, Just 1 ] , [Just 2, Nothing] , [Nothing,Just 3 ] ] ]]

4 4

There is flexible exception handling in Haskell?
by 7253146＠informatica.alumnos.uma.es 17 Nov '03

17 Nov '03

Hi all. I am porting to Haskell a small zlib-based library for .zip files (I have not seen any released package for it, although it should very useful). The matters come when I try to address exceptional conditions: all the library functions return a integer code with OK/SOMEERROR meaning. The most natural way to carry the exceptional situations should be raise IO exceptions, but here comes the problem: how can I define new Exception codes, instead of raising userError all the time? I think it makes sense for a library to raise specialized exceptions, instead of userErrors. There is such a mechanism? Can someone help? Thanks. --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

1 0

Hypothetical reasoning in type classes
by Ken Shan 16 Nov '03

16 Nov '03

Hello, Has anyone thought about adding hereditary Harrop formulas, in other words hypothetical reasoning and universal quantification, to the instance contexts in the Hsakell type class system? Just today (and not only today) I wanted to write instance definitions like instance (forall a. C a => D a) => E [a] where ... This is analogous to wanting to write a rank-2 dictionary constructor (forall a. C a -> D a) -> E [a] at the term level, but with type classes, this dictionary constructor should be applied automatically, in a type-directed fashion, at compile time. The theory behind such instance contexts doesn't seem so intractable; indeed it looks decidable to my cursory examination. The opreational intuition is that we would like the type checker to generate an eigenvariable "a" and perform hypothetical reasoning. I would also like to quantify universally over type classes; in other words, if "?" is the kind of a type class constraint (aka a dictionary type; perhaps "o" would be a better choice of notation), then I would like to define not just types of kind "*->*->?" (aka type classes) or kind "(*->*)->?" (aka constructor classes), but also types of kind "(*->?)->(*->?)". But that's for another day... Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig "Hi, my name is Kent, and I let people change my .sig on the internet." "Hi, Ken!" "Put midgets back in midget porn!" -- Not authorized by Ken Shan. Supported by the association of midget porn workers, Local 9823.

2 1

what's the deal with "user error" on fail?
by David Roundy 15 Nov '03

15 Nov '03

When one triggers an exception with something like fail "Error opening file" The user gets a message like Fail: user error Reason: Error opening file which is confusing to the user, because it the user's fault. Is there some other way that it is recommended one fail? Or should I be catching userErrors at the top level and failing with my own error message? -- David Roundy http://www.abridgegame.org/darcs

3 3

RE: Type tree traversals [Re: Modeling multiple inheritance]
by Simon Peyton-Jones 15 Nov '03

15 Nov '03

| More overlapping: | Allow any overlapping rules, and apply the most specific rule that | matches our target. Only complain if there is a pair of matching | rules neither of which is more specific than the other. | This follow the spirit of the treatment of duplicate imports... Happy days. I've already implemented this change in the HEAD. If you can build from source, you can try it. | Backtracking search: | If several rules matched your target, and the one you picked didn't | work, go back and try another. | | This isn't as well through out: you probably want to backtrack through all | the matching rules even if some are unordered by being more specific. It | would probably be godd enough to respect specificity, and make other | choices arbitrarilily (line number, filename, etc. maybe Prolog has a | solution?). This probably isn't too hard if you can just add | nondeterminism to the monad the code already lives in. I didn't follow the details of this paragraph. But it looks feasible. | Overloading resolution: | This one is really half-baked, but sometimes it would be nice if there was | some way to look at | class MyNumber a where | one::a | instance MyNumber Int where | one = 1 | | then see (one+1) and deduce that the 1 must have type Int, rather than | complaining about being unable to deduce MyNumber a from Num a. This is | really nice for some cases, like a lifting class I wrote for an Unlambda | interpreter, with instances for LiftsToComb Comb and (LiftsToComb a => | LiftsToComb (a -> Comb)). With some closed world reasoning lift id and | lift const might give you I and K rather than a type error. Also, for | this work with modelling inheritance you almost always have to give type | signatures on numbers so you find the method that takes an Int, rather | than not finding anything that takes any a with Num a. This obviously | breaks down if you have instances for Int and Integer, and I don't yet | know if it is worth the trouble for the benefits in the cases where it | would help. Implementation is also a bit tricky. I think it requires | unifying from both sides when deciding if a rule matches a goal. I'm much less sure about this stuff. Mark Shields and I did something about closed classes in our OO paper http://research.microsoft.com/~simonpj/Papers/oo-haskell/index.htm, and Martin Sulzmann and colleagues have done lots of foundational work -- but the dust is still swirling I think. Simon

4 3

RE: haskell httpd
by Simon Marlow 14 Nov '03

14 Nov '03

> <rant> > Frustrating. > > Its been 4 years since I seriously looked at > Haskell. I would have expected that over this > time, someone here would have consolidated it into > a language useful for real world applications. > > The Haskell in Practice page is shockingly short > and many of the examples are not actually Haskell > in practice. > > Does anyone here eat the Haskell dog food or is > this all just fooling around (basic reasearch)? > > Simon, why did you write the Haskell web server? 1. To show that it could be done 2. Because it was fun, and 3. So I could write a paper about it Note that this list does *not* include 4. So I could use it However, several people have found the web server useful and are using it, either as the basis of further research, or in some cases as the basis for a real production web server. It isn't a production web server, as you noticed, but it's a start. Cheers, Simon

2 1

Re: what's the deal with "user error" on fail?
by Jon Cast 13 Nov '03

13 Nov '03

David Roundy <droundy(a)abridgegame.org> wrote: > hello, > well that's because haskell is not as pure as it claims to be :-) Nonsense. Haskell is perfectly pure; the IO monad is just nondeterministic :) > if every monad supports errors depends on what you mean by "supporting > errors". I mean `supporting errors' in the only possible sense that `supporting errors' can be implied by the existence of `fail': we have a throw function. > i would argue that supporting errors and divergence is not the same > thing. I never said it was. > the difference is that one should be able to handle an error thrown by > a computation, Although this doesn't imply the existence of a `catch' HOF; see the MonadPlus instance for Maybe. > while clearly we cannot detect nonterminating computations. Of course. But we can detect exceptions thrown by `error'. Even though we can't distinguish them from non-termination /in pure Haskell/. We can of course distinguish them in the IO monad (which perhaps ought to be re-named the SinBin monad, to be more honest...). So we can detect erroneous computations in any monad. Jon Cast

1 0

record matching syntax forensics
by John Meacham 13 Nov '03

13 Nov '03

so I noticed DrIFT was generating code like f Foo{bar} = ... as seemingly a shorthand for f Foo{bar = bar} = ... which does not seem to work with current compilers. I fixed this in 2.0.2 but was curious why it was generating code like that in the first place. it appears to be illegal looking at the haskell report and I was uncertain who wrote the derive rules in the first place so thought I would ask here. John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net ---------------------------------------------------------------------------

2 1

Re: what's the deal with "user error" on fail?
by Jon Cast 13 Nov '03

13 Nov '03

David Roundy <droundy(a)abridgegame.org> wrote: > i would say that if you are wanting to report errors to users, you > should not use "fail" or "error". you should instead explicitly > report the error. when i program i typically use "error" in > situations that i think are imposible, but if there is a bug one gets > a better error messeage. i don't use fail (well except sometimes > implicitly in list comprahensions). the reason i avoid "fail" is that > it seems hackish to me -- it implies that every monad supports errors ^^^^^^^^^^^^^^^^^^^^^^^^^^^ In Haskell, this is indeed the case---every monad is after all a monad transformer applied to Haskell's identity monad, which supports errors (hence the existence of Haskell's `error' function :). So even if a monad designer doesn't explicitly add error support, the monad still supports errors. Jon Cast

3 2

Re: ANNOUNCE: Release of Vital, an interactive visual programming environment for Haskell
by Graham Klyne 13 Nov '03

13 Nov '03

[Switching to haskell-cafe] For "serious programming", I entirely agree. But my view is that we are seeing some degree of programmability entering all sorts of everyday objects -- video recorders spring to mind as an early example -- and there's lots of work going on in the field of "ubiquitous computing". Many of these pervasive devices may be fire-and-forget, but I suspect many will not be. Graphical displays may be more common than full keyboards. So how is the user to be presented with options to enter programming information? I don't have any final answers here, but I do have an intuition that for many users, where the "programming" requirement is a simple but flexible composition of existing functions, that a graphical, self-documenting interface may be an appropriate response to the "video recorder programming hell" syndrome. Some of my thoughts about this came from considering issues faced by a friend of mine who has recently wired his new home for "total data" (several kilometres of Cat5A cable in the loft!) -- it's all very well having all these intelligent devices around the home, but how to actually tell them what to do? Opening a door may signal that a light should turned on, or an alarm should be set off -- how to describe the distinction? (Assuming the owner is not an experienced programmer.) Finally, as evidence for this view of user interfaces, I note that for tasks like computer system administration, graphical interfaces have pretty much taken over from the old command-line-and-text-file approach. Even Linux systems have graphical front-ends for most of the common configuration, even though, for an experienced sysadmin, the text-based versions are generally quicker to set up and understand what's happenning. In short, it's the occasional user, not the full-time expert, who may be better served by a non-textual approach. #g -- At 23:56 12/11/03 +0100, Marcin 'Qrczak' Kowalczyk wrote: >W li¶cie z ¶ro, 12-11-2003, godz. 11:06, Graham Klyne pisze: > > > I've sometimes thought that a functional language would be the ideal > > platform to usher in a purely graphical style of programming; > >I don't understand why so many people talk about graphical programming, >i.e. putting together functions, arguments, definitins etc. with the >mouse instead of the keyboard, drawing arrows instead of naming etc. > >No wonder it didn't succeed. It would be much less convenient than >typing text and less readable too. > >-- > __("< Marcin Kowalczyk > \__/ qrczak(a)knm.org.pl > ^^ http://qrnik.knm.org.pl/~qrczak/ > >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1