- Haskell - Haskell.org

deriving over renamed types
by Hal Daume III 03 Apr '02

03 Apr '02

Why can't I do this: > import FiniteMap > type FM = FiniteMap > instance (Show a, Show b) => Show (FiniteMap a b) where > show = show . fmToList > data X = X (FM Int Int) > deriving (Show) if I replace > type FM = FiniteMap with > type FM a b = FiniteMap a b it works fine. I wasn't aware there was (supposed to be) a difference between these two declarations? Is there? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

RE: ">>" and "do" notation
by Simon Peyton-Jones 03 Apr '02

03 Apr '02

| > I think the point that's being missed in this discussion | > is that a monad is a n *abstract* type, and sometimes the | > natural "equality" on the abstract type is not the same as | > equality on representations. ... If we can give >> a | more efficient | > implementation, which constructs a better representation | > than >>= does, that's fine, as long as the two | > representations "mean" the same thing. | | Point taken, but I remain unconvinced. What comes out of the | monad /isn't/ abstract; there's nothing to ensure that | subsequent use respects the abstraction. | | That's true, of course. But *should* we insist that the | programming language guarantee that abstractions are always | respected? i.e. equivalent representations are always treated | equivalently? This is an interesting discussion but from the point of view of H98 I'm interested in answering the following much narrower question: what should be the desugaring of do { e ; Q } The current Report uses (>>) for this, and (>>=) for the "p <- e" case. An alternative would be to use (>>=) for both. I take it for granted that (>>) stays as an operation of class Monad: several people have argued for this, and I have no intention of changing H98 in that respect. I take it for granted that if the Report says "use >>" then implementations should. So either GHC and Hugs have to change or the Report does. So the question remains: what would be best for programmers: A: the predictability that desugaring do-notation uses only (>>=) and return, or B: or the extra power of using (>>) for the no-patterns case? If there are Good Reasons for having (>>) in the class, as several have argued, then I guess we should go for (B). In that case the Report would stay unchanged, and the impls would have to change. I also thought that James's analogy of (-x) translating to (negate x) and not to (0-x) was a good one. I originally favoured (A) but I'm happy to go with (B). anyone disagree? Simon

1 0

Re: ">>" and "do" notation
by John Hughes 03 Apr '02

03 Apr '02

> I think the point that's being missed in this discussion > is that a monad is a n *abstract* type, and sometimes the > natural "equality" on the abstract type is not the same as > equality on representations. ... If we can give >> a more efficient > implementation, which constructs a better representation > than >>= does, that's fine, as long as the two > representations "mean" the same thing. Point taken, but I remain unconvinced. What comes out of the monad /isn't/ abstract; there's nothing to ensure that subsequent use respects the abstraction. That's true, of course. But *should* we insist that the programming language guarantee that abstractions are always respected? i.e. equivalent representations are always treated equivalently? We don't always in other contexts. To take an example, consider a bag datatype with a bagFold operator and an Eq instance that implements bag equality. Then xBag == yBag doesn't necessarily imply bagFold op z xBag == bagFold op z yBag We rely on the programmer to use bagFold properly, i.e. supply an AC op with unit z. If he doesn't, the abstraction is broken. > This is all perfectly respectable, and has to do with the > fact that Haskell i s a programming language, not > mathematics -- so we represent equivalence classe s by > values chosen from them. For the *language* to rule out > constructing different representations for "equivalent" > constructions, such as >> and >>=, would be unreasonable. Here's the problem. Your argument sounds very similar to the one against type checking. That /you/ can get it right doesn't encourage me to believe that J Random Hacker isn't going to abuse the facility. It's not as if you couldn't define >!= and >! for something that's nearly a monad, it would just stop you using the do notation, which is, I think fair, since Haskell provides no way of selecting the correct form of equality for do {_ <- A; B} == do {A; B}. Jón This is a much bigger cost than you make out. Making something into a monad allows not only the use of the do syntax, it allows the use of a large number of generic monad operations, the application of monad transformers, etc etc. It's a big deal. I agree there's an analogy here with type-checking here. Indeed, there's a tradeoff where typechecking is concerned too: we give up some flexibility for greater safety. We accept that nowadays, because the flexibility we give up with Hindley-Milner typing is not so great, and the gain in safety is considerable. But would you argue that we should prohibit programs which potentially break an abstraction? I.e. prohibit bagFold, or alternatively allow it only for operators which the compiler can *decide* are AC? Would you want to prohibit monad instances which the compiler cannot decide satisfy the monad laws? I know you would want to prohibit monad instances where the compiler cannot decide that >> and >>= are properly related. The trouble is that prohibiting bagFold, separate definitions of >>, etc. altogether is quite a big cost: such things are very useful! Yet we lack the analogue of the Hindley-Milner type system -- a way for the compiler to *decide* that a monad instance, an ADT definition, or whatever, is OK, which is *proven* sufficiently flexible to handle almost all practical cases. In its absence, the analogy with type-checking is not compelling. If all we had was a monomorphic type system, then I would be against imposing type-checking too. Perhaps there's an interesting research direction here for somebody... John

