- Haskell - Haskell.org

Re: type class does not compile
by oleg＠pobox.com 13 Jul '04

13 Jul '04

Ben Yu wrote: > class Rule r u u' m where > apply :: r -> u -> m u' > > data And = And > > data Bin a b o = Bin a b o > > instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => > Rule (Bin r1 r2 And) u u'' m where > apply (Bin r1 r2 _) u = apply r1 u >>= apply r2 > > Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u'' > m)", but it is obviously same as the constraint I gave in the instance > declaration. This is like the famous show . read problem. Here, 'apply r1 u' produces the value of a type `m v' for _some_ v. and 'apply r2' consumes this value. There is no way for the compiler to figure out what this 'v' is. You specified 'Rule r1 u u' m' as a constraint. However, there is nothing that guarantees that your u' in the constraint is the same as v that is needed to resolve the overloading. So, we need either a functional dependency, or a resort to nifty local type variables. The example of the latter is > instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => > Rule (Bin r1 r2 And) u u'' m where > apply (Bin r1 r2 _) u = ((apply r1 u)::m u') >>= apply r2 which makes your code compile. For more detail, please see: http://www.haskell.org/pipermail/haskell/2003-September/012782.html http://www.haskell.org/pipermail/haskell/2003-October/012783.html

1 0

type class does not compile
by Ben.Yu＠combined.com 13 Jul '04

13 Jul '04

Hi, please bear with me if my question turns out to be a stupid mistake. It has taken me hours to figure this out. class Rule r u u' m where apply :: r -> u -> m u' data And = And data Bin a b o = Bin a b o instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => Rule (Bin r1 r2 And) u u'' m where apply (Bin r1 r2 _) u = apply r1 u >>= apply r2 Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u'' m)", but it is obviously same as the constraint I gave in the instance declaration. What am I doing wrong here? Thank you very much! This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.

2 2

RTA'05: call for papers
by femke＠few.vu.nl 11 Jul '04

11 Jul '04

