- Haskell - Haskell.org

System.Random
by Wolfgang Jeltsch 01 Mar '04

01 Mar '04

Hello, why is the Random module situated under System? Wouldn't something like Data be more adequate? Wolfgang

1 0

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Simon Peyton-Jones 01 Mar '04

01 Mar '04

| > In Haskell today, you can at least tell what value is bound to each | > identifier in the program, *without* first doing type checking. | | I'm afraid I'm confused. In the following code | | > data Z | > data S a | > | > class Card c where c2int:: c -> Int | > | > instance Card Z where c2int _ = 0 | > instance (Card c) => Card (S c) where c2int _ = 1 + c2int (undefined::c) | > | > foo = c2int (undefined::(S (S (S (S Z))))) | | how can one tell the value of foo without first doing the | typechecking? What I meant was that you can always tell what executable code a value is bound to, without type checking. 'foo' is bound to the code for 'c2int (undefined::(S (S (S (S Z)))))'. 'c2int' is bound to code that extracts a method from it's first argument (which is a dictionary for Card). In any higher-order language, a function might invoke one of its arguments f x g = g x but I still say that it's clear what code is executed when f is called! It's true that with type classes the value of one of the dictionary argument is dependent on type checking, which certainly muddies the waters. But at least the type of 'c2int' isn't affected by which method is chosen, which is the real difficulty I was pointing out Simon

1 0

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Simon Peyton-Jones 28 Feb '04

28 Feb '04

> The idea that I've been throwing around is to be able to define a > separate namespace for each type; a function can either belong in a > "global" (default) namespace, or belong in a particular type's > namespace. So, in the above example, instead of writing "addToFM fm > ...", we could instead associate an 'add' function with the FiniteMap > type, so we could write "fm.add ..." instead. Provided that fm's type > is monomorphic, it should be possible to call the 'correct' add > function; if we defined another 'add' function that's associated with Remember, too, that in OO languages the type of 'fm' is usually declared, in advance, by the programmer. In Haskell it isn't. That makes it much harder to figure out which 'add' function is going to be used. Which 'add' function is chosen depends on type type of 'fm'. But the add function that is chosen in turn influences the type of the other arguments. For example, in the call (fm.add foo), the type of 'foo' is influenced by the choice of 'add'. But the type of 'foo' might (by the magic of type inference) affect the type of 'fm'.... In Haskell today, you can at least tell what value is bound to each identifier in the program, *without* first doing type checking. And the binding story, all by itself, is somewhat complicated. The typing story is also (very) complicated. Winding the two into a single indissoluble whole would make it far more complicated still. My nose tells me that this way lies madness. But I've been wrong before. Simon

5 4

Re: Data.Set whishes
by Wolfgang Jeltsch 28 Feb '04

28 Feb '04

