- Haskell - Haskell.org

Haskell Weekly News: February 06, 2006
by dons＠cse.unsw.edu.au 06 Feb '06

06 Feb '06

Haskell Weekly News: February 06, 2006 Greetings, and thanks for reading issue 23 of HWN, a weekly newsletter covering developments in the Haskell community. Each Monday, new editions are posted to [1]the Haskell mailing list and to [2]The Haskell Sequence. [3]RSS is also available. 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ 3. http://sequence.complete.org/node/feed Announcements and New Code * EclipseFP. Thiago Arrais [4]announced that EclipseFP 0.9.1 has been released since last Friday. It is an open-source development environment for Haskell code. EclipseFP integrates GHC with an Haskell-aware code editor and also supports quick file browsing through an outline view, automatic building/compiling and quick one-button code execution. Downloads and more information are available on the [5]project home page. 4. http://article.gmane.org/gmane.comp.lang.haskell.cafe/11141 5. http://eclipsefp.sourceforge.net/ * Class-parameterized classes, and type-level logarithm. Oleg Kiselyov [6]writes: we show invertible, terminating, 3-place addition, multiplication, exponentiation relations on type-level Peano numerals, where any two operands determine the third. We also show the invertible factorial relation. This gives us all common arithmetic operations on Peano numerals, including n-base discrete logarithm, n-th root, and the inverse of factorial. The inverting method can work with any representation of (type-level) numerals, binary or decimal. Oleg says, "The implementation of RSA on the type level is left for future work". 6. http://article.gmane.org/gmane.comp.lang.haskell.general/13223 * Fast mutable variables for IO and ST. Bulat Ziganshin [7]released a module for fast mutable variables, providing efficient newVar/readVar/writeVar, as well as support for unboxed values, fast unboxed bitwise operations, and more. 7. http://article.gmane.org/gmane.comp.lang.haskell.cafe/11230 * Bang patterns. Strictify yourself up! As seen [8]here, GHC now implements [9]bang patterns: Fri Feb 3 09:51:08 PST 2006 simonpj * Add bang patterns This commit adds bang-patterns, enabled by -fglasgow-exts or -fbang-patterns disabled by -fno-bang-patterns 8. http://article.gmane.org/gmane.comp.lang.haskell.cvs.ghc/13434 9. http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/BangPatterns Contributing to HWN Ed: apologies for the length this week, as I was a bit rushed. You can help us create new editions of this newsletter. Please see the [10]contributing information, send stories to dons -at- cse.unsw.edu.au. The darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 10. http://sequence.complete.org/hwn-contrib

1 0

System.FilePath survey
by Krasimir Angelov 06 Feb '06

06 Feb '06

Hello Haskellers, There was a long discussion in October 2004, about the a FilePath module which is currently used in Cabal. There was an idea to move it to the standard libraries but since there were a lot of objections it was removed. http://www.haskell.org/pipermail/libraries/2004-October/002591.html I would like to hear what the community think we need for the proper file path handling. This module is important if we would like to make Haskell more portable. Please answer to the following questions: * Have you used the existing FilePath module and what do you think about it? Do you found it useful? Have you made any significant bugfixes or extensions to it? * Will you be happy with a library that represents the file path as String? The opposite is to use ADT for it. The disadvantage is that with the current IO library we should convert from ADT to String and back again each time when we have to do any IO. The ADT may have advantages for the internal library implementation. * Do you think that we have to use unboxed arrays of Word8/Word16 for file path? Any other suggestions are welcome. Since such kind of discussions are going to be rather long please reply to libraries(a)haskell.org Cheers, Krasimir

8 9

unsafeInterleaveST
by Bulat Ziganshin 06 Feb '06

06 Feb '06

