September 2002 - Haskell

tuple component functions
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

S.D.Mechveliani writes: > As Haskell has the standard functions fst, snd to decompose (a,b), > maybe, it worths to provide also > tuple31, tuple31, tuple31, > ... > tuple51, tuple52, tuple53, tuple54, tuple55 > > for the tuples of n = 3,4,5 ? I've found some of these useful, except I named them differently: > fst3 :: (a,b,c) -> a > fst3 (x,_,_) = x > snd3 :: (a,b,c) -> b > snd3 (_,x,_) = x > thd3 :: (a,b,c) -> c > thd3 (_,_,x) = x .... never got around to quadruples etc. I also defined (some of these may be untested): > tripl :: a -> (a,a,a) > tripl x = (x,x,x) > curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d > curry3 f x y z = f (x, y, z) > uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d) > uncurry3 f t = f (fst3 t) (snd3 t) (thd3 t) > applyTriple :: (a -> b, a -> c, a -> d) -> a -> (b,c,d) > applyTriple (f,g,h) x = (f x, g x, h x) > cross3 :: (a -> b, c -> d, e -> f) -> (a,c,e) -> (b,d,f) > cross3 (f,g,h) (x,y,z) = (f x, g y, h z) > mapTriple :: (a -> b) -> (a, a, a) -> (b, b, b) > mapTriple = cross3 . tripl > applyFst3 :: (a -> b) -> (a, c, d) -> (b, c, d) > applyFst3 f = applyTriple (f . fst3, snd3, thd3) > applySnd3 :: (a -> b) -> (c, a, d) -> (c, b, d) > applySnd3 f = applyTriple (fst3, f . snd3, thd3) > applyThd3 :: (a -> b) -> (c, d, a) -> (c, d, b) > applyThd3 f = applyTriple (fst3, snd3, f . thd3) > applyArgs3 :: (a -> b) -> (c -> d) -> (e -> f) -> (b -> d -> f -> g) -> (a -> c -> e -> g) > applyArgs3 af1 af2 af3 f = \x y z -> f (af1 x) (af2 y) (af3 z) > rotl :: (a -> b -> c -> d) -> (b -> c -> a -> d) > rotl f y z x = f x y z > rotr :: (a -> b -> c -> d) -> (c -> a -> b -> d) > rotr f z x y = f x y z > rotl4 :: (a -> b -> c -> d -> e) -> (b -> c -> d -> a -> e) > rotl4 f y z t x = f x y z t > rotr4 :: (a -> b -> c -> d -> e) -> (d -> a -> b -> c -> e) > rotr4 f t x y z = f x y z t Some more combinators (only for pairs so far): > twin :: a -> (a,a) > twin x = (x,x) > swap :: (a,b) -> (b,a) > swap (x,y) = (y,x) -- apply a pair of functions to one argument > applyPair :: (a -> b, a -> c) -> a -> (b, c) > applyPair (f, g) x = (f x, g x) -- apply a pair of functions to a pair > cross :: (a -> b, c -> d) -> (a, c) -> (b, d) > cross (f, g) = applyPair (f . fst, g . snd) -- compose a pair of functions onto one function > dotPair :: (a -> b, a -> c) -> (d -> a) -> (d -> b, d -> c) > dotPair (f, g) h = (f . h, g . h) -- compose a pair of functions onto a pair of functions > dotCross :: (a -> b, c -> d) -> (e -> a, f -> c) -> (e -> b, f -> d) > dotCross (f, g) (h, i) = (f . h, g . i) > mapPair :: (a -> b) -> (a, a) -> (b, b) > mapPair = cross . twin > applyFst :: (a -> b) -> (a, c) -> (b, c) > applyFst f = applyPair (f . fst, snd) > applySnd :: (a -> b) -> (c, a) -> (c, b) > applySnd f = applyPair (fst, f . snd) > applyArgs :: (a -> b) -> (c -> d) -> (b -> d -> e) -> (a -> c -> e) > applyArgs af1 af2 f = \x y -> f (af1 x) (af2 y) > betweenFst :: (a -> b -> c) -> (a, d) -> (b, e) -> c > betweenFst = applyArgs fst fst > betweenSnd :: (a -> b -> c) -> (d, a) -> (e, b) -> c > betweenSnd = applyArgs snd snd I find these combinators useful, and probably other people have their own versions - it would be nice to get them standardised, so we all speak the same language. By standardised, I mean a prominent version that will be adopted by users, not necessarily a committee process. Tim

3 2

ICFP programming contest
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

