February 2001 - Haskell-Cafe

Re: Primitive types and Prelude shenanigans
by Ketil Malde 22 Feb '01

22 Feb '01

qrczak(a)knm.org.pl (Marcin 'Qrczak' Kowalczyk) writes: > 'negate' defined, as it's obviously meaningless for them. We can put > 'fromInteger' in some class and 'negate' in its subclass, and make > only the former instance for natural numbers. Nitpick: not necessarily its subclass, either. We can probably imagine types where negate makes sense, but fromInteger does not, as well as vice versa. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

making a Set
by Tom Pledger 21 Feb '01

21 Feb '01

(moved to haskell-cafe) G Murali writes: | hi there, | | I'm tryng to get my concepts right here.. can you please help in | defining a funtion like | | makeSet :: (a->Bool)->Set a | | I understand that we need a new type Set like | data Set a = Set (a->Bool) what puzzles me is how to apply the funtion | to all elements belonging to type a. What other operations do you need to implement for "Set a"? Is there anything that can't be expressed in terms of those set membership functions you already have?

1 0

RE: Primitive types and Prelude shenanigans
by Simon Peyton-Jones 21 Feb '01

21 Feb '01

I don't mind doing this, but can someone first give a brief justification about why it's a good idea, independent of the discussion that has taken place on this list? I'd like to add such an explanation to the code. Simon | -----Original Message----- | From: qrczak(a)knm.org.pl [mailto:qrczak@knm.org.pl] | Sent: 16 February 2001 17:42 | To: haskell-cafe(a)haskell.org | Subject: Re: Primitive types and Prelude shenanigans | | | Thu, 15 Feb 2001 20:56:20 -0800, William Lee Irwin III | <wli(a)holomorphy.com> pisze: | | > literal "5" gets mapped to (fromPositiveInteger 5) | > literal "-9" gets mapped to (fromNonZeroInteger -9) | | Note that when a discussed generic Prelude replacement | framework is done, and ghc's rules are changed to expand -9 to | negate (fromInteger 9) instead of fromInteger (-9), then you don't | need uglification of the fromInteger function to be able to define | types with only nonnegative numeric values. Just define your negate | in an appropriate class, different from the fromInteger's class. | | -- | __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ | \__/ | ^^ SYGNATURA ZASTEPCZA | QRCZAK | | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe |

3 4

RE: newbie: running a state transformer in context of a state rea der
by Konst Sushenko 21 Feb '01

21 Feb '01

Marcin, thanks for your help. to implement the lift functionality i added these well known definitions: class (Monad m, Monad (t m)) => TransMonad t m where lift :: m a -> t m a instance (Monad m, Monad (State s m)) => TransMonad (State s) m where lift m = ST (\s -> m >>= (\a -> return (a,s))) but my lookahead function lookahead p = do { s <- fetch ; lift (evalState p s) } is typed as lookahead :: State MyState Maybe a -> State MyState Maybe (a,MyState) but i need lookahead :: State MyState Maybe a -> State MyState Maybe a apparently, the (>>=) and return used in the definition of lift above are for the monad (State s m), and not monad m... everything works if i do not use the TransMonad class, but define lift manually as: lift :: Parser a -> Parser a lift m = ST (\s -> unST m s >>= (\(a,_) -> return (a,s))) but this looks like a special case of the lift above, except the right hand side of 'bind' is executed in the right context. i am still missing something konst -----Original Message----- From: Marcin 'Qrczak' Kowalczyk [mailto:qrczak@knm.org.pl] Sent: Tuesday, February 20, 2001 10:17 AM To: haskell-cafe(a)haskell.org Subject: Re: newbie: running a state transformer in context of a state reader Mon, 19 Feb 2001 18:07:17 -0800, Konst Sushenko <konsu(a)microsoft.com> pisze: > now i am curious if it is possible to run the given parser (state > transformer) in a context of a state reader somehow, so as the state > gets preserved automatically. something that would let me omit the > calls to fetch and set methods. It should be possible to do something like this: lookahead:: Parser a -> Parser a lookahead p = do { s <- fetch ; lift (evalState p s) } where evalState :: Monad m => State s m a -> s -> m a lift :: Monad m => m a -> State s m a are functions which should be available or implementable in a monad transformer framework. I don't have the Hutton/Meijer's paper at hand so I don't know if they provided them and under which names. Such functions are provided e.g. in the framework provided with ghc (by Andy Gill, inspired by Mark P Jones' paper "Functional Programming with Overloading and Higher-Order Polymorphism"). This definition of lookahead uses a separate state transformer thread instead of making changes in place and undoing them later. I don't think that it could make sense to convert a state transformer to a state reader by replacing its internals, because p does want to transform the state locally; a value of type Parser a represents a state transformation. The changes must be isolated from the main parser, but they must happen in some context. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTEPCZA QRCZAK _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

