- Haskell - Haskell.org

RE: Scoped type variables
by Simon Peyton-Jones 15 May '01

15 May '01

Hi Mark, Thanks for your reply. | | Arguments in favour: | | - It's more like term-variable pattern matching | | Term variables in a pattern are binding occurrences, but type | variables are not. Making the latter look more like the | former would appear to be a recipe for unnecessary confusion | given that that they are actually different. Why do you say "type variables are not"?. When I say f x = e I mean "inside e, use x as the name for whatever value is passed as argument to f". Under what Marcin proposes f (x::a) = e would mean "inside (type signatures in) e, use a as the name for whatever type is the type of the argument passed to f". When you say there's a good theoretical foundation (typed lambda calcului) I think you are imagining that when we say f (x::a) = e we are saying "There's a /\a as well as a \x::a in this definition". In which case it would certainly be wrong to allow f :: Int -> Int f (x::a) = e But I'm suggesting something different * Place the big lambdas wherever they would be now (i.e. not influenced by the position of (x::a) type signatures. * Explain the pattern type signatures as let-bindings for types. Thus we might translate f to system-F like this: f = \x::T -> let-type a = T in e I've use let-type here, but one could equally well say (/\a -> e) T. This (admittedly informal) translation works fine if T happens to be Int, for exampe; i.e. x's type is not universally quantified. In short, the pattern type signature is used solely to bind names to types, and not for universal quantification. I want to have a slightly more elaborate let-type, thus: g :: (Int,Bool) -> Int g (x::(a,b)) = e translates to g = \x::(Int,Bool) -> let-type (a,b) = (Int,Bool) in e But notice that the RHS of a pattern-matching let-type is statically guaranteed to have the right shape. So I don't allow let-type (a,b) = c in ... (where c is a type variable). So it's just syntactic sugar, like let-type itself, and I could equally well write g = \x::(Int,Bool) -> let-type a = Int; b = Bool in e OK, so there are two questions a) does that answer the question about the techincal foundation b) is it a good design from a software engineering point of view I hope the answer to (a) is yes, but I realise that opinions may differ about (b). I thought this might be of general enough interest to be worth continuing to cc the Haskell list. Simon

3 2

standard library. Reply
by S.D.Mechveliani 14 May '01

14 May '01

Ch. A. Herrmann <herrmann(a)infosun.fmi.uni-passau.de> writes > [..] > Anyway, an algebraic library is important: > it is nice that Haskell has the rational numbers but recently, it > appeared useful for me also to have the algebraic numbers, e.g., > to evaluate expressions containing roots exactly. The problem is > that I'm not an expert in this stuff and thus, be very glad if > such things are added by an expert. > > On the other hand, I'd like to add things like a linear equation solver > for a non-invertible system which may help to convince people that > Haskell provides more features than other programming languages do. The BAL library http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ provides such linear solver, as well as operations with roots. For example, the root of x^5 - x + 1 can be handled (in many respects) in BAL as only a residue of polynomials modulo this equation - a data like (Rse ...(x^5-x+1))). But BAL is not a standard library. And there is another point: > [..] for a non-invertible system which may help to convince people that > Haskell provides more features than other programming languages do. In any case, we have to distinguish between a standard library and an application. A standard library should be small. I think, for Haskell, it should be something that you mention now. But, for example, the true algebraic number theory algorithms are too complex, it is for the non-standard application writers. And if a language is good, there should come many special applications (non-standard ones). Haskell's www page does reveal some. Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
by cwitty＠newtonlabs.com 14 May '01

14 May '01

"Manuel M. T. Chakravarty" <chak(a)cse.unsw.edu.au> writes: > I didn't say that this works for any kind of parser > combinator, I merely said that it works Doitse's and mine. > Both implement SLL(1) parsers for which - as I am sure, you > know - there exists a decision procedure for testing > ambiguity. More precisely, whenever the library can build > the parse table, the grammar must be non-ambigious. As the > parse table construction is lazy, this covers only the > productions exercised in that particular run, which is why I > said that you need a "file involving all grammar constructs > of the language." Nothing magic here. Wow. Clearly I haven't spent enough time looking at your parser systems. I apologize for my incorrect assumptions and statements. Carl Witty

1 0

CA proposal by D.Thurston
by S.D.Mechveliani 14 May '01

14 May '01

I was said that there exists an algebraic library proposal for Haskell (version 0.02) dated by February (2001?), by Dylan Thurston. Who could, please, tell me where to download this document from? For I could not find it from http://haskell.org Thanks in advance for the help. ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2

permutations. Reply
by S.D.Mechveliani 14 May '01

14 May '01

Andy Fugard <andyfugard(a)eircom.net> writes > Hi all, > > I'm currently teaching myself a little Haskell. This morning I coded the > following, the main function of which, permutate, returns all the > permutations of a list. (Well it seems to at least!) > > [..] The BAL library implements several operations with permutations. In particular, it can list permutations by applying nextPermutation. You may look into the source and demonstration example: http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Permutations of a list
by Andy Fugard 14 May '01

14 May '01