1 0

RE: handling errors in Happy
by Simon Marlow 03 Apr '02

03 Apr '02

> Is it possible to get the result of function happyError, in > the main module > of my program (which imports the module generated by Happy)? Sure. You need to use Happy's %monad feature, the documentation describes how to turn parse errors into something you can handle in the program: http://www.haskell.org/happy/doc/html/sec-monads.html#SEC-EXCEPTION Cheers, Simon

1 0

Haskell/Erlang Research Position
by Phil Trinder 03 Apr '02

03 Apr '02

Research Associate in Haskell/Erlang for Distributed Telecommunications �17,278-�26,229 p.a. Applications are invited for a three year Research Associate position at Heriot-Watt University to work with Dr Phil Trinder on an EPSRC funded project entitled "High-Level Techniques for Distributed Telecommunications Software". The project is a collaboration with Motorola UK Research Labs and aims to evaluate high-level distributed programming techniques for constructing realistic telecommunications software. Applications are welcomed from candidates with a doctorate or a very good first degree in Computing or cognate discipline; a successful candidate without a PhD will have the opportunity of registering for one. Applicants should have good written and verbal communication skills and be able to demonstrate a strong programming ability: experience with distribution and the Haskell or Erlang programming languages is desirable. Likewise a research background, and familiarity with the telecommunications sector are desirable. For application details please contact the Personnel Office, Heriot-Watt University, Edinburgh, EH14 4AS, tel/fax: 0131 451 3475 (24 hours) quoting Ref 66/02/J. The closing date is Friday 19th April 2002. Informal enquires can be directed to Phil Trinder tel: +44 131 451 3435, or e-mail: trinder(a)cee.hw.ac.uk. More details of the project and further particulars for the position can be found at: http://www.cee.hw.ac.uk/~dsg/telecoms/

1 0

Re: ">>" and "do" notation
by John Hughes 03 Apr '02

03 Apr '02

>If (as a human reader of a programme) I see > >do a <- thing1 > <expression> > >and I notice (perhaps after some modifications) that a is >not present in <expression>, then I /really/ don't want a >change to > >do thing1 > <expression> > >to change the meaning of the programme. I think the point that's being missed in this discussion is that a monad is an *abstract* type, and sometimes the natural "equality" on the abstract type is not the same as equality on representations. Of course, we want the left and right hand sides of the monad laws to have the same "meaning", and we want >> to "mean" >>= \_ ->, but this meaning is really up to the abstract equality, not the concrete one. If we can give >> a more efficient implementation, which constructs a better representation than >>= does, that's fine, as long as the two representations "mean" the same thing. To be specific, the application that kicked off this discussion was program generation. In this example, it's not important that >> and >>= generate the same *program text*, the important thing is that they generate equivalent programs. If >> can more easily generate a more efficient program, that's fine. There's another example in QuickCheck, where we use a monad Gen for random value generation -- Gen a is a generator for random values of type a. Gen does not satisfy the monad laws: for example, g and g >>= return will usually generate different values. But viewed as *probability distributions* (which is how we think of them), they are the same. "Morally", Gen is a monad. This is all perfectly respectable, and has to do with the fact that Haskell is a programming language, not mathematics -- so we represent equivalence classes by values chosen from them. For the *language* to rule out constructing different representations for "equivalent" constructions, such as >> and >>=, would be unreasonable. John Hughes