Hello haskell, is it possible to implement unsafeInterleaveST? why i want it: i have the following definitions: class (MonadHelper m) => Stream m h where vGetContents :: h -> m String -- default definition vGetContents h = mUnsafeInterleaveIO $ do eof <- vIsEOF h if eof then return [] else do x <- vGetChar h x `seq` return () xs <- vGetContents h return (x:xs) class (Monad m) => MonadHelper m where mUnsafeInterleaveIO :: m a -> m a instance MonadHelper IO where mUnsafeInterleaveIO = unsafeInterleaveIO instance MonadHelper (ST s) where mUnsafeInterleaveIO = id that allows to make much more efficient lazy implementation of vGetContents for streams that work in IO monad. on the other side, ST-based streams will need to build full list before returning from vGetContents. if the unsafeInterleaveST is possible, then this type of computations will become much more efficient moreover, this can be way to mix up several ST computations and to implicitly define parallelism in algorithm so that compiler can better optimize program -- Best regards, Bulat mailto:bulatz@HotPOP.com

2 2

Streams: the extensible I/O library
by Bulat Ziganshin 06 Feb '06

06 Feb '06

Hello I have developed a new I/O library that IMHO is so sharp that it can eventually replace the current I/O facilities based on using Handles. The main advantage of the new library is its strong modular design using typeclasses. The library consists of small independent modules, each implementing one type of stream (file, memory buffer, pipe) or one part of common stream functionality (buffering, Char encoding, locking). 3rd-party libs can easily add new stream types and new common functionality. Other benefits of the new library include support for streams functioning in any monad, Hugs and GHC compatibility, high speed and an easy migration path from the existing I/O library. You can find further information about the library at the page http://haskell.org/haskellwiki/Library/Streams and download it as http://freearc.narod.ru/Streams.tar.gz I thank Jean Philippe Bernardy, Jared Updike and Henk Jan Van Tuyl, who are corrected library documentation ps: the library also includes two more layers - binary I/O and serialization - on top of Streams. now i'm hardly working on documenting these modules -- Best regards, Bulat mailto:bulatz@HotPOP.com

3 3

Survey of Haskell in higher education
by John Hughes 06 Feb '06

06 Feb '06

Before Christmas I invited people on this mailing list to complete a web survey about the use of Haskell in higher education. Many have done so--thank you very much! I received 126 responses from 89 universities, accounting for 5-10,000 students taught using Haskell this academic year. The survey is now closed, and the results are available on the web at http://www.cs.chalmers.se/~rjmh/Wash/Survey/teaching.htm. I've put up the raw data, together with various simple analyses. Enjoy! John Hughes

1 0

FRP and Yampa
by Brett G. B. Wortzman 05 Feb '06

05 Feb '06

Hi all, I'm doing my undergraduate thesis on monads, comonads, and arrows and their applications. I've been focusing part of my research on the Yale Haskell group's work on Functional reactive programming, and specifically on their move from a monadic to an arrow-based implemenation (as in http://haskell.cs.yale.edu/yale/papers/haskellworkshop02/index.html) I've been unable to find any literature that really gives a good explanation of why they chose to make this move, however. Can anybody shed some light on why arrows were seen as a better choice for this? Also, does anyone know if there's been any research about implementing FRP with comonads? I can't find any literature about it, but I'm not sure if it's never been looked into, or just attempted and determined to be a bad idea. If the latter, I'd be interested to know why. Thanks, Brett Wortzman

2 1

RE: [Haskell] System.FilePath survey
by David Wakeling 03 Feb '06

03 Feb '06

>===== Original Message From Krasimir Angelov <kr.angelov(a)gmail.com> ===== >Hello Haskellers, > >There was a long discussion in October 2004, about the a FilePath >module which is currently used in Cabal. There was an idea to move it >to the standard libraries but since there were a lot of objections it >was removed. > >http://www.haskell.org/pipermail/libraries/2004-October/002591.html > >I would like to hear what the community think we need for the proper >file path handling. This module is important if we would like to make >Haskell more portable. >Please answer to the following questions: > > * Have you used the existing FilePath module and what do you think >about it? >Do you found it useful? Have you made any significant bugfixes or >extensions to it? > > * Will you be happy with a library that represents the file path >as String? The opposite is to use ADT for it. The disadvantage is that >with the current IO library we should convert from ADT to String and >back again each time when we have to do any IO. The ADT may have >advantages for the internal library implementation. > > * Do you think that we have to use unboxed arrays of Word8/Word16 >for file path? > >Any other suggestions are welcome. Since such kind of discussions are >going to be rather long please reply to libraries(a)haskell.org > >Cheers, > Krasimir >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell

1 0