****************************** * * * RTA'05 CALL FOR PAPERS * * * ****************************** http://www-i2.informatik.rwth-aachen.de/RTA05/ April 19--21, 2005 Nara, Japan The 16th Int. Conf. on Rewriting Techniques and Applications (RTA'05) will collocate with the 7th International Conference on Typed Lambda Calculi and Applications (TLCA'05) as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05). IMPORTANT DATES: Nov 12, 2004: Deadline for electronic submission of title and abstract Nov 19, 2004: Deadline for electronic submission of papers Jan 14, 2005: Notification of acceptance of papers Feb 4, 2005: Deadline for final versions of accepted papers Apr 19-21, 2005: Conference RTA is the major forum for the presentation of research on all aspects of rewriting. Typical areas of interest include (but are not limited to): * APPLICATIONS: case studies; rule-based (functional and logic) programming; symbolic and algebraic computation; theorem proving; system synthesis and verification; proof checking. * FOUNDATIONS: matching and unification; narrowing; completion techniques; strategies; constraint solving; explicit substitutions; tree automata. * FRAMEWORKS: string, term, and graph rewriting; lambda-calculus and higher-order rewriting; proof nets; constrained rewriting/deduction; categorical and infinitary rewriting. * IMPLEMENTATION: compilation techniques; parallel execution; rewriting tools. * SEMANTICS: equational logic; rewriting logic. INVITED TALKS will be given at RTA'05 by: * Amy Felty (Ottawa) * Yoshihito Toyama (Sendai) * Philip Wadler (Edinburgh) BEST PAPER AWARDS: An award of 100,000 Yen will be given to the best paper or papers as decided by the PC. RTA'04 PROGRAM COMMITEE: * Franz Baader (Dresden) * Mariangiola Dezani (Torino) * Juergen Giesl (Aachen, Chair) * Bernhard Gramlich (Vienna) * Florent Jacquemard (Cachan) * Claude Kirchner (Nancy) * Pierre Lescanne (Lyon) * Aart Middeldorp (Innsbruck) * Hitoshi Ohsaki (Amagasaki) * Vincent van Oostrom (Utrecht) * Christine Paulin-Mohring (Orsay) * Frank Pfenning (Pittsburgh) * Femke van Raamsdonk (Amsterdam) * Mark-Oliver Stehr (Urbana) * Rakesh Verma (Houston) * Andrei Voronkov (Manchester) RTA'05 SUBMISSIONS: Submissions must be original and not submitted for publication elsewhere. Submission categories include regular research papers and system descriptions. Also problem sets and submissions describing interesting applications of rewriting techniques will be very welcome. The page limit is 15 pages (10 pages for system descriptions). As usual, accepted papers will appear in the Springer-Verlag Lecture Notes in Computer Science series. More information about paper submission is available at the RTA'05 web page. http://www-i2.informatik.rwth-aachen.de/RTA05/ LOCATION, TRAVEL, ACCOMODATION, AND REGISTRATION The conference takes place in Nara park, which is one of the most important cultural sights of Japan with some of the oldest and most impressive temples and shrines. Airfares from Europe or the US to Japan are not expensive in mid-April and the conference will offer reasonably priced accommodation and low registration fees. RTA'05 PROGRAM CHAIR: Juergen Giesl LuFG Informatik II RWTH Aachen Ahornstr. 55 52074 Aachen Germany giesl(a)informatik.rwth-aachen.de RTA'05 CONFERENCE CHAIR: Hitoshi Ohsaki AIST Japan ohsaki(a)ni.aist.go.jp

1 0

ANN: "An Introduction to Computing with Haskell" in German
by Manuel M T Chakravarty 09 Jul '04

09 Jul '04

The book "An Introduction to Computing with Haskell" is now available in German from Pearson Education Germany http://www.pearson-studium.de/main/main.asp?page=bookdetails&ProductID=81781 The original English version has been reviewed in the Journal of Functional Programming, 14(2), March 2004, http://dx.doi.org/10.1017/S0956796803215033 The approach of the book was discussed in an Educational Pearl in the Journal of Functional Programming, 14(1), January 2004, http://dx.doi.org/10.1017/S0956796803004805 Manuel

1 0

Do the libraries define S' ?
by Graham Klyne 09 Jul '04

09 Jul '04

There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following: [[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a) (.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&) (.|.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.|.) = combineTest (||) t1 = (>0) .&. (<=4) $ 2 -- True t2 = (>0) .&. (<=4) $ 5 -- False t3 = (>0) .&. (<=4) $ 0 -- False t4 = (>0) .|. (<=4) $ 5 -- True t5 = (>0) .|. (<=4) $ 0 -- True tall = and [t1,not t2,not t3,t4,t5] ]] Looking at the fully-generalized type of 'combineTest', and digging around in SPJ's book on implementation of FP languages, I notice that my combineTest function has the same reduction pattern as the S' combinator used as an optimization of SK combinator compilation. All this (the recurring requirement, and the fact that S' is a very well-known combinator) leads me to think that maybe there is a version of S' somewhere in the standard Haskell libraries. If there is, where is it please? If not, should it be in there somewhere? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

8 8

CfP: SNPD'03 Workshop on High-Level Approaches to Parallel and Distributed Computing
by Clemens Grelck 08 Jul '04

08 Jul '04

Please apologize in case you receive multiple copies of this information. ========================================================================== CALL FOR PAPERS Workshop on High-Level Approaches to Parallel and Distributed Computing held in the context of the Fourth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD'03) October 16th - 18th, 2003 Luebeck, Germany http://www.isp.uni-luebeck.de/snpd03/Workshop/ws02/index.htm ========================================================================== Scope and Topics: ================== Today parallel and distributed computing systems are readily available and provide a continuously improving price/performance ratio. However, this technological breakthrough in hardware is not accompanied by similar progress in software technology. Parallel and distributed programming is still dominated by low-level techniques such as explicit message passing. This low level of abstraction makes programming these systems exceedingly difficult, time-consuming, and error-prone. Hence, parallel and distributed computing requires new programming models which liberate programmers from low-level concerns and increase programming productivity while maintaining reasonable trade-offs between level of abstraction and runtime performance. Topics of interest include, but are not limited to - methodologies for high-level parallel programming, - parallel programming languages, - high-level libraries for parallel computing, - compilers and runtime systems for parallel computing, - implementation aspects of high-level parallel programming environments, - compiler-based optimization and parallelization, - experience with high-level parallel programming environments, - support for debugging and performance analysis, - concurrent array programming, - programming concepts for the grid. This workshop provides a forum for researchers and practitioners interested in the design, implementation, and evaluation of high-level parallel programming concepts. It aims at creating some focus within the otherwise broad spectrum of the SNPD'03 conference. Workshop Chair and Organizer: ============================== Clemens Grelck University of Luebeck Institute of Software Technology and Programming Languages Seelandstr. 1A 23569 Luebeck, Germany E-Mail: grelck(a)isp.uni-luebeck.de Papers and Publication: ======================== Original, unpublished papers in English not exceeding 8 pages in ACIS double column format are solicited. For detailed formatting instructions see the SNPD'03 conference web site at http://www.isp.uni-luebeck.de/snpd03/index.htm Please send your papers as PDF documents by electronic mail directly to the workshop chair: grelck(a)isp.uni-luebeck.de Please indicate your paper submission by the subject SNPD03 WORKSHOP SUBMISSION Accepted papers will be published in the conference proceedings with ISBN. A selection of excellent papers presented at the conference including its workshops will be published in a special issue of the International Journal of Computer and Information Science. Important Deadlines: ===================== Full paper submission due: August, 30th Notification of acceptance: September, 10th Camera-ready papers due: September, 24th

1 3

Separate Namespaces and Type Classes
by Stephan Herhut 08 Jul '04

08 Jul '04

Hi all, I am pretty new to haskell, but while exploring the haskell module system, I came along some questions. As far as I found out, haskell supports separated namespaces, i.e. every module has its own symbol space. Thus, when defining a class in one module like module A(Foo(f)) where class Foo a where f :: a -> Integer one should be able to define two instances having the same signature, as long as they are in different namespaces module B(bar) where import A(Foo(f)) instance Foo Integer where f x = x bar x = f x module C(tango) import A(Foo(f)) instance Foo Integer where f x = x + 1 tango x = f x As the integer instances of Foo are in separate modules and thus namespaces, one should be able to just import bar and tango module Main(main) import B(bar) import C(tango) main = print( (bar 5) + (tango 4) ) But now, ghc complains about two instances of Foo Integer, although there should be none in the namespace main. I have not found any documentation on why ghc behaves like this and whether this conforms to the haskell language specification. Is there any haskell compiler out there that is able to compile the above example? Thanks for your help Stephan

3 2

SDL binding available.
by Adrian Hey 08 Jul '04

08 Jul '04

Hello, I've put my Haskell bindings to SDL,SDL_Image, and SDL_TTF here.. http://homepages.nildram.co.uk/~ahey/HLibs/Multimedia.SDL.Core/ http://homepages.nildram.co.uk/~ahey/HLibs/Multimedia.SDL.Image/ http://homepages.nildram.co.uk/~ahey/HLibs/Multimedia.SDL.TTF/ It's not really as polished as I would like for a first release, but I haven't had much time to work on it recently and it seems a pity to see it just gathering dust when it might be useful to some people. I hope to get back to work on it myself soon. At the moment it's probably not terribly useful. It's just a raw binding to (most of) the SDL video and event handling. So it has no sound, no computed graphics capability (just text rendering and pre-prepared sprite blitting), and joystick handling still sucks a bit. Also, blitting is not very fast under X11 (no surprises there). It was much faster on Win32/DirectX last time I tested it, but that was a while ago so I don't know if the current version builds or works on Win32. BTW, If anybody finds the lack of audio too style cramping, feel free to contribute a binding to this part of SDL :-) It's not something I need particularly urgently so you might have to wait a while otherwise. I plan to give the graphics capabilities higher priority. Regards -- Adrian Hey

