- Haskell-Cafe - Haskell.org

Re: Inferring from context declarations
by D. Tweed 22 Feb '01

22 Feb '01

George Russell wrote: > > (3) Simon Peyton Jones' comments about dictionary passing are a red herring, > since they assume a particular form of compiler. Various (MLj, MLton) > ML compilers already inline out all polymorphism. Some C++ compilers/linkers > do it in a rather crude way as well, for templates. If you can do it, > you can forget about dictionary passing. [Standard disclaimer: I write prototype code that's never `finished' to ever-changing specs in a university environment; other people probably view things differently.] I'm not sure I'd agree about this. Note that there's two levels, inlining polymorphic functions at the call site and `instantiating polymorphic functions at each usage type' without doing the inlining. C++ compilers have to at least do the second because of the prevailing philosophy of what templates are (i.e., that they're safer function-macros). Some of the time this is what's wanted, but sometimes it imposes annoying compilation issues (the source code of the polymorphic function has to be available everytime you want to use the function on a new class, even if its not time critical, which isn't the case for Haskell). I also often write/generate very large polymorphic functions that in an ideal world (where compilers are can do _serious, serious_ magic) I'd prefer to work using something similar to a dictionary passing implementation. I'd argue that keeping flexibility about polymorphic function implementation (which assumes some default but can be overridden by the programmer) in Haskell compilers is a Good Thing. Given that, unless computing hardware really revolutionises, the `speed/memory' profile of todays desktop PC is going to recurr in wearable computers/PDAs/etc I believe that in 20 years time we'll still be figuring out the same trade-offs, and so need to keep flexibility. ___cheers,_dave________________________________________________________ www.cs.bris.ac.uk/~tweed/pi.htm|tweed's law: however many computers email: tweed(a)cs.bris.ac.uk | you have, half your time is spent work tel: (0117) 954-5250 | waiting for compilations to finish.

2 2

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