Michael Hobbs writes: > Just took a look at the results for the ICFP contest. Am I correct in > assuming that "LA" stands for Lennart Augustsson and that "Si^3" stands > for Simon Marlow, Simon Peyton-Jones, Sigbjorn Finne? Is there a URL for the results ? Tim

2 1

efficiency of mfix
by Hal Daume III 14 Oct '02

14 Oct '02

Hi all, I've been experimenting in ghc with mfix (I noticed on the cvs logs that mdo is going to be supported shortly :P), so I decided to see how it would work for me. My simple task is to normalize an array. That is, given an array, replace each value with a new value such that the array sums to one and that the ratios between values before and after normalization are the same. There is of course a two pass solutions, using a fold and a map. This is implementing using IOArrays, so this looks like: norm a = do t <- foldM (\t i -> (t+) `liftM` readArray a i) 0 [1..sz] mapM_ (\i -> readArray a i >>= writeArray a i . (/t)) [1..sz] where (_,sz) = Data.Array.IO.bounds a There is a one pass solution using mfix. This looks like: mfix (\ ~s -> ioaA a 1 s) where ioaA is defined as: ioaA a i s | i > sz = return 0 | otherwise = do s' <- ioaA a (i+1) s v <- readArray a i writeArray a i (v/s) return (s' + v) where (_,sz) = Data.Array.IO.bounds a Now, in practice, the two-pass solution is about twice as fast as the one-pass solution. I've looked a bit at the core generated, but without knowing what's going on internally, it's hard to say where the inefficiencies come from. I'm hoping someone can shed some light on this. Some timing results based on different array sizes: 50000 elements, 32m heap fix: 0.79u 0.04s 0:00.89 93.2% 0.77u 0.07s 0:00.89 94.3% 0.75u 0.10s 0:00.94 90.4% normal: 0.58u 0.01s 0:00.60 98.3% 0.53u 0.03s 0:00.66 84.8% 0.53u 0.05s 0:00.61 95.0% 100000 elements, 32m heap fix: 2.40u 0.10s 0:02.73 91.5% 2.38u 0.10s 0:02.54 97.6% 2.37u 0.13s 0:02.70 92.5% normal: 1.50u 0.03s 0:01.55 98.7% 1.49u 0.05s 0:01.57 98.0% 1.52u 0.03s 0:01.59 97.4% 200000 elements, 32m heap fix: 7.90u 0.16s 0:08.09 99.6% 7.99u 0.17s 0:08.38 97.3% 7.96u 0.21s 0:08.40 97.2% normal: 4.43u 0.06s 0:04.69 95.7% 4.38u 0.14s 0:04.75 95.1% 4.49u 0.07s 0:04.79 95.1% 400000 elements, 32m heap fix: 29.09u 0.34s 0:30.95 95.0% normal: 14.51u 0.16s 0:15.02 97.6% Using unboxed arrays is not possible in the fixed point version (loop). On the normal version, it just about triples the speed across the board. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 3

Pure File Reading (was: Dealing with configuration data)
by Koen Claessen 11 Oct '02

11 Oct '02

Dear all, At the moment, a discussion on haskell-cafe is going on about how to neatly program the fact that an entire program depends on a number of parameters that are read in once at the beginning of a program. The suggestion that many people came up with was using unsafePerformIO in the beginning to read the file. Here is my version of that: | data Configuration = ... -- config data | | getConfig :: Configuration | getConfig = unsafePerformIO $ | do ...read configuration from file... | return configuration | | main = | do doStuff It is quite disturbing that there is no other easy way to do this than using unsafePerformIO (except for using implicit parameters perhaps, but there are other reasons for not using those). I have been thinking a little bit more about this and here is what I found. Remember the Gofer days, when Gofer had a "function": openFile :: FilePath -> String This was of course a cheap and dirty way of implementing things like the getConfig above, but it is impure. However, one could imagine a functional version of this function: readFileOnce :: FilePath -> Maybe String This function will read the contents of the file (and return Nothing if something went wrong), but it is memoized, so that the second time you use this function you get the same result. So, it is a pure function. (Admittedly, it is somewhat unpredictable, but you will always get the same result for the same arguments.) It is no more strange than GHC's pure version of the getArgs function (I forgot what it was/is called). How about space behavior, you say? Reading a file, and memoizing the result means storing the whole contents of the file in memory! The point is that the use of this function will typically happen at the beginning of a program, when reading the configuration file(s). When all this has happened, the function readFileOnce, and its memo table, will be garabage collected. (Of course there is no guarantee that all calls to readFileOnce will be evaluated at the beginning of a program, and it is not required, but when you do, there are no space problems.) There could of course be pure "-Once" versions of other IO operations. Here is a list of possibilities: - reading a file - getting arguments - getting environment variables - downloading a webpage - ... What do you think? Regards, /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden.

3 2

SQL queries in Haskell
by João Marcos 01 Oct '02

01 Oct '02

We're currently developing a project in my gradutaion course (Computer Science), about databases in Haskell. We didn't manage to write the correct Haskell code for the "Insert" and "Delete" operations. If you could help us with this, we would be very grateful. Best regards, Joao Marcos jmfa(a)terra.com.br joao(a)dcc.uesb.br

2 1

call for workshops
by icalp2003＠TUE.nl 30 Sep '02

30 Sep '02

[apologies for multiple copies] ICALP 2003 Eindhoven, the Netherlands, June 30 - July 4, 2003 ICALP 2003, the 30th International Colloquium on Automata, Languages and Programming, will be held next year in Eindhoven, the Netherlands from June 30th till July 4th. For the weekends preceding and following the week of the ICALP conference several satelite events are planned. For more information see http://www.win.tue.nl/icalp2003. The ICALP 2003 Organizing Commitee welcomes further initiatives. In particular, workshop proposals are invited addressing the following issues: - workshop title and brief description of the scope and goal - motivation of the relevance to the TCS community - organizing commitee and potential invited speakers - format of the workshop, duration and refereeing procedure, if applicable Proposals can be sent to Erik de Vink, workshop coordinator for ICALP 2003, e-mail evink(a)win.tue.nl, no later than November 8th, 2002.

1 0

Re: Pure File Reading (was: Dealing with configuration data)
by Yoann Padioleau 26 Sep '02

26 Sep '02

Lars Lundgren <d95lars(a)dtek.chalmers.se> writes: > On 26 Sep 2002, Yoann Padioleau wrote: > > > Koen Claessen <koen(a)cs.chalmers.se> writes: > > > > i find your idea very good. > > indeed for the library GetOpt, the argument of a program never change so it > > make sense to make this library without using IO monad, same for argv and for the enviroment. > > > for openFile it seems harder, it would require to have a lock on the file > > to be sure that no one modify the file, same for a webpage. > > > > No, not at all. All that is required is to make sure all calls to openFile > f returns the same string, i.e the contents of the file when it was read > the first time. yes you are right. but it requires to change the name of the function to have Once appended to it. so in the Prelude, we should have 2 version of the same kind of fonction, one pure such as readFileOnce with a cool type, and one such as readFile with an Io type. Sounds good idea to me, cos many programs require just to read a file one time. i dont know if practically it is useful. after all we can do all the IO stuff in the main, and then continue in a pure world. dont know if it is useful to read a file in the middle of a pure function. > > /Lars L > > > -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**

1 0

Re: Pure File Reading (was: Dealing with configuration data)
by Yoann Padioleau 26 Sep '02

26 Sep '02

Koen Claessen <koen(a)cs.chalmers.se> writes: i find your idea very good. indeed for the library GetOpt, the argument of a program never change so it make sense to make this library without using IO monad, same for argv and for the enviroment. for openFile it seems harder, it would require to have a lock on the file to be sure that no one modify the file, same for a webpage. > Dear all, > > At the moment, a discussion on haskell-cafe is going on > about how to neatly program the fact that an entire program > depends on a number of parameters that are read in once at > the beginning of a program. > > The suggestion that many people came up with was using > unsafePerformIO in the beginning to read the file. Here is > my version of that: > > | data Configuration = ... -- config data > | > | getConfig :: Configuration > | getConfig = unsafePerformIO $ > | do ...read configuration from file... > | return configuration > | > | main = > | do doStuff > > It is quite disturbing that there is no other easy way to do > this than using unsafePerformIO (except for using implicit > parameters perhaps, but there are other reasons for not > using those). > > I have been thinking a little bit more about this and here > is what I found. > > Remember the Gofer days, when Gofer had a "function": > > openFile :: FilePath -> String > > This was of course a cheap and dirty way of implementing > things like the getConfig above, but it is impure. However, > one could imagine a functional version of this function: > > readFileOnce :: FilePath -> Maybe String > > This function will read the contents of the file (and return > Nothing if something went wrong), but it is memoized, so > that the second time you use this function you get the same > result. > > So, it is a pure function. (Admittedly, it is somewhat > unpredictable, but you will always get the same result for > the same arguments.) It is no more strange than GHC's pure > version of the getArgs function (I forgot what it was/is > called). > > How about space behavior, you say? Reading a file, and > memoizing the result means storing the whole contents of the > file in memory! > > The point is that the use of this function will typically > happen at the beginning of a program, when reading the > configuration file(s). When all this has happened, the > function readFileOnce, and its memo table, will be garabage > collected. (Of course there is no guarantee that all calls > to readFileOnce will be evaluated at the beginning of a > program, and it is not required, but when you do, there are > no space problems.) > > There could of course be pure "-Once" versions of other IO > operations. Here is a list of possibilities: > > - reading a file > - getting arguments > - getting environment variables > - downloading a webpage > - ... > > What do you think? > > Regards, > /Koen. > > -- > Koen Claessen > http://www.cs.chalmers.se/~koen > Chalmers University, Gothenburg, Sweden. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**

2 1

CFP: Special Session and Journal Issue
by Dr. M. Sarfraz 26 Sep '02

26 Sep '02

>>>>>SORRY for DUPLICATES<<<< ==================================== Special Session on Computer Aided Geometric Design and Modeling ==================================== IN WSCG International Conference in Central Europe ------------------------------------------------ Call for Papers & Participation =============================== Please, VISIT http://wscg.zcu.cz for detailed information and for on-line papers repository since 1992 - 2002 Access is NOT LIMITED -------------------------------------------------------------------------------- Unique opportunity ------------------ - to visit the Golden City - PRAGUE - to take a part at event, where West and East meet ----------------------------------------- Aceepted papers will be published in The Journal of WSCG Vol. 11. No 1-3, ISSN 1213-6972 W S C G ' 2003 The 11-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2003 in co-operation with EUROGRAPHICS to be held at the University of West Bohemia, Plzen, close to Prague - the Golden European City Czech Republic February 3 - 7, 2003 Honorary Chair Jack E.Bresenham, Winthrop University, USA Programme Co-Chairs Dirk Bartz, University of Tübingen, Germany Vaclav Skala, University of West Bohemia, Czech Republic Keynote speakers: Gabor T. Herman: Blobs for Representing and Visualizing 3D Objects, City University of New York, USA Dirk Bartz: Large Model Visualization: Techniques and Applications, University of Tuebingen, Germany ====================== Topics included ====================== o Curve and Surface Design o Visualization o Computer Graphics o Geometric Modeling o Geometric Algorithms o Manufacturing Geometry o Computational Geometry o Reverse Engineering o Solid Modeling o Computer Aided Design (CAD) o Computer Aided Manufacturing (CAM) o Font Design o Multiresolution Methods o Geometric Transformations o Mesh Processing o Shape Abstraction and Modeling o Shape Analysis and Description o Industrial Applications The International Program Committee and Reviewing Board members review all papers peer-to-peer carefully and anonymously. Selected papers will be published in the Journal of WSCG, Vol.11. ISSN 1213-6972, all presented papers will be published in the WSCG proceedings with ISBN. Both are indexed/abstracted in: Engineering Index, Inspec Database, CompuMath Citation Index, Information Science Abstracts, Cambridge Scientific Abstracts and others. Information for authors Deadline for contributions: October 10, 2002 24:00 GMT (London time) -------------------------------------------------------------------- Format A4 (strictly), max. 8 pages, additional material (video as MPEG, AVI and similar files, color plates etc. can be submitted, please, no video tapes) up to 5 MB ================ IMPORTANT: ================ For details, please, see http://wscg.zcu.cz select WSCG'2003. After electronic submission, please report to: The Session Organizer =================================== Dr Muhammad Sarfraz Department of Information and Computer Science King Fahd University of Petroleum and Minerals KFUPM # 1510, Dhahran 31261 Saudi Arabia. Tel: +966-3-860-2763 Fax: +966-3-860-1562 Email: sarfraz(a)ccse.kfupm.edu.sa Email: sarfraz(a)kfupm.edu.sa WWW: http://www.ccse.kfupm.edu.sa/~sarfraz/

1 0

RE: Haskell 98
by Simon Marlow 25 Sep '02

25 Sep '02

> Out of curiousity, it's a bit strange that > > > data D = D !Int > > myD = D {} > > in invalid, but > > > newtype N = N !Int > > myN = N {} > > is not. The second example is also invalid: the newtype declaration is disallowed by the grammar. (incedentally, it looks like this example triggers a bug in nhc98). Cheers, Simon

1 0