Am Montag, 16. Februar 2004 10:05 schrieb Ketil Malde: > Wolfgang Jeltsch <wolfgang(a)jeltsch.net> writes: > > * subsetOf :: Ord element => Set element -> Set element -> Bool > > (Isn't "isSubsetOf" a better name?) So is "isElementOf". I just said "subsetOf" to be consistent with "elementOf". Well, the naming in the Data.* modules should generally undergo some changes. > Would > > x `isSubsetOf` y = x `union` y == y > > do, or did you want something more efficient? It's unefficient if, e.g., the x sets are always very small but so are union, intersect etc. I think, at first a complexity of O(|x| + |y|) would be acceptable so that your definition would be fine. Maybe, the implementation of union, intersect etc. should be changed so that the complexity is more like O(min(|x|,|y|)). > -kzm Wolfgang

19 31

Regular Patterns (RE: [Haskell] regular expression syntax)
by Niklas Broberg 27 Feb '04

27 Feb '04

>Subject: [Haskell] regular expression syntax - perl ain't got nothin on >haskell Agreed, Perl certainly ain't got nothing on Haskell, but we could go even further than just imitating (although better than the original) Perl functionality. =) Hence: As a spin-off of another project [1], we found ourselves in need of a nice way of expressing regular expression matching in Haskell, and not only for strings. We came up with the idea of HaRP: Haskell Regular Patterns. We have implemented this as a pre-processor to ordinary Haskell and it works quite well. However it is something we are still working on, and if it hadn't been for this discussion on the list we would probably have waited a few weeks more before presenting it, but here goes: Simple pattern matching on concrete, fully specified lists can be done in Haskell as so: foo [Foo, Bar, Baz] = ... We propose an extension of this to regular pattern matching, example: foo [/ Foo Bar* Baz /] = ... The intuition of the above is that we get a match for any list that starts with a Foo, ends with a Baz, and has zero or more Bar in between. Regular patterns that can be used are: * - match zero or more + - match one or more ? - match zero or one a | b - match a or b (/ a b /) - match the sequence of a, then b (this is also implicit in the top level [/ ... /]). Applying the regular expressions on patterns gives some extra nice features. One is that the regular patterns are "type safe", i.e. they are not encoded in strings. Another is that identifiers can be named and bound inside regular patterns, examples: foo [/ _* a /] = ... => a is bound to the last element of the list foo [/ a@(/ _ _ /) _* /] = ... => a is bound to the list containing the first two elements foo [/ (/ a _ /)* /] = ... => a is bound to the list of the first, third, fifth etc elements of a list of even length Note that since we introduce bindings of identifiers inside what we call numerating patterns, i.e. patterns that imply an uncertain number of matches, identifiers are automatically bound to lists inside such patterns. We also introduce an explicit list-binding operator, @:, for accumulating items in lists as so: foo [/ (_ a@:(/ _ _ /))* /] = ... => a is bound to a list of lists (exactly what the elements will be is left as an exercise to the reader ;) The types of sub-patterns are as follows (a :: a, b :: b): a* => [a] a+ => [a] a? => Maybe a (/ ... /) => [e], where e is the type of the elements in the list matched, regardless of sub-patterns ( a | b ) => Either a b As more complete example using all the presented features: foo [/ _ a@1 b c@3* 4+ d@5? e@(/ f@:6 g /)* h@( 8 | (/ 9 i /) ) /] = (a,b,c,d,e,f,g,h,i) Assuming all the numerical literals are of type Int, foo will have the following type: foo :: [Int] -> (Int, Int, [Int], Maybe Int, [[Int]], [Int], [Int], Either Int [Int], [Int]) Examples of applying foo to some lists: ?> foo [0,1,2,3,4,5,6,7,8] (1, 2, [3], Just 5, [[6,7]], [6], [7], Left 8, []) ?> foo [0,1,2,3,3,3,4,6,0,6,1,6,2,9,10] (1,2,[3,3,3], Nothing, [[6,0],[6,1],[6,2]], [6,6,6], [0,1,2], Right [9,10], [10]) Discussion of each variable in detail: a :: Int - a binds to a single element at top level (top level meaning it is bound outside any numerating pattern). b :: Int - b binds to a single element at top level. c :: [Int] - c is bound to a zero-or-many pattern, and it will contain all the matches of the sub-pattern, in this case all matches of 3. d :: Maybe Int - d is bound to a zero-or-one pattern, and it will be Nothing in case of zero matches, and Just the match to the sub-pattern in case of a match, in this case 5. e :: [[Int]] - e is bound to a zero-or-more pattern, and will thus contain a list of all the matches of the sub-pattern. In this case the sub-pattern is a sequence, which has a list type, so the type of e is a list of lists. f :: [Int] - f is bound using the list-binding operator @:, so its type will always be a list of the type of the sub-pattern, regardless of the context it appears in. It will contain all matches of the sub-pattern (Note that a normal bind using @ would have been illegal here). At top level (and in ordinary pattern matching), the pattern foo is equivalent to foo@_, but inside numerating patterns the pattern foo is equivalent to foo@:_. (see discussion below) g :: [Int] - g is equivalent to g@:_ as mentioned above, so the same will hold for g as for f. h :: Either Int [Int] - h is bound to a choice pattern (or union pattern if you prefer), so it will be bound to the match of one of the two sub-patterns, annotated with Left or Right. In this case the left sub-pattern matches a single element of type Int, whereas the right sub-pattern matches a sequence of type [Int]. i :: [Int] - Since the choice pattern is numerating (each of the sub-patterns are matched zero or one times), i is equivalent to i@:_. For completeness, another example to show how sequences work: bar :: [Int] -> [Int] bar [/ 0 a@(/ 1* 2 (3|4) (/ 5 6 /) 7? /) /] = a In this case a will have the type [Int], since a sequence will always have the type [e] where e is the type of the elements of the list to match. So in this example, ?> bar [0,2,3,5,6] [2,3,5,6] ?> bar [0,1,1,1,2,4,5,6,7] [1,1,1,2,4,5,6,7] Hopefully that's enough examples, it should be fairly clear how it all works. =) Regarding @ vs @:, it would be fully possible to implement this just using @ and change its behavior depending on the context it appears in, much like we do with identifiers bound without using the explicit @ operator. We feel that doing so could lead to (even more) confusion regarding how variables are bound, and have therefore chosen to introduce the extra @: operator to make this differing behavior explicit. That identifiers bound without a @ or @: have differing semantics depending on context is unfortunate but unavoidable, and we feel that the added confusion is minor in this case. As we said at the beginning we have implemented this as a preprocessor to ordinary Haskell, but it still needs some more alpha-testing before we release it... we need to catch the big fish first. There are a number of open issues still, one is the choice of delimeter token. We have chosen to delimit patterns with just a whitespace, but using a comma might be better. The motivation for the current choice is that [/ a, b*, c /] lends the feeling that each pattern is an element of sorts, when in fact each pattern may represent any number of elements. Any input on this? Another open issue is greedy vs. non-greedy matching of * and +. The current implementation is greedy, but some voices were raised earlier on this list that non-greedy matching would be better as default. We envision a system where you can choose behavior by adding "flags" to the pattern, i.e. [g/ .... /] might indicate a greedy match etc. Strings are a special syntactic case of a list, and we are planning a special case of regular patterns for it, for instance [s/ "Hello " a* /] would be equal to [/ 'H' 'e' 'l' 'l' 'o' ' ' a* /], but this is not yet implemented. Of course, unfortunately, there is also a downside. Our preprocessor is implemented by translating regular patterns into code in a parser monad. Due to the way that matching is done, matching will always be "strict" in the sense that if you apply the function foo [/ a* /] = a to an infinite list, the call will loop forever. At this point we see no reasonable way around this, there may be some special cases we can catch but we see no overall solution to the problem. Another drawback, at least in our implementation, is efficiency. Using an external C engine for matching regular expression would far outperform our system, no matter how efficient we make our backend. Thus this is not intended to replace any existing functionality, rather we envision it as a very high-level interface to matching regular expressions in the spirit of String being [Char], where Text.Regex can be compared to using PackedString for critical programs. Perhaps by integrating regular patterns directly into a compiler like ghc we could use ugly low-level behind-the-scenes tricks for doing the actual matching in an external engine, thus greatly increasing efficiency. Any thoughts? =) We will supply the preprocessor for public scrutiny some time next week, we just need to do some more alpha-testing first... Comment away! regards, Niklas Broberg, d00nibro[at]dtek.chalmers.se Andreas Farre, d00farre[at]dtek.chalmers.se Chalmers University of Technology [1] Feel free to also visit the project that lead to this spin-off, Haskell Server Pages http://www.dtek.chalmers.se/~d00nibro/hsp/ _________________________________________________________________ Take off on a romantic weekend or a family adventure to these great U.S. locations. http://special.msn.com/local/hotdestinations.armx