1 0

Re: [Haskell] for large x, log (x::Integer) :: Double
by Greg Buchholz 05 Jul '04

05 Jul '04

-- Inspired from Mr. Howard Oakley. Might not qualify as "good", -- but with this function I get log10(x)=849.114419903382 main = do print(show(log10(x))) x = 1301427272151881160612765560226881966218101403436917787184856303672382623256898455416763978959067300249652773943715743032733292602624834984761739233232794619193611954735720284761058146899246611113236700853600891798968920775344491685185906922596026543915321367577774522912315930144523472702386240645993859368230855941019371447058664115974032571881072431604651385520393674840678811793554266595013773947434115579588912967969680150473258236727830867832149867100437142705476716669039640252677955201589378051836112800268367331455296715904387732836350613539218249950829555418397197909288345303407194983545308212828662999623279222913080214196287140117582811769188486693208227570257136851945943408206281672555558289460256867016896063334140640075708083581866297494610834545554864846306383014549439540479675828018496049574066533167553894586573246931377586176000 log10 :: Integer -> Double log10 n = let i = length(show(n)) - 1 t = take 12 (show(n)) r = read(t) f = r / 10 ^ (length(t) - 1) in fromIntegral(i) + log(f)/log(10) --Greg Buchholz

3 2

Overriding Prelude functions
by André Pang 05 Jul '04