Hi all, I'm currently teaching myself a little Haskell. This morning I coded the following, the main function of which, permutate, returns all the permutations of a list. (Well it seems to at least!) insertAt :: a -> Int -> [a] -> [a] insertAt x i xs | i < 0 || i > length xs = error "invalid position" | otherwise = front ++ x:back where (front,back) = splitAt i xs insertAtAll :: a -> (Int,Int) -> [a] -> [[a]] insertAtAll x (i,j) xs | i > j = error "PRE: i <= j" | i == j = [insertAt x i xs] | otherwise = (insertAt x i xs):(insertAtAll x (i+1,j) xs) buildPermList :: a -> [[a]] -> [[a]] buildPermList x xs | length xs == 0 = [] | otherwise = list ++ buildPermList x (tail xs) where list = insertAtAll x (0, length curr) curr; curr = head xs permutate :: [a] -> [[a]] permutate xs | length xs == 0 = [[]] | otherwise = buildPermList (last xs) (permutate (init xs)) and some test runs.... Main> permutate "" [""] Main> permutate "a" ["a"] Main> permutate "ab" ["ba","ab"] Main> permutate "abc" ["cba","bca","bac","cab","acb","abc"] My main question is really what facilities of the language I should be looking at to make this code more elegant! As you can see I currently know only the basics of currying, and some list operations. Also regarding the method of generating the permutations; is there a better way? The current is just "Method 1" from Knuth's TAOCP, volume 1 (3rd edition), p45-46. Thanks in advance, Andy -- [ Andy Fugard /'andi fju:ga:d/ ] [ Phone: +44 (0)7901 603075 ]

2 2

typing question
by Ben 13 May '01

13 May '01

Hello, I hope that a question here wont be too much of a bother. Yesterday I wrote a library for polynomial manipulation. Everything is fine except for the composition operator. Which I having problems with, probably trivial, but as I don't program in Haskell everyday a solution isn't clear. I have my polynomials defined as: newtype Polynomial a = Polynomial [a] deriving (Eq) with toPolynomial :: (Num a) => [a] -> Polynomial a toPolynomial x = Polynomial x fromPolynomial :: Polynomial a -> [a] fromPolynomial (Polynomial x) = x instance Show a => Show (Polynomial a) where instance Num a => Num (Polynomial a) where... and defined appropriately I also have a function, degree :: Polynomial a -> Int but to be more pointed my question is related to, (@@) :: (Num a) => Polynomial a -> a -> a f @@ g = applyrec (fromPolynomial f) g 0 where applyrec (f:fs) g m = f * g^m + applyrec fs g (m+1) applyrec [] _ _ = 0 This was originally written to evaluate f at value, ie n \mapsto f(n). But I realized that this should also work for overloading, as my Polynomials are Nums. In hugs the following works fine, t = Polynomial [1,2,3] @@ Polynomial [3,2,1] but I suspect that there is a type conversion happening for me which I should be aware of as something like the following doesn't work, [ f @@ g | f <- poly, g <- poly, f /= g ] where poly is a list of polynomials gives me, *** Expression : f @@ g *** Term : f *** Type : Polynomial Integer *** Does not match : Polynomial (Polynomial Integer) so my question boils down to, how do I tell hugs/Haskell that Polynomials over Polynomials of Integers are just Polynomials of Integers or at least that this kind of composition is ok? I am not on this mailing list so please CC me any responses. Thank you. Ben.

2 2

io monad question
by luc 13 May '01

13 May '01

i designed some basic functions, , mainly String -> [String], or similar with types, plus some more complex datatypes. Up to now; i was testing them on a basic database I was creating in the core main, "by hand". Then i added a basic parser with happy; and bingo; my test database is now loaded from a file... as IO String..; huh! after a second though; this makes sense, except that i have to change all the type of my functions; now IO String.. plus a few that just dont compile; and i cant understand why... my question: I had to change most of my type of the functions.as is propagated through the code. (i.e. f need g; that need h; etc...) to add IO. is that kind of propagation normal, or can i Stop it somewhere ? how? is that because my functions just uses string as type ? and not data (ie type relation =string; instead data Relation String) can i design a function that will do IO String-> String, or IO String -> Data X, that will stop that IO propagation , through my code ? how can i handle function when my database is not IO, then ? i suppose im not the first to ask. any link ? thread ? faq example would be welcomed...

2 1

ANNOUNCE: Happy 1.10 released
by Simon Marlow 13 May '01

13 May '01

ANNOUNCING Happy 1.10 - The LALR(1) Parser Generator for Haskell ----------------------------------------------------------------- I'm pleased to announce version 1.10 of Happy, the parser generator system for Haskell. Changes in this version, relative to version 1.10 (the previous full release): * bugfixes, and minor performance improvements, * most of the examples work again. Happy is available in source form, which can be compiled with GHC version 4.xx (4.08 or 5.00 recommended), and we also provide binaries for some architectures. The Happy homepage with links to the various distributions lives at: http://www.haskell.org/happy/ Please send any bug reports and comments to simonmar(a)microsoft.com.

4 4

Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
by cwitty＠newtonlabs.com 12 May '01

12 May '01

"Manuel M. T. Chakravarty" <chak(a)cse.unsw.edu.au> writes: > I don't think, the point is the test for non-ambiguity. At > least, Doitse's and my self-optimising parser combinator > library will detect that a grammar is ambigious when you > parse a sentence involving the ambiguous productions. So, > you can check that by parsing a file involving all grammar > constructs of the language. Sorry, doesn't work. Where do you get this "file involving all grammar constructs of the language"? If such an approach worked, you could use it to determine whether an arbitrary context-free grammar was ambiguous; but this problem is undecidable. Carl Witty

3 2