November 2004 - Haskell-Cafe

Problem with overlapping class instances
by Graham Klyne 23 Nov '04

23 Nov '04

Once again, the Haskell class system is proving rather subtle for me. On this occasion, I'm getting an overlapping class instance error which I think should be fully disambiguated by the supplied class context. The code below (end of message) is a .lhs file that reproduces the problem in Hugs, with external dependencies from my working codebase stripped out. It should be possible to simply load it (or this whole email) to get the same error: [[ Reading file "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs": ERROR "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs":30 - Overlapping inst ances for class "ConceptExpr" *** This instance : ConceptExpr (a b) *** Overlaps with : ConceptExpr AtomicConcept *** Common instance : ConceptExpr [Char] ]] The line referred to as "this instance" is: instance (ConceptWrapper cw c, ConceptExpr c) => ConceptExpr (cw c) where The reported overlapping instance is [Char], which I take to be derived from the type constructor [] applied to type Char, this yielding a form that matches (cw c). But the instance ConceptExpr (cw c) is declared to be dependent on the context ConceptWrapper cw c, which has *not* been declared for the type constructor []. GHCi with -fglasgow-exts is no more informative. What am I missing here? #g -- [Source code follows] spike-overlap-ConceptExpr.lhs ----------------------------- > type AtomicConcepts a = [(AtomicConcept,[a] )] > type AtomicRoles a = [(AtomicRole ,[(a,a)])] > > type TInterpretation a = ([a],AtomicConcepts a,AtomicRoles a) > class (Eq c, Show c) => ConceptExpr c where > iConcept :: Ord a => TInterpretation a -> c -> [a] ... > type AtomicConcept = String -- named atomic concept Declare AtomicConcept and AtomicRole as instances of ConceptExpr and RoleExpr (AtomicRole is used by AL, and including AtomicConcept here for completeness). > instance ConceptExpr AtomicConcept where > iConcept = undefined ... To allow a common expression to support multiple description logics, we first define a wrapper class for DLConcept and DLRole: > class ConceptExpr c => ConceptWrapper cw c | cw -> c where > wrapConcept :: c -> cw c -> cw c > getConcept :: cw c -> c Using this, a ConceptWrapper can be defined to be an instance of ConceptExpr: This is line 30: > instance (ConceptWrapper cw c, ConceptExpr c) => ConceptExpr (cw c) where > iConcept = iConcept . getConcept Error message: Reading file "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs": ERROR "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs":30 - Overlapping inst ances for class "ConceptExpr" *** This instance : ConceptExpr (a b) *** Overlaps with : ConceptExpr AtomicConcept *** Common instance : ConceptExpr [Char] ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 6

Re: Top Level TWI's again was Re: [Haskell] Re: Parameterized Show
by Graham Klyne 23 Nov '04

23 Nov '04

[Switching to Haskell-cafe] At 11:26 22/11/04 +0000, you wrote: >I would ask an alternative question - is it possible to live without >unsafePerformIO? I have never needed to use it! I have used it once, with reservations, but at the time I didn't have the time/energy to find a better solution. (The occasion of its use was accessing external entities within an XML parser; by making the assumption that the external entities do not change within any context in which results from a program are compared, I was able to satisfy the "proof obligation" of not causing or being sensitive to side effects.) The reason this was important to me is that I wanted to be able to use the parser from code that was not visibly in the IO monad. For me, treating Web data transformations as pure functions is one of the attractions of using Haskell. (Since doing that, I had an idea that I might be able to parameterize the entity processing code on some Monad, and use either an Identity monad or IO depending on the actual requirements. This way, I could keep pure XML processing out of the IO monad, but use IO when IO was needed.) In short: I think it's usually possible to avoid using unsafePerformIO, but I'd be reluctant to cede it altogether, if only for sometimes quick-and-dirty pragmatic reasons. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

8 15

Re: Global variables again
by Benjamin Franksen 23 Nov '04

23 Nov '04