05 Jul '04

Hi all, Inspired by a bit of hackery today, I managed to find a nice way to re-define Prelude functions in modular way. There may be some functions in the Prelude that you would like to redefine: in this example, we redefine the "lookup" function, which normally has a type signature of lookup :: forall b a. (Eq a) => a -> [(a, b)] -> Maybe b Here, we make lookup a bit more generic, so that we can look up any data structure that is "lookupable" -- we override the Prelude's lookup function with our own. The motivation is that there may be a module which provides you many useful functions, but unfortunately has namespace clashes with your own module. One example is that you've defined a generic 'zip' function named gzip, which could substitute perfectly for the Prelude's own zip function, but you have to call it gzip only because the function name 'zip' is already taken. The advantage of this is that you can smoothly integrate extra functionality with already-existing functions by overriding them -- and by providing the extra functionality in a module, you leave it up to the module user whether they want to take advantage of that functionality or not. The essential idea is to define a module (e.g. MyPrelude), which does the following: module MyPrelude(module Prelude, lookup) where import qualified Prelude as P import Prelude hiding (lookup) lookup = ... (your own definition here) ... That module re-exports the Prelude and its own lookup function. Then, a module which wants to use the overridden lookup function does the following: {-# OPTIONS -fno-implicit-prelude #-} module UseLookup where import MyPrelude ... now uses MyPrelude's lookup function instead of Prelude's lookup ... A concrete implementation of this idea is below. Have the appropriate amount of fun :). MyPrelude.hs {-# OPTIONS -fglasgow-exts #-} module MyPrelude(module Prelude, lookup) where import qualified Prelude as P import Prelude hiding (lookup) import Data.FiniteMap import Data.Set -- override the lookup function, defined in the Prelude as: -- -- lookup :: forall b a. (Eq a) => a -> [(a, b)] -> Maybe b class Lookup lookupable key value | lookupable -> key value where lookup :: Ord key => lookupable -> key -> Maybe value instance Lookup (FiniteMap key value) key value where lookup = lookupFM instance Lookup [(key, value)] key value where lookup = lookupListOfTuples instance Lookup (Set value) value value where lookup container element | elementOf element container = Just element | otherwise = Nothing lookupListOfTuples [] _ = Nothing lookupListOfTuples ((key, value):xs) key' | key == key' = Just value | otherwise = lookupListOfTuples xs key' UseLookup.hs: {-# OPTIONS -fno-implicit-prelude #-} module UseLookup where import Data.FiniteMap import Data.Set import MyPrelude fm = addToFM emptyFM "foo" "bar" set = mkSet ["foo"] tupleList = [("foo", "bar")] An example session: *UseLookup> lookup fm "foo" Just "bar" *UseLookup> lookup fm "baz" Nothing *UseLookup> lookup set "foo" Just "foo" *UseLookup> lookup tupleList "foo" Just "bar" *UseLookup> -- % Andre Pang : trust.in.love.to.save

1 0