- Haskell - Haskell.org

cross product of lists
by jefu 08 May '01

08 May '01

This is not a class assignment - indeed I'm a professor who has used haskell in classes (and is currently being fired for having done so - it seems teaching anything other than c++ is questionable). I'd like to have a program that will take a description of a regular language and produce a list of strings in that language in order of size. If the lists are infinite (a* and the like) things work fine, but when the lists are finite, things dont work. I have two programs that I've tried to use and both have been hacked a bit in my process of experimentation so they're not the nicely honed final product I'd like to have. The first is based on my original ideas but with some attempt to cajole the finite/infinite list problem - it still seems to me that this would be a good way to go if possible, but I'm stumped. It is at : http://cs.eou.edu/jefu/reglang.hs The second is built on the idea of remembering if a list is finite or infinite and handling it accordingly. This one manages to segfault hugs and ghci also just quits about half the time (linux, redhat 7). This one is at : http://cs.eou.edu/jefu/nreglang.hs Any suggestions ? jefu -- jeff putnam -- jefu(a)eou.edu -- http://cs.eou.edu/~jefu

2 1

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

08 May '01

| > 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). | | Really? I disagree. Making pattern type sygnatures perform | unification of the variable with the supplied signature is | useful for resolving ambiguities, and backward-compatible | (valid programs will remain valid), and doesn't allow | "unwanted generality" to cause trouble (when an expression | has a more general type than needed). I was meaning in the translation into System F of the program. Under my proposal (= yours) if one writes f (x::(a,b)) = e then f is forced to have type f :: (T1, T2) -> ... for some T1, T2. In saying that let-type can't pattern-match against a type variable c, I'm just saying that f cannot have type f :: forall c. c -> .... I think I just didn't express myself well enough. Simon

2 1

making plurals
by Gian 08 May '01

08 May '01

i was wandering if you would be able to show me how to implement a function which converts a list of words into the plurals say maybe to convert "shelf" into "shelves". I thought maybe with using some kind of recursion, tupples and the prelude function isSuffixOf. but im not sure how to implement it can you help.

2 1

Re: question on type classes
by Ashley Yakeley 08 May '01

08 May '01

At 2001-05-08 03:07, Markus Lauer wrote: >Hugs sais ERROR Test.hs:20 - syntax error in instance head (constructor > expected) Invoke as 'hugs -98' to switch on extensions. Hugs will then complain of overlapping instances: instance FooList Char instance Foo a => FooList a Yes, I know Char is not an instance of Foo. See the "Anomalous Class Fundep Inference" thread. -- Ashley Yakeley, Seattle WA

1 0

question on type classes
by Markus Lauer 08 May '01

08 May '01

Is it possible in Haskell to define a type class like Show, which has a generic implementation for Lists and a special one for [Char], but (in contrast to Show) where Char is not in this Class I'd like to have something like the following, but this example doesn't work: ------------------------------------------- module Test where class Foo a where foo :: a -> a .... .... instance FooList a => Foo [a] where foo lst = fooList lst .... .... class FooList a where fooList :: [a] -> [a] .... .... genericImpl :: Foo a => [a] -> [a] genericImpl = ... specialImpl :: String -> String specialImpl = .... instance FooList Char where fooList s = specialImpl s ..... instance Foo a => FooList a where fooList lst = genericImpl lst ..... --------------------------------------------- Hugs sais ERROR Test.hs:20 - syntax error in instance head (constructor expected) ghc (5.00) sais Test.hs:20: Illegal instance declaration for `FooList a' (the instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) is there a better way, than to copy the instance declaration of FooList for every a in that is in class Foo? Thanks for any hint, Markus -- Markus Lauer <Markus.Lauer(a)lauer-edv.com>

1 0

FW: Scoped type variables
by Simon Peyton-Jones 07 May '01

07 May '01

This is the message that Marcin referred to, proposing a change in the semantics of scoped type variables. I may just go ahead and implement it in GHC. (The implementation is easy: delete a couple of lines; and I guess the same is so for Hugs. The question is whether it's a desirable change.) Simon -----Original Message----- From: Simon Peyton-Jones Sent: 08 February 2001 02:32 Cc: Simon Peyton-Jones; qrczak(a)knm.org.pl Subject: Scoped type variables Dear Huggy people | But for pattern and result type signatures changing the rules makes | sense. | f (x::a) = ... | does not mean that x has type "forall a. a" anyway. It should actually | only give the type a name, no matter what it is. | | Similarly, | f (x :: (a,b)) = ... | should unify the appropriate type variable with (,), and give names to | monomorphic arguments of (,) used in the call we are in. I must say that I agree with Marcin's point. When we write f x = e we mean that x is a name for whatever argument f is given. Marcin argues that the same should apply for f (x :: (a,b)) = e Namely, that x is a name for the argument, a is a name for the type of the fst of x, and slly b. Arguments in favour: - It's more like term-variable pattern matching - In the present system, saying (x::a) doesn't mean x's type is really universally quantified -- it may have a type constraint. And there's really a continuum between saying forall a. C a => t[a] and t[Int] because the Int amounts to a rather strong constraint on a. Indeed, when we have functional dependencies, forall a. C Int a => t[a] may indeed be the same as C Int Int => t[Int] - It's simpler; less to explain to the programmer (quite a bit of the GHC documentation on this stuff is to explain what about the universal quantification) Arguments against - It's not what GHC and Hugs do now. It would be an easy change to make, but I'd prefer it if GHC and Hugs stayed in sync over this (modulo release schedules), so I'd be interested in your views. Simon Someone (Jeff?) wrote: | Could you clarify what you are proposing? Is it | something like "let me name that type `a' even tho I know | it's really something more specific"? (i.e. similar to the | current hugs extension, but without the "can't be more | specific than inferred" restriction) Exactly so. For example f (x::a) = let y::a = x+1 in h x y would be legal even if h :: Int -> Int -> Int The point is that 'a' simply names the type of x, even if that type isn't a type variable.