[we should really keep this on haskell-cafe because such lengthy discussions are what the cafe is for] On Tuesday 23 November 2004 10:26, Adrian Hey wrote: > On Monday 22 Nov 2004 4:03 pm, Benjamin Franksen wrote: > > This is getting ridiculous. At least two workable alternatives have been > > presented: > > > > - C wrapper (especially if your library is doing FFI anyway) > > - OS named semaphores > > Neither of these alternatives is a workable general solution. Since the problem only appears in special situations, a general solution is not required, nor is it desirable (because of the danger of infection with the "global variable disease".) > There are several significant problems with both, but by far > the most significant problem (at least if you believe that top > level mutable state is evil) is that they both rely on the use > of top level mutable state. If this is evil it is surely just as > evil in C or OS supplied resources as it is in Haskell. The evil is in the world in the form of C libraries with hidden global variables and hardware with non-readable registers. What I am arguing for is to *contain* this disease by forcing a solution to happen outside of Haskell. What you are arguing for (i.e. a general solution *in* Haskell) amounts to (deliberately) *spreading* the disease. > The fact that one solution requires the use of a completely different > programming language And that is exactly the point: In order to do evil you have to go somewhere else, preferably to where the problem originally came from. If it originated in C, go fix it on the C level. If originates in the OS, go fix it on the OS level. As for broken hardware, you should use a OS level mechanism, so that multiple initialization is prevented OS wide and not only per program run. > and the other requires the use of a library which > could not be implemented in Haskell (not without using unsafePerformIO > anyway) must be telling us that there something that's just plain missing > from Haskell. Yes it's plain missing and for good reasons. There are many things plainly missing from Haskell besides global variables. > IMO this is not a very satisfactory situation for a language > that's advertised as "general purpose". "General purpose" doesn't mean that any programming idiom is supported. > > Further, as for "evidence or credible justification" for the my claim, > > you can gather it from the numerous real-life examples I gave, and which > > you chose to ignore or at least found not worthy of any comment. > > I have no idea what examples you're talking about. Did you post any code? No, I didn't post code. I already said it's annecdotal evidence. For instance, I was talking about using the ONC/RPC implementation on VxWorks, which is broken because they internally use thread-local mutual state. > If so, I must have missed it for some reason. Perhaps your're refering > to your elimination of unsafePerformIO from a library you were writing. I wasn't. > > Of course, > > these examples are only annecdotal but I think this is better than a > > completely artificial requirement (like your "oneShot"). > > Being able to avoid the use of top level mutable state sometimes (or even > quite often) is not proof that it's unnecessary, True. I have never claimed that, though. What I claimed is that in the cases where they are necessary, FFI is probably used anyway, so it *is* workable to use a foreign language wrapper. In order to convince me that this is wrong you could present a (real-world, no artificial requirements) example that does not require the use of FFI anyway. If you can do so (which I doubt) I might be willing to accept a compiler-supported standard library routine with a very long and very ugly name like warningBadStyleUseOnlyIfAbolutelyNecessary_performOnlyOnce: IO a -> IO a ;-) > especially when nobody > (other than yourself presumably) knows why you were using it in the first > place. Not I. And it was for convenience only, as I proved by completely eliminating them without making the code any more complicated. I never claimed that this proves anything, it was just a personal experience. BTW, the main reason they use global variable in C all the time is because it's just so damn convenient (at first) and *not* because there are problems otherwise unsolvable. (There are *very* few exceptions.) > However, the existance of just one real world example where it does > appear unavoidable is pretty convincing evidence to the contrary IMO. I agree that the alternatives are not a good *general* solution. I have been arguing that a general solution is not desirable. > > You have been asked more than once to present a *real-life* example to > > illustrate that > > > > (a) global variables are necessary (and not just convenient), > > (b) both above mentioned alternatives are indeed unworkable. > > I knew this would happen. I was asked to provide an example and I *did*. > I gave the simplest possible example I had of the more general problem, > and now this whole thread has consisted of either repeated denials of > the reality of even this simple problem (something you've just done again) > or protracted discussions over various half baked non-solutions to > this one particular problem (such as those you identify above) without > seeing the real underlying general problem. There is no underlying problem, apart from interfacing evil hardware or foreign libraries. At least I know of none. > > > You have yet to > > > explain how you propose to deal with stdout etc.. > > > > I see absolutely no reason why stdxxx must or should be top-level mutable > > objects. They can and should be treated in the same way as environment > > and command line arguments, i.e. > > > > getArgs :: IO [String] > > getEnv :: String -> IO String > > getStdin, getStdout, getStderr :: IO Handle > > > > Note that (just like environment and command line arguments) these > > handles may refer to completely different things on different program > > runs. > > Sure, Peter Simons suggested the same thing. I have no great objection, > but why do this? Strange. I told you the reason. You even cited it. What about reading it, too ;-? > I mean what extra safety does this buy you? Nobody claimed that global variables are unsafe in any strict sense. > Anybody can > still get at stdout and write anything they like to it. Sure they can. They have been warned, though... ;-) > The only difference is that instead of writing.. > > do ... > foo stdout > ... > > ..they now have to write.. > > do ... > stdout <- getStdout > foo stdout > ... > > I don't see why the former should be regarded as a source of great evil > which is somehow eliminated by the latter. To repeat myself once again: The latter version makes it clear to anyone looking at the code, that the stdout above (a) might refer to something different from other results of getStdout elsewhere in the program (e.g. stdout might have been closed or re-opened) (b) might refer to completely different things on different program runs (e.g. output of program is piped to some other process or even a socket). Ben -- Top level things with identity are evil. -- Lennart Augustsson

