- Haskell - Haskell.org

RE: BAL paper available
by Conal Elliott 15 May '01

15 May '01

Small comment. Marcin wrote: > About program transformation possibility: I don't see how it would > be applied in practice. There is no use of associativity of (+) for > the compiler. It can do many optimizations, but it won't rewrite > x+(y+z) to (x+y)+z nor vice versa. Associativity and commutativity (AC) are not optimizations in themselves, but rather enable optimizations if you have an AC matcher in your rewriting system (as, for instance, in Mathematica). - Conal

1 0

Ix class
by Matt Harden 15 May '01

15 May '01

Hello, I am working on an Ix instance for one of my types and finding it rather restrictive. For me it would be useful to have rangeSize be defined in the Ix class (with a default definition of course), so that it can be overridden. Also, does anybody know why Ix derives from Ord? It seems to me this is an unnecessary limitation on the types that can be instances of Ix. I cannot think of a reason why the implementation of anything in the Ix or Array modules would require that every Ix be an Ord (with a minor exception -- see below). If an implementation is using a comparison on an Ix type, chances are it should be using inRange or comparing (index bnds x) with (index bnds y) instead. One change would have to be made in the Array module if Ord is removed from Ix: instance (Ix a, Eq b) => Eq (Array a b) where a == a' = assocs a == assocs a' instance (Ix a, Ord b) => Ord (Array a b) where a <= a' = assocs a <= assocs a' would become: instance (Ix a, Eq a, Eq b) => Eq (Array a b) where a == a' = assocs a == assocs a' instance (Ix a, Ord a, Ord b) => Ord (Array a b) where a <= a' = assocs a <= assocs a' As I said, I think this is a very minor issue. I believe that making these changes in the standard would not impact existing programs in any way. Could these changes be considered as a possible "typo" to be fixed in the Library Report? P.S. In case anybody's interested, here's why I want to override rangeSize: > newtype Honeycomb = Hx (Int,Int) deriving (Eq,Show,Ord) > > indexError = error "Index out of range" > > instance Ix Honeycomb where > range (Hx b1, Hx b2) = > [Hx x | x <- range (b1,b2), isHexIx x] > inRange (Hx b1, Hx b2) (Hx x) = > inRange (b1,b2) x && isHexIx x > index (Hx b1, Hx b2) (Hx x) = > let i = index (b1,b2) x in > if isHexIx x then i `div` 2 else indexError > > isHexIx :: (Int,Int) -> Bool > isHexIx (x,y) = x `mod` 2 == y `mod` 2 This implements a honeycomb or hexagonal tiling for a maze generating program. The honeycomb is superimposed on a grid such that only every other square is "active", corresponding to a particular hexagon in the honeycomb. It's similar to a checkers game, where only the dark squares are used. I would like _any_ pair of Ints to be an acceptable boundary for the honeycomb, not just the ones that represent valid indexes. For example, (Hx (0,0), Hx (15,12)) should be a valid set of bounds. The current definition of rangeSize makes this impossible, which is why I would like to override it. By the way, the Library Report does not explicitly say that the bounds have to both be valid indexes, though it does imply this with the sample definition of rangeSize. Thanks, Matt Harden

2 1

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 15 May '01

15 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 14 May '01

14 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