2 1

RE: User defined Ix instances potentially unsafe
by Simon Peyton-Jones 07 May '01

07 May '01

[Here's a possible Haskell 98 Library Ix "typo"] | > > An implementation is entitled to assume the following laws about | > > these operations: | > > | > > range (l,u) !! index (l,u) i == i -- when i is in range | > > inRange (l,u) i == i `elem` range (l,u) | > | > So my "bug" is only in my mind. Sorry for bothering everyone. | | I don't think it's quite as straight-forward as that. | Hugs and ghc may conform to the Library Report, but the | behaviour is still undesirable, and IMHO should be fixed. I rather agree with this. But I'm not sure what the fix is. In thinking about this I've realised that there's an assumption in the Ix interface that (*) map index (range (l,u)) = [0..rangeSize (l,u)-1] That is, index maps an index densely into the range 0..N where N is the size of the array. Without this assumption, an array implementation would need to store the Int bounds of the array as well as the ix bounds. I bet that no Haskell implementation does this. If this were not so, the implementation of rangeSize in Section 5.2 would be utterly wrong rangeSize b@(l,u) = index b h + 1 The constraint (*) also specifies that 'range' returns subscripts in increasing order of index. That seems reasonable, but perhaps less important. One could alternatively say (*a) index (l,u) l = 0 (*b) index (l,u) u = rangeSize (l,u) - 1 In the spirit of making minimal changes/additions to H98, perhaps (*a) and (*b) would be better. Any thoughts? Simon PS: none of this answers Matt's original question which I can rephrase thus: if a user provides implementations of index, range etc that do not obey the specified invariants, can that crash the system? I would rather the answer were 'no'. But that means the implementation would have to check the output of 'index' against the size of the array allocated from the supplied bounds. Which means that in the common case that 'index' also makes such a check there'd be two checks. Unless the compiler was clever enough to eliminate one of them, which isn't easy since one is at the 'ix' type and the other at 'Int'.

4 3

RE: Anomalous Class Fundep Inference
by Simon Peyton-Jones 07 May '01

07 May '01

There's a design space about how vigorous one is about checking for "unsatisfiable" instances when doing overlap things. It's quite a complicated design space that I don't fully understand, which is why GHC at least implements a conservative rule. For example, does one complain about overlap when the instance declarations are defined, or when they are used? Does one assume that new instances can be added "later"? and there is more I think. Simon | -----Original Message----- | From: Ashley Yakeley [mailto:ashley@semantic.org] | Sent: 05 May 2001 07:53 | To: Haskell List | Subject: RE: Anomalous Class Fundep Inference | | | At 2001-05-03 01:42, Simon Peyton-Jones wrote: | | >Quite right too! | | OK, I understand it a bit better now. This code does not compile: | -- | class X a | instance X Bool | instance (Num a) => X a | -- | Can someone explain why the two instances overlap, given that | Bool is not | an instance of Num? | | Would it be possible for Haskell to figure out this sort of | thing and not | complain about it, or would that lead to nasty problems? | | -- | Ashley Yakeley, Seattle WA | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

RE: Implict parameters and monomorphism
by Simon Peyton-Jones 06 May '01

06 May '01

Now that is a *really* amazing example. I had no idea that polymorphic recursion would do this. I withdraw my claim that a type signature can't change the answer. But I'm worried. Simon | -----Original Message----- | From: Lennart Augustsson [mailto:augustss@augustsson.net] | Sent: 03 May 2001 15:24 | To: C.Reinke(a)ukc.ac.uk; qrczak(a)knm.org.pl | Cc: haskell(a)haskell.org | Subject: Re: Implict parameters and monomorphism | | | OK, so since noone liked my original example here's another | one. It involves no defaulting and no classes in the funny | function definition. | | -- Here's the type signature that makes a difference. | --fun :: a -> Char | fun x = const (fun x) (fun True) | | fix f = let x = f x in x | | class C a where | m :: a -> String | | instance C Char where | m _ = "has signature" | | instance C Bool where | m _ = "no signature" | | main = putStrLn (m (fix fun)) | | | It is not at all surprising that you can write this. | Originally type signatures only allowed you to put a | signature that was | more specific. | Polymorhic recursion on the other hand allows you to make the | type more general by putting a type signature on a | definition. Combining these you can make the signature be | incomparable to the deduced type. Using the class system you | can then dispatch on the type and get different behaviour. | | -- Lennart | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

3 3

Haskell Simulator of Quantum Computer
by Jan Skibinski 05 May '01

05 May '01

Hoping to get some early feedback I am posting this very preliminary version: http://www.numeric-quest.com/haskell/QuantumComputer.html Jan

1 1