1 0

Haskell-cafe message-length restriction
by Graham Klyne 23 Nov '04

23 Nov '04

To the list Haskell-cafe admin... May I suggest that the maximum message length for postings to the haskell-cafe list without moderation be raised from its current 5K limit? It seems to me that a value of (say) 20K would reduce the moderator's workload without obviously allowing too many undesirables ... (though I allow the moderator surely knows more about what is thrown at the list that most of us don't see.) Just a thought. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Mutable and persistent values (was: Top Level TWI's again)
by Graham Klyne 23 Nov '04

23 Nov '04

[I'm moving my response to the Haskell-cafe mailing list, as it seems more appropriate for this kind of discussion.] Your question seems to touch on the old chestnut of how to reconcile pure functional programs with the inherently procedural aspects of I/O and state management. Most of the richness to which you refer is, to my mind, a fairly esoteric corner of Haskell with which I've had little cause to engage. I sense you may be coming from a perspective similar to mine of a couple of years ago, hence this response. Maybe what follows is already well known to you (some of it is basic stuff), so please accept my apologies if I'm retreading well-worn paths for you. The classical work (c. 1970's) on using functions to describe programs that update machine state models such programs as functions that take a state and return a new state, maybe returning some other values as well. This could get complicated to handle, and along the way functional structures based on monads were invoked to tidy up the housekeeping. (A paper by Simon Peyton-Jones and John Launchbury [1] about handling state in Haskell was useful for me.) Note the central role of higher order functions in dealing with this: a state-monad function represents a computation on some state, not the result of that state; the result of the computation is available only when the function is applied to some initial state. The do-notation is a syntactic sugar to make this easier to write, but (I think) it can sometimes obscure what is going on. Philip Wadler's paper "The Essence of Functional Programming" [3] nicely illustrates how monads can take care of various housekeeping chores. The IO monad can be viewed as a special case that allows a program to access and update state ("the real world") that exists outside the program. So, turning to your specific questions/concerns: >Also, ultimately, I want to be able to save my work and restart >the next day (say) picking up the tags where I left off. Your top-level program must be "in the IO monad" (or: is an expression that describes an IO monad value, which is a computation that interacts with the real world). Thus, it can access yesterdays work, and also your interactive inputs, and compute a new value that is today's work. The IO monad allows you to sequence the various interactions with persistent state and user dialogue, in a purely functional way. >I'm darned if I can see how to do this in a callback without a global >variables (and references from other callbacks, by the way). I would expect the callback function to accept an initial value of the "global" variable(s), and return its new value(s), leaving the calling site to ensure that the new value is used as required. (This interaction may be "hidden" in a monad (e.g. a state monad), and if the "callback" itself involves interaction with a user must use the IO monad.) > I want to use the old value of a tag to compute the new value, in a > callback, > > I want to access the tag from other callbacks, and > > I want to the value to a mutable list from within the callback. All of these are accommodated by adopting the accept-a-value-and-return-a-new-value perspective. The calling program that invokes the callbacks deals with ensuring that the callbacks have access to the appropriate results from other callbacks. It is my view that use a functional language effectively, it is necessary to think differently about its structure than one would for a conventional imperative program. Global values become parameters and return values; mutable values become input values and new (separate) return values. If you're used to writing imperative programs that do not use global state, but rather use parameters to pass values, the difference isn't always quite as great as might be imagined. For complex values, this sounds horribly inefficient, but because values are pure (not mutable), very high levels of sharing can (sometimes, with good design!) be extensively shared. Thus, a return value may well consist mostly of a copy of the input value, with differences, rather than actually being a complete new copy. (Chris Okasaki's book shows well how to design to obtain these benefits.) Also, because Haskell is lazy, complex structures passed between functions don't necessarily ever exist in their entirety. Sometimes, I think of a data structure as describing a computational traversal through some data, rathert than something that actually exists. (This leads to very elegant expression of things like Prolog search-and-backtrack algorithms.) So the main point of this posting is to say that I think that the "richness" of "implicit parameters, linear implicit parameters, unsafePerformIO, ..." to which you refer is a shoal of red herring, as far as your goals are concerned. I hope this helps. I've added below a couple of links to my web site to stuff that I accumulated while learning Haskell over the past couple of years. #g -- [1] Simon Peyton-Jones and John Launchbury, State in Haskell, linked from: http://research.microsoft.com/Users/simonpj/Papers/papers.html#monads, document at: http://research.microsoft.com/Users/simonpj/Papers/state-lasc.ps.gz, also at: http://www.cse.ogi.edu/~jl/Papers/stateThreads.ps. Introduces monads as a general technique for handling state, and then introduces a concept of "the world" as a state manipulated by IO. I found this to be one of the more illuminating introductions to Monads (which are central to Haskell I/O). [2] Chris Okasaki, "Purely Functional Data Structures", Cambridge University Press, 1998 [3] Philip Wadler, "The essence of functional programming", linked from http://homepages.inf.ed.ac.uk/wadler/topics/monads.html, paper at http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps . [4] http://www.ninebynine.org/Software/Learning-Haskell-Notes.html [5] http://ninebynine.org/Links.html#Programming-Haskell At 15:34 22/11/04 -0800, John Velman wrote: >On Mon, Nov 22, 2004 at 07:27:44PM +0100, Lennart Augustsson wrote: > > >[snip] > > I admit there are proper uses of global variables, but they are very > > rare. You have not convinced me you have one. > > > > -- Lennart > >It's with some trepidation I bring a problem as a total newbie, but I've >been obsessed with this and hung up on it ever since I decided a couple of >weeks ago to learn Haskell by using it. > >Some brief background: > >A while back I decided I wanted a simple 'concept mapping' program that >would work the way I work instead of the way someone else works. I >envisioned a GUI with a canvas and an entry box (TK/tcl). I type a >"concept name" into the entry box, and it shows up on the canvas (initially >in a slightly randomized position), in a box, with a unique sequenced >identifier. The identifier is also used as a canvas tag for the item. >Similar input for relations between concepts. I think that's enough >description for now. > >Initially, I started programming this with PerlTK, but that effort was >interrupted for a few weeks. When I got back to it, I decided to do it in >Python instead. But that effort also got interrupted for a few weeks. >Before I got back to it, I ran across some material on Haskell I've had in >my files for a few years, and decided that I'd use this as a vehicle to >actually learn Haskell. (This all sounds a bit unfocused, and it is: I'm >retired, sometimes describe myself as an ex mathematician or an ex-PhD >having spent years in the aerospace industry instead of academia. Anyway, >I have both the luxury and lack of focus of no deadlines, no pressure to >publish. I hope to use Haskell to further my main hobby of knowledge >representation.) > >In perl, my labels/tags were very easy: > >In the initialization code: > > my @taglist = (); > my $nextag = "a"; > >and in the callback for the entry box: > > push(@taglist,$nextag); > $nextag++; > >(With the starting tag of "a" this results in "a",...."z","aa","ab",...) > >Also, ultimately, I want to be able to save my work and restart >the next day (say) picking up the tags where I left off. > >I'm darned if I can see how to do this in a callback without a global >variables (and references from other callbacks, by the way). > >In looking for a method, I've discovered that Haskell is a lot richer than >I thought (or learned when I tinkered with it back in the late '90s ). >I've found out about (but don't know how to use properly) implicit >parameters, linear implicit parameters, unsafePerformIO, "safe and sound >implementation of polymorphic heap with references and updates (Oleg >Kiselyov, (http://www.haskell.org/pipermail/haskell/2003-June/011939.html) >implicit configurations, phantom types, ... > >I've also found warnings against many of these. I'm inclined to try the >unsafePerformIO route as being the simplest, and most commonly used, even >though perhaps the least haskell-ish. I like implicit configurations, but >couldn't begin to say I understand them yet, and it's a bit heavy for a >novice. > >In a nutshell: > > I want to use the old value of a tag to compute the new value, in a > callback, > > I want to access the tag from other callbacks, and > > I want to the value to a mutable list from within the callback. > >I'd certainly be interested in doing without global variables, and would >appreciate any advice. > >(By the way, I'm using Linux, and so far it looks like HTk is my choice for >the GUI interface.) > >Best, > >John Velman >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