3 2

Re: sort inefficiency
by Serge D. Mechveliani 03 Apr '02

03 Apr '02

Glenn G. Chappell <ggchappell(a)yahoo.com> writes > I am wondering about a design decision in the List module. > > To wit: "sort", in both the H98 library report and the Hugs file > List.hs, is implemented using a quadratic sort (insertion sort). > > Using the name "sort" certainly suggests that this is a good function > to use for sorting. I would think it is pretty obvious that "sort" > should be implemented using an efficient algorithm. I am thinking > primarily of merge sort, which has O(n log n) worst case behavior, > is stable, and has an elegant and efficient functional implementation. > > Certainly insertion sort is good to have around, if one is sorting > data that is nearly sorted already, but I would say insertion sort > is clearly not the best choice (or even a good choice) for a general- > purpose sorting algorithm. > > Or am I missing something? The Standard library specifies only the map related to the name `sort'. This map can be described, for example, via sort-by-insertion program. And the algorithm choice is a matter of each particular implementation. Implementation has right to change the algorithm. For example, I tried once to argue with GHC for incorporating the mergeSort algorithm for `sort'. But they have some version of quickSort which is said faster on average and O(n^2) in the worst case. Disliking this n^2 hazard, I overload `sort' with my_sort. ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

handling errors in Happy
by Andre W B Furtado 03 Apr '02

03 Apr '02

Is it possible to get the result of function happyError, in the main module of my program (which imports the module generated by Happy)? Thanks a lot, -- Andre

1 0

JVM-Bridge Current Status
by Ashley Yakeley 03 Apr '02

03 Apr '02

1. Changes So Far The following changes have been checked into CVS since the 0.1 release: Native/ * MacOS X support * Beginnings of mingw32 support * New Sun 1.4 JVM * Now installs in /usr/lib/jvm-bridge/ * ExecuteFunction bindings now done at run-time Haskell/ * MacOS X support * 'Haskell' now a separate Autotools project installing in /usr/lib/jvm-bridge/ * New array region access functions * Correct array types in autogenerated class interfaces * Subtype parameters in autogenerated class interfaces * VMLayer 'env' parameter now implicit * Various changes in the BasicLayer * new native StartExecuteFunction function called by getExecuteFunctionClass, defineCallbackClass I recommend using GHC 5.02.2 or later. Possibly it might work with 5.02. 2. Current Work MacOS X callback support is buggy, and I'm currently working on it. It might a problem with ghc-5.03-13032002-MacOSX (foreign export dynamic), or it might be a bug in JVM-Bridge. Thomas Pasch <extern.thomas.pasch(a)volkswagen.de> has done some work on getting JVM-Bridge to compile under mingw32. I have integrated some of his patches. I do not have a Windows machine myself. I would like to do a 0.2 release, say when both examples work on all three platforms. 3. I have created a new mailing list: <http://lists.sourceforge.net/lists/listinfo/jvm-bridge-devel> If you are using JVM-Bridge I encourage you to subscribe. -- Ashley Yakeley, Seattle WA

1 0

Inefficient sort implementation
by Glenn G. Chappell 02 Apr '02

02 Apr '02

I am wondering about a design decision in the List module. To wit: "sort", in both the H98 library report and the Hugs file List.hs, is implemented using a quadratic sort (insertion sort). Using the name "sort" certainly suggests that this is a good function to use for sorting. I would think it is pretty obvious that "sort" should be implemented using an efficient algorithm. I am thinking primarily of merge sort, which has O(n log n) worst case behavior, is stable, and has an elegant and efficient functional implementation. Certainly insertion sort is good to have around, if one is sorting data that is nearly sorted already, but I would say insertion sort is clearly not the best choice (or even a good choice) for a general- purpose sorting algorithm. Or am I missing something? ===== Glenn G. Chappell <>< ggchappell(a)yahoo.com Dept. of Mathematical Sciences * Ofc: (907) 474-5736 University of Alaska Fairbanks * Fax: (907) 474-5394 __________________________________________________ Do You Yahoo!? Yahoo! Tax Center - online filing with TurboTax http://http://taxes.yahoo.com/

1 0