RE: Just for your fun and horror
by Manuel M. T. Chakravarty 20 Feb '01

20 Feb '01

Jon Cast <jcast(a)ou.edu> wrote, > Manuel M. T. Chakravarty writes: > > So, I guess, I have to extend my example to > > > > bar x = x + 42 > > > > I don't know if this counts, but gcc allows: > > int bar(int x)__attribute__(const) > { > return(x + 42); > } > > which is the exact C analogue of the Haskell syntax. Sorry, but I would say that it doesn't count as it is a compiler specific extension :-) Nevertheless, a good point. > The majority of `C > functions', I believe, (and especially in well-written code) are intended to > be true functions, not IO monads. They modify the state for > efficiency/ignorance reasons, not because of a conscious decision. Yes and no. I agree that they are often intended to be true functions. However, it is not only efficiency and ignorance which forces side effects on the C programmer. Restrictions of the language like the lack of call-by-reference arguments and (true) multi-valued returns force the use of pointers upon the programmer. Anyway, I don't want to do C bashing here - although, on this list, I might get away with it ;-) Cheers, Manuel

2 1

Re: Just for your fun and horror
by jhf＠lanl.gov 20 Feb '01

20 Feb '01

On 16-Feb-2001 Matthias Felleisen wrote: > > Because imperative languages have named one half of the denotation (the > value return) and not all of it for a long long long time. It's too late > for Haskell to change that. -- Matthias Well now, if I am to understand what a return statement in C does, I must realize not only that it may return a value to a calling routine, but also that it preserves the store. If it allowed the store to vanish, it wouldn't be very useful, would it? So I don't see how it's reasonable to assert that "return" means only one of these two things to a C programmer. Cheers, --Joe Joseph H. Fasel, Ph.D. email: jhf(a)lanl.gov Technology Modeling and Analysis phone: +1 505 667 7158 University of California fax: +1 505 667 2960 Los Alamos National Laboratory post: TSA-7 MS F609; Los Alamos, NM 87545

4 5

newbie: running a state transformer in context of a state reader
by Konst Sushenko 20 Feb '01

20 Feb '01

hello, i have a parser which is a state transformer monad, and i need to implement a lookahead function, which applies a given parser but does not change the parser state. so i wrote a function which reads the state, applies the parser and restores the state (the State monad is derived from the paper "Monadic parser combinators" by Hutton/Meijer): type Parser a = State String Maybe a lookahead :: Parser a -> Parser a lookahead p = do { s <- fetch ; x <- p ; set s ; return x } now i am curious if it is possible to run the given parser (state transformer) in a context of a state reader somehow, so as the state gets preserved automatically. something that would let me omit the calls to fetch and set methods. i would appreciate any advise thanks konst

2 1

RE: Typing units correctly
by Andrew Kennedy 19 Feb '01

19 Feb '01

First, I think there's been a misunderstanding. I was referring to the poster ("Christoph Grein") of http://www.adapower.com/lang/dimension.html when I said that "he doesn't know what he's talking about". I've not been following the haskell cafe thread very closely, but from what I've seen your (Dylan's) posts are well-informed. Sorry if there was any confusion. As you suspect, negative exponents are necessary. How else would you give a polymorphic type to \ x -> 1.0/x ? However, because of the equivalence on type schemes that's not just alpha-conversion, many types can be rewritten to avoid negative exponents, though I don't think that this is particularly desirable. For example the type of division can be written / :: Real (u.v) -> Real u -> Real v or / :: Real u -> Real v -> Real (u.v^-1) where u and v are "unit" variables. In fact, I have since solved the simplification problem mentioned in my ESOP paper, and it would assign the second of these two (equivalent) types, as it works from left to right in the type. I guess it does boil down to choosing a nice basis; more precisely it corresponds to the Hermite Normal Form from the theory of integer matrices (more generally: modules over commutative rings). For more detail see my thesis, available from http://research.microsoft.com/users/akenn/papers/index.html By the way, type system pathologists might be interested to know that the algorithm described in ESOP'94 doesn't actually work without an additional step in the rule for let (he says shamefacedly). Again all this is described in my thesis - but for a clearer explanation of this issue you might want to take a look at my technical report "Type Inference and Equational Theories". Which brings me to your last point: some more general system that subsumes the rather specific dimension/unit types system. There's been some nice work by Martin Sulzmann et al on constraint based systems which can express dimensions. See http://www.cs.mu.oz.au/~sulzmann/ for more details. To my taste, though, unless you want to express all sorts of other stuff in the type system, the equational-unification-based approach that I described in ESOP is simpler, even with the fix for let. I've been promising for years that I'd write up a journal-quality (and correct!) version of my ESOP paper including all the relevant material from my thesis. As I have now gone so far as to promise my boss that I'll do such a thing, perhaps it will happen :-) - Andrew. > -----Original Message----- > From: Dylan Thurston [mailto:dpt@math.harvard.edu] > Sent: Wednesday, February 14, 2001 7:15 PM > To: Andrew Kennedy; haskell-cafe(a)haskell.org > Subject: Re: Typing units correctly > > > On Wed, Feb 14, 2001 at 08:10:39AM -0800, Andrew Kennedy wrote: > > To be frank, the poster that you cite doesn't know what he's talking > > about. He makes two elementary mistakes: > > Quite right, I didn't know what I was talking about. I still don't. > But I do hope to learn. > > > (a) attempting to encode dimension/unit checking in an existing type > > system; > > We're probably thinking about different contexts, but please see the > attached file (below) for a partial solution. I used Hugs' dependent > types to get type inference. This makes me uneasy, because I know that > Hugs' instance checking is, in general, not decidable; I don't know if > the fragment I use is decidable. You can remove the dependent types, > but then you need to type all the results, etc., explicitly. This > version doesn't handle negative exponents; perhaps what you say here: > > > As others have pointed out, (a) doesn't work because the algebra of > > units of measure is not free - units form an Abelian group (if > > integer exponents are used) or a vector space over the rationals (if > > rational exponents are used) and so it's not possible to do > > unit-checking by equality-on-syntax or unit-inference by ordinary > > syntactic unification. ... > > is that I won't be able to do it? > > Note that I didn't write it out, but this version can accomodate > multiple units of measure. > > > (b) not appreciating the need for parametric polymorphism over > > dimensions/units. > > ... Furthermore, parametric polymorphism is > > essential for code reuse - one can't even write a generic squaring > > function (say) without it. > > I'm not sure what you're getting at here; I can easily write a > squaring function in the version I wrote. It uses ad-hoc polymorphism > rather than parametric polymorphism. It also gives much uglier > types; e.g., the example from your paper > f (x,y,z) = x*x + y*y*y + z*z*z*z*z > gets some horribly ugly context: > f :: (Additive a, Mul b c d, Mul c c e, Mul e c b, Mul d c a, > Mul f f a, Mul g h a, Mul h h g) => (f,h,c) -> a > > Not that I recommend this solution, mind you. I think language > support would be much better. But specific language support for units > rubs me the wrong way: I'd much rather see a general notion of types > with integer parameters, which you're allowed to add. This would be > useful in any number of places. Is this what you're suggesting below? > > > To turn to the original question, I did once give a moment's thought > > to the combination of type classes and types for units-of-measure. I > > don't think there's any particular problem: units (or dimensions) > > are a new "sort" or "kind", just as "row" is in various proposals > > for record polymorphism in Haskell. As long as this is tracked > > through the type system, everything should work out fine. Of course, > > I may have missed something, in which case I'd be very interested to > > know about it. > > Incidentally, I went and read your paper just now. Very interesting. > You mentioned one problem came up that sounds interesting: to give a > nice member of the equivalence class of the principal type. This > boils down to picking a nice basis for a free Abelian group with a few > distinguished elements. Has any progress been made on that? > > Best, > Dylan Thurston >

2 1

Re: framework for composing monads?
by Elke Kasimir 19 Feb '01

19 Feb '01

(Moving to haskell cafe...) On 18-Feb-2001 Manuel M. T. Chakravarty wrote: >> It is even acceptable for me to manage the state in C - >> independent of the API design - but then some time there >> will be the question: Why do I always say that that Haskell >> is the better programming language, when I'm >> really doing all the tricky stuff in C?... > > Sure - therefore, I proposed to use `IORef's rather than C > routines. Thanks for the hint! I took a look at them and now have some questions: a) It is clear that I need some C-link to access the cli/odbc lib. Up to now I planned to use Haskell Direct for this. Except of this, I want to stick to Haskell 98 and seek for maximal portability. Practically, this raises the question of wether nhc and hbc support hslibs or else I can provide a substitute for IORef's for these compilers. Can someone give me hint? b) What I finally need is "hidden state". My first attempt to get one using IORefs is: > import IOExts > > state :: IORef Int > state = unsafePerformIO $ newIORef 0 > > main = seq state $ do > writeIORef state 1 > currstate <- readIORef state > putStr (show currstate) Is this the right way? Cheers, Elke --- "If you have nothing to say, don't do it here..." Elke Kasimir Skalitzer Str. 79 10997 Berlin (Germany) fon: +49 (030) 612 852 16 mail: elke.kasimir(a)catmint.de> see: <http://www.catmint.de/elke> for pgp public key see: <http://www.catmint.de/elke/pgp_signature.html>