foldlWhile
by Serge D. Mechveliani 22 Nov '04

22 Nov '04

Is such a function familia to the Haskell users? foldlWhile :: (a -> b -> a) -> (a -> Bool) -> a -> [b] -> a foldlWhile f p a bs = case (bs, p a) of ([], _ ) -> a (_, False) -> a (b:bs', _ ) -> foldlWhile f p (f a b) bs' foldl does not seem to cover this. Example. Sum the list while the sum is less than bound: boundSum :: Integer -> [Integer] -> Integer boundSum b = foldlWhile (+) (< b) 0 Example: boundSum 100 $ map (^2) [1 ..] Is this reasonable? More `generic' variant: foldlWhileJust :: (a -> b -> Maybe a) -> a -> [b] -> a foldlWhileJust f a bs = case bs of [] -> a b:bs' -> case f a b of Just a' -> foldlWhileJust f a' bs' _ -> a Please, copy the replies to mechvel(a)botik.ru ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2

Re: [Haskell-cafe] foldlWhile
by Serge D. Mechveliani 22 Nov '04

22 Nov '04

To my question of >> foldlWhile :: (a -> b -> a) -> (a -> Bool) -> a -> [b] -> a >> foldlWhile f p a bs = >> case >> (bs, p a) >> of >> ([], _ ) -> a >> (_, False) -> a >> (b:bs', _ ) -> foldlWhile f p (f a b) bs' >> >> foldl does not seem to cover this. Dylan Thurston wrote: On Nov 20, 2004 > An alternative is > > foldlWhile f p a bs = last $ takeWhile p $ scanl f a bs > Yes. Thank you. Inspecting Prelude, we find out that scanl expresses, mainly, the thing. ----------------- Serge Mechveliani mechvel(a)botik.ru

2 1

Predicates in HaXml
by Tom Spencer 21 Nov '04

21 Nov '04

Hi there, In XSLT there is an XPath function that will let you select a particular node in the current context, for example; <xsl:value-of select="team[1] "/> in Michael Kay's article http://www-106.ibm.com/developerworks/xml/library/x-xslt/?article=xr This selects the first team element in the current context. Is there a work around to get similar functionality from the HaXml library? Many Thanks Tom Spencer

2 2

Re: [Haskell-cafe] foldlWhile
by dpt＠bostoncoop.net 20 Nov '04

20 Nov '04

On Sat, Nov 20, 2004 at 03:48:23PM +0000, Jorge Adriano Aires wrote: > > On Sat, Nov 20, 2004 at 12:47:58PM +0300, Serge D. Mechveliani wrote: > > > foldlWhile :: (a -> b -> a) -> (a -> Bool) -> a -> [b] -> a > > > foldlWhile f p a bs = > > > case > > > (bs, p a) > > > of > > > ([], _ ) -> a > > > (_, False) -> a > > > (b:bs', _ ) -> foldlWhile f p (f a b) bs' > > > > Why not just > > foldlWhile f p a bs = takeWhile p $ foldl f a bs > > Quite different. The former stops a foldl when the accumulating parameter no > longer satisfies p, the later assumes the accumulating parameter of the foldl > is a list, and takes the portion of the list that does satisfy p. Yes, this was a mistake. > The following is closer to the original, but doesn't work when the whole list > is folded (i.e., p always satisfied): > foldlWhile f p a = head . dropWhile p . scanl f a Serge's version returns the last 'a' that satisfies 'p', while yours returns the first 'a' that does not satisfy 'p'. This should be an equivalent version: foldlWhile f p a = tail . takeWhile p . scanl f a But what about the version with Maybe? There ought to be a concise way to write that too. Peace, Dylan

2 1

No need for integer literals
by Henning Thielemann 19 Nov '04

19 Nov '04

In addition to Paul Hudak's "The Haskell School of Expression", Appendix A "Built-in types are not special" I want to note that there is also hardly a need for integer literals. :-] module Digits where infixl 9 # (#) :: a -> (a -> b) -> b x # f = f x int :: Num a => a int = 0 d0, d1, d2, d3, d4, d5, d6, d7, d8, d9 :: (Enum a, Num a) => a -> a d0 n = n+n+n+n+n+n+n+n+n+n d1 = succ . d0 d2 = succ . d1 d3 = succ . d2 d4 = succ . d3 d5 = succ . d4 d6 = succ . d5 d7 = succ . d6 d8 = succ . d7 d9 = succ . d8 test :: (Enum a, Num a) => a test = int#d1#d4#d2#d8#d5#d7 * int#d2#d1

1 0