2 1

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Graham Klyne 27 Feb '04

27 Feb '04

At 09:28 27/02/04 +0000, Simon Peyton-Jones wrote: >Which 'add' function is chosen depends on type type of 'fm'. But the >add function that is chosen in turn influences the type of the other >arguments. For example, in the call (fm.add foo), the type of 'foo' is >influenced by the choice of 'add'. But the type of 'foo' might (by the >magic of type inference) affect the type of 'fm'.... > >In Haskell today, you can at least tell what value is bound to each >identifier in the program, *without* first doing type checking. [...] Nicely explained. Until this, I had a feeling that the proposed type-directed value-binding resolution was potentially problematic for Haskell, but couldn't say why. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Regular Expressions - take 2
by John Meacham 26 Feb '04

26 Feb '04

I went ahead and implemented Perl Compatable Regular Expression support as well as a module which uses template haskell to check regular expressions at runtime. The full set of modules is RRegex - PCRE if available, else Posix, (compatable with Text.Regex) RRegex.PCRE - Perl compatable regular expressions RRegex.Posix - posix regular extensions (compatable with Text.Regex.Posix) RRegex.TH - template haskell compile-time checked regular expressions RRegex.Syntax - perl like overloaded matching syntax Along the way, I extende the Posix interface, as the one in Text.Regex.Posix was lacking in several key ways. among the more interesting changes are ability to use (?options) syntax with posix expressions all of PCRE goodness. which is a lot. much better error messages (compile-time when using TH) example: > Fail: user error (PCRE Regular Expression Error: > [a-z_A-Z]+\(.*); > ^ unmatched parentheses) notice it points out the exact spot of the error. ability to pull out offset,length integer pairs, rather than extracting the substrings all the =~ stuff mentioned in my previous email. see the sort-of homepage here: http://haskell.org/hawiki/RegexSyntax and haddock documentation here: http://repetae.net/john/computer/haskell/hsregex/hsregex/docs/index.html John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net ---------------------------------------------------------------------------