3 2

Re: Just for your fun and horror
by Jerzy Karczmarczuk 19 Feb '01

19 Feb '01

Dear all, at haskell-café & plt-scheme. 1. THANK YOU VERY MUCH for enlightening comments about the terminology, student psychology, etc. I will get back to it in a second, for the moment I ask you very politely: survey the adressee list if you "reply-all". For people subscribing both Haskell and Scheme forums means 4 copies of your message, if you send the messages simultaneously to the private address of the previous author...!. I thought that a cross posting might have some merits, and I see now the nuisance. My deep apologies. 2. People suggest that the word return has been badly chosen. I have no strong opinion, I begin to agree... we had unit, result, people propose liftM, compute, deliver, etc. I wonder why return stuck? Just because it exists elsewhere? I believe not, it has some appeal, as Joe Fasel acknowledges. C. Reinke writes: > One way to look at the problem is that some of your students have > concrete experience with `return' in different contexts, and that > Haskell tries to make different things look similar here. You say > "we worked with monads for several weeks" but, you being yourself, > this was probably at a fairly abstract and general level, right? No, not exactly. Being myself, just the opposite. There is *NO* more abstraction in my course than in Wadler's "Essence...". * I begin with a silly functional evaluator of a tree representing an arithmetic expression. * We recognize together with the students that a program may fail, and we introduce Maybe. They see thus a simple monadic generali- sation and the first non-trivial instance of return. We try to implement (in a sketchy way) a tracing generalisation as well. * They have parallelly a course of Prolog, so we play con mucho gusto with a few "non-deterministic" algorithms, such as standard combinatoric exercices : the generation of permutations, of the powerset, etc. On average the students seem to understand the idea and the implementation, and *mind you*: while writing their exercises <<a vista>> they duly corrected themselves when they were tempted to write "z" instead of "return z". ([] =-> [[]]). * We worked for a reasonable period with monadic parsers. The comment above is valid. Semantically they accepted the difference between "z" and "return z". I couldn't foresee any surprises. * They had to write a serious program in Haskell, so I gave them an introduction to Haskell I/O. They couldn't escape from *practical* Monads (although some of my students "perverted" [with my approval] the idea of writing a *syntactic* converter to Scheme, realizing it not in Haskell but in Scheme...) I spoke of course about types, but not simultaneously. We took advantage of the type inference, and the *type* of return has not been discussed explicitly sufficiently early. This is - I believe - my main, fundamental pedagogical fault! Yes Joe, I think this has been my own <<pons asinorum>>. If my compilation course survives all this affair (not obvious) I will try to remember Jón Fairbarn's suggestion (repeated by Manuel Chakravarty), and to discuss thoroughly the status of "C" imperative concepts, in order to prevent misunderstandings. C. Reinke again: > Unless you're one of Asimov's technicians of eternity, it is a bit > difficult to change the history of programming languages, and assuming > that the students pay for the opportunity to learn, you can't really > fire them either.. Hm. We are all Technicians able to change the past, but since we do not live outside the System, we do it usually in the Orwellian way: we change the INTERPRETATION of the past. Things which were good (structural top-down programming) become bad (inadapted to object approach). Strong typing? A straitjacket for some, a salvation for the other. Scheme'ists add OO layers in order to facilitate the code reusing, and this smuggles in some typing. Dynamic typing in static languages became a folkloric, never-ending issue... The history of languages is full of "second thoughts". Who will first write a paper with a Wadlerian style [[but taken from earlier literature]] title: "Monads considered harmful" "Return should NOT return its argument" etc.? And in France students don't pay for the opportunity to learn. Regards. Jerzy Karczmarczuk Caen, France

1 0