Class-parameterized classes, and the type-level logarithm
by oleg＠pobox.com 02 Feb '06

02 Feb '06

We show invertible, terminating, 3-place addition, multiplication, and exponentiation relations on type-level Peano numerals, where _any_ two operands determine the third. We also show the invertible factorial relation. This gives us all common arithmetic operations on Peano numerals, including n-base discrete logarithm, n-th root, and the inverse of factorial. The inverting method can work with any representation of (type-level) numerals, binary or decimal. Furthermore, the inverter itself is generic: it is a type-class function, that is, a type-class parameterized by the type-class to `invert'. There has been a proposal on Haskell' to give equal rights to types and classes. In Haskell98+multi-parameter type classes, classes are already first-class, for all practical purposes. We can quite easily define (potentially, higher-order) type functions on type classes. Ashley Yakeley wrote: ] I know for the usual Peano representation of natural numbers, at least, ] it's possible to represent addition and subtraction with a single class ] with two fundeps (because classes represent relations between types ] rather than functions on them). That can be done even for decimal type numerals, cf. number-parameterized-types paper. But we can do better: we can have _three_ functional dependencies, so that any two operands of the type class determine the third. The key insight was the result of a conversation with Chung-chieh Shan and Gregory Price in the evening of Nov 10, 2003. Despite what the extension says, the arithmetic relations in this file are all decidable. > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module PeanoArithm where > > data Z > data S a > __ = __ First we define a semi-sum relation, with only two functional dependencies: > class Sum2 a b c | a b -> c, a c -> b > instance Sum2 Z a a > instance Sum2 a b c => Sum2 (S a) b (S c) Now we add the third dependency. It is that simple. > class Sum a b c | a b -> c, a c -> b, b c -> a > instance (Sum2 a b c, Sum2 b a c) => Sum a b c After defining a few numbers, > add:: Sum a b c => a -> b -> c > add = __ > > type One = S Z > type Two = S (S Z) > > zero = __ :: Z > one = __ :: One > two = __ :: Two > three = add one two > n4 = add two two we see that the typechecker can indeed add and subtract: > ta1 = \x -> (add three x `asTypeOf` three) > ta2 = \x -> (add x two `asTypeOf` three) > -- ta3 = \x -> (add three x `asTypeOf` two) -- fails *PeanoArithm> :t ta1 ta1 :: Z -> S (S (S Z)) *PeanoArithm> :t ta2 ta2 :: S Z -> S (S (S Z)) Before we move to products, we introduce a few utilities > class NLE x y > instance Sum2 x a y => NLE x y > > class Mul a b c | a b -> c -- a single-dependency multiplication > instance Mul Z b Z > instance (Mul a b c', Sum c' b c) => Mul (S a) b c -- (a+1)*b = a*b + b The relation |NLE x y| holds if |x| is less or equal to |y|, that is, there exists a numeral |a| that in sum with |x| gives |y|. We now introduce the generic inverter of an arithmetic function defined on the whole set of natural numbers. The inverter is parameterized by the numeric function (that is, a type class) to invert. We define the type of these classes by the following class. It maps types to classes (see also the HList paper): > class Registry clas a b c | clas a b -> c The inverter, the type-class function, is so trivial that I'm ashamed to discuss it. It is a simple for-loop. > class Inv clas init limit a b c | clas init a b -> c > instance (NLE x limit, Registry clas x b a', Sum2 a' r a, > Inv' r clas x limit a b c) > => Inv clas x limit a b c > class Inv' r clas x limit a b c | r clas x a b -> c > instance Inv' Z clas x limit a b x -- Found it > instance Inv clas (S x) limit a b c -- try next x > => Inv' (S r) clas x limit a b c Division is defined as an inverse of multiplication: > data RegMul > instance Mul a b c => Registry RegMul a b c > > class Div m n q | m n -> q -- m = n * q > instance Inv RegMul Z m m n q => Div m n q We partially apply Inv to the right operands, and get the Div relation in return. > pdiv :: Div a b c => a -> b -> c > pdiv = __ > > -- Only where all dependencies exist... > class Product a b c | a b -> c, a c -> b, b c -> a > instance (Mul a b c, Div c b a, Div c a b) => Product a b c > > prod:: Product a b c => a -> b -> c > prod = __ Now the typechecker can multiply and divide > n6 = prod two three > tm1 = \x -> (prod three x `asTypeOf` n6) > tm2 = \x -> (prod x two `asTypeOf` n6) > -- tm3 = \x -> (prod x n4 `asTypeOf` n6) > tm4 = \x -> (prod x n6 `asTypeOf` n6) > -- tm5 = \x -> (prod x zero `asTypeOf` n6) > tm6 = \x -> (prod x zero `asTypeOf` zero) The inferred types are tm1 :: S (S Z) -> S (S (S (S (S (S Z))))) tm2 :: S (S (S Z)) -> S (S (S (S (S (S Z))))) tm4 :: S Z -> S (S (S (S (S (S Z))))) The commented-out tests raise type errors. The exponentiation is trivial: > class Raise b e c | b e -> c -- c = b ^ e > instance Raise a Z (S Z) > instance (Raise b e c', Mul b c' c) => Raise b (S e) c The logarithm and the n-th root are two inverses of (partially-applied) exponentiation. It takes a couple of lines to define each > data RegRaiseI > instance Raise b a c => Registry RegRaiseI a b c > > class Log n b e | n b -> e -- e = log_b n > instance Inv RegRaiseI Z n n b e => Log n b e > > data RegRaise > instance Raise a b c => Registry RegRaise a b c > > class Root a b c | a b -> c -- c = b-th root of a > instance Inv RegRaise Z a a b c => Root a b c We introduce the full exponentiation relation > class Exp b e c | b e -> c, b c -> e, e c -> b > instance (Raise b e c, Log c b e, Root c e b) => Exp b e c > > pexp:: Exp a b c => a -> b -> c > pexp = __ and test it > n8 = add n4 n4 > n9 = prod three three > te1 = pexp three two > te2 = \x -> (pexp two x `asTypeOf` (add n8 n8)) > te3 = \x -> (pexp x three `asTypeOf` n8) > -- te4 = \x -> (pexp x three `asTypeOf` n6) > te5 = \x -> (pexp three x `asTypeOf` three) *PeanoArithm> :t te2 te2 :: S (S (S (S Z))) -> S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S Z))))))))))))))) *PeanoArithm> :t te3 te3 :: S (S Z) -> S (S (S (S (S (S (S (S Z))))))) Indeed, 4 is the binary logarithm of 16, and two is the cubic root of 8. Having gone that far, it is impossible to avoid factorial and its inverse (as an evidence of further evolution of the Haskell programmer) > class FactF a b | a -> b > instance FactF Z (S Z) > instance (FactF a b', Mul (S a) b' b) => FactF (S a) b > > data RegFact > instance FactF a c => Registry RegFact a b c > > class FactR a c | a -> c -- Inverse of Fact > instance Inv RegFact (S Z) a a Z c => FactR a c > > class Fact a b | a -> b, b -> a > instance (FactF a b, FactR b a) => Fact a b > > fact :: Fact a b => a -> b > fact = __ -- :t fact n4 *PeanoArithm> :t \x -> (fact x `asTypeOf` (prod n4 n6)) \x -> (fact x `asTypeOf` (prod n4 n6)) :: S (S (S (S Z))) -> S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S Z))))))))))))))))))))))) Indeed, 4 is the inverse factorial of 24. It took only a split second. The practical outcome of this exercise is the creation of a benchmark suite for Haskell typecheckers, e.g., computing the inverse factorial of 720. Perhaps there should be a shoot-out entry for the speed of typechecking. The implementation of RSA on type level is left for future work.

1 0

RULE 2006 at FLoC --- paper deadline 14 May
by Ralf Lammel 02 Feb '06

02 Feb '06

====================================================================== Call for Papers RULE 2006 7th International Workshop on Rule-Based Programming http://www.dcs.kcl.ac.uk/events/RULE06/ Seattle, USA 11th August 2006 A satellite event of RTA 2006 at FLoC ======================================================================= The basic concepts of rule-based programming appear throughout Computer Science, from theoretical foundations to practical implementations. Term rewriting is used in semantics in order to describe the meaning of programming languages, as well as in the implementation of program transformation systems. Rules are used implicitly or explicitly to perform computations, e.g., in Mathematica, OBJ, ELAN, Maude or to perform deductions, e.g., by using inference rules to describe or implement a logic, theorem prover or constraint solver. Mail clients and mail servers use complex rules to help users organising their email and sorting out spam. Language implementations use bottom-up rewrite systems for code generation (as in the BURG family of tools.) Constraint-handling rules (CHRs) are used to specify and implement constraint-based algorithms and applications. Rule-based programming idioms also give rise to multi-paradigm languages like Claire. The purpose of this workshop is to bring together researchers from the various communities working on rule-based programming to foster advances in the theory of rule-based programming, cross-fertilization between theory and practice, research on rule-based programming methods, and the exploration of important application domains of rule-based programming. RULE 2006 will be a one-day satellite event of RTA 2006 at FLoC. Topics of interest ------------------ * Languages for rule-based programming - Expressive power, Idioms, Design patterns - Semantics, Type systems - Implementation techniques - System descriptions * Other foundations - Complexity results - Advances on rewriting logic - Advances on rewriting calculus - Static analyses of rule-based programs - Transformation of rule-based programs * Applications of rule-based programming, e.g.: - Program transformation - Software analysis and generation - System Control - Work-flow control - Knowledge engineering - System descriptions * Combination with other paradigms - Functional programming - Logic programming - OO programming - Biocomputing - Language extensions - Language embeddings Submissions and Publication: Papers (of at most 15 pages) should be submitted electronically via the submission page: http://www.easychair.org/RULE2006 Any problems with the submission procedure should be reported to one of the PC chairs: Maribel.Fernandez(a)kcl.ac.uk, Ralf.Lammel(a)microsoft.com Accepted papers will be published in the preliminary proceedings volume, which will be available during the workshop. The final proceedings will be published in Electronic Notes in Theoretical Computer Science (ENTCS), Elsevier. IMPORTANT DATES - 14th May 2006: Deadline for electronic submission of papers - 15th June 2006: Notification of acceptance of papers - 30th June 2006: Deadline for final versions of accepted papers - 11th August 2006: Workshop Programme Committee: - Mark van den Brand (TU Eindhoven, Netherlands) - Horatiu Cirstea (LORIA, France) - Pierre Deransart (INRIA Rocquencourt, France) - Michael L. Collard (Kent State University, USA) - Martin Erwig (Oregon State University, USA) - Francois Fages (INRIA Rocquencourt, France) - Maribel Fernandez (Co-Chair, King's College London, UK) - Jean-Pierre Jouannaud (LIX, Ecole Polytechnique, France) - Oleg Kiselyov (FNMOC, USA) - Ralf Laemmel (Co-Chair, Microsoft, USA ) - Ugo Montanari (Universita di Pisa, Italy) - Pierre-Etienne Moreau (LORIA, France) - Tobias Nipkow (Technical University Munich, Germany) - Tom Schrijvers (K.U.Leuven, Belgium) - Martin Sulzmann (National University of Singapore, Singapore) - Victor Winter (University of Nebraska at Omaha, USA)

1 0

Type synonyms in the instance head
by Mads Lindstrøm 02 Feb '06

02 Feb '06

Hi all In this url http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.htm… one can read about "Type synonyms in the instance head". A quote: "You cannot, for example, write: type P a = [[a]] instance Monad P where ... This design decision is independent of all the others, and easily reversed, but it makes sense to me." It does not make sense to me! Could anybody explain why this makes sense? Below, I will try to explain why it does not make sense to me. If I have: data LongAndUglyName a = ... type ShortAndTellingName a = LongAndUglyName a It seems to make sensible to: instance Foo ShortAndTellingName Also it is called a type _synonym_ and the type synonym and what it is synonym for, should therefore be interchangeable. This restriction do not only apply to instance heads, but also to contexts, as in: instance (Foo LongAndUgleName) => class something ... Here again LongAndUglyName cannot be replaced by ShortAndTellingName. This can be annoying if you have a lot of these instance declarations. Also what the type synonym is synonym for, may not have any name and thus properly not be telling at all, as in: type TellingName a = \a -> String /Mads Lindstrøm

4 3