1 0

RE: [Haskell] performance tuning Data.FiniteMap
by Simon Peyton-Jones 26 Feb '04

26 Feb '04

| But in managing this tradeoff, what is faster: | * constructing/destructing e.g. 16 trees (for a 65000 item table) | * 2 memcpy of 256 item arrays (perhaps after you primop?) | | If the later is not dramatically slower than I | will bias towards more arrayness. I doubt the latter is dramatically slower, but you'd have to experiment to find out. And GHC is not doing as well as it should on arrays just now. (One of the things on our to-do list.) Might vary between implementations too. Simon

2 1

Haskell job (OH, USA)
by Mark.Carroll＠Aetion.com 26 Feb '04

26 Feb '04

Aetion Technologies LLC seeks another high-quality programmer. Development is mostly in Haskell, with some Java, mostly under Linux. An ideal candidate is excellent at acquiring, applying, and writing about new knowledge. Additional background in disciplines like mathematics, science, engineering, etc. is also attractive. Aetion's main customers are in defense and finance, so we prefer to hire people who can likely get a security clearance, and who do not object to developing military applications. Telecommuting isn't really an option, but Columbus, Ohio is a nice enough city, and the work tends to be varied and interesting - more challenging than mundane. Although we work to build useful software, a lot of our activities are at the leading edge of research, keeping us far ahead of competitors. The vacancy has not yet been advertised more formally through the usual HR channels. Aetion is most definitely an equal-opportunity employer. It would be fine to direct questions and resumes directly to me; I can pass them on to the right people where necessary. -- Mark

1 0

RE: [Haskell] regular expression syntax - perl ain't got nothin on haskell
by Simon Marlow 26 Feb '04

26 Feb '04

> At 18:07 23/02/04 -0800, John Meacham wrote: > >It provides regular and monadic versions, a very overloaded > and useful > >interface, as well as extensibility. although currently the only > >instance is based on Text.Regex, it generalizes to matching lists of > >arbitrary type, not just strings, and also leaves the door open for > >compile-time checked and optimized regular expressions via template > >Haskell. > > I have a concern here that I hope you won't see as a negative > response to > your ideas... > > I recently ran into some problems porting some Haskell code > to Windows > because it used the Text.Regex library, which is dependent on > a Unix-only system. Text.Regex works fine on Windows, at least on GHC. It seems that Hugs doesn't make it available, perhaps because it requires an auxiliary C regex engine, which we provide as part of GHC. It may be that this code isn't as portable as the rest of Hugs, which is why they don't provide it, but I'll let the Huge folks comment on that. Cheers, Simon

2 1