October 2001 - Haskell

Re: Working character by character in Haskell
by Malcolm Wallace 19 Oct '01

19 Oct '01

"Simon Marlow" <simonmar(a)microsoft.com> writes: > > Well, in Haskell each character of the string takes 20 bytes: 12 bytes > > for the list cell, and 8 bytes for the character itself Ahem, _Haskell_ mandates no such thing. Perhaps you are talking about a specific implementation? ghc probably. > Isn't it possible to optimize this, e.g. by embedding small data > directly in the cons cell? I believe Hugs does at least part of this - ASCII characters and small ints < 256 are embedded in the tag word, so a character takes only 4 bytes, not 8. In addition, some implementations distinguish pointers and small values by tags, so the character can appear literally in the list cell, rather than needing a pointer and separate allocation. Hence some implementations only require 12 bytes per list cell + character, not 20. Regards, Malcolm

1 0

Re: Large lists, heaps, stacks...
by Steinitz, Dominic J 19 Oct '01

19 Oct '01

Have you looked in the list library? partition or groupBy may be what you want. Dominic. ------------------------------------------------------------------------------------------------- To receive our special fares directly by email, register at http://www.britishairways.com/registration

1 0

More Unicode nit-picking
by Colin Paul Adams 19 Oct '01

19 Oct '01

I have accidentally noticed another problem in the revised Haskell report (actually the library report, this time). in module Char, toLower and toUpper appear to be under-specified (and indeed, the whole module looks a little suspect) Exactly what is wrong with them I find hard to say, and even harder to say what the cure should be, nevertheless: Firstly: "This module offers only a limited view of the full Unicode character set; the full set of Unicode character attributes is not accessible in this library." I take it this implies that operations in this module apply to the ENTIRE Unicode character set, so: "Function toUpper converts a letter to the corresponding upper-case letter, leaving any other character unchanged. Any Unicode letter which has an upper-case equivalent is transformed. Similarly, toLower converts a letter to the corresponding lower-case letter, leaving any other character unchanged." But this seems to assume there is a one-to-one mapping of upper-case to lower-case equivalent, and vice-versa. Apparently this is not so. (I'm only going on hearsay - something I saw on the xml-dev list yesterday - I haven't checked any of this). It seems that whilst the Unicode database's definitions of whether or not a character is upper/lower/title case are normative, the mappings from upper to lower case are only suggestive. This is because it depends upon language conventions as to how the mapping is done. In Turkish for instance, I is not the upper-case equivalent of i, and vice-versa (apparently there is a dotted i, and a non-dotted i, and likewise for I). So it would seem that the definitions: "-- Case-changing operations toUpper :: Char -> Char toUpper = primUnicodeToUpper toLower :: Char -> Char toLower = primUnicodeToLower" just beg the question - what should the primUnicodeToLower/ToUpper operations actually do? Should they be locale sensitive? -- Colin Paul Adams Preston Lancashire

2 1

Re: Large lists, heaps, stacks...
by Janis Voigtlaender 19 Oct '01

19 Oct '01

Till Doerges writes: > select' :: [a] -> [Integer] -> ([a],[a]) > select' xs poss = sAcc xs (sort poss) 0 ([],[]) > where sAcc :: [a] -> [Integer] -> Integer -> (([a],[a]) -> ([a],[a])) > ... > > Crash> select' "test" [0..] > > (35922 reductions, 63905 cells) > ERROR: Control stack overflow > ... > > 2) Why does "select' "test" [0..]" not work? > You are trying to *sort* the *infinite* list poss=[0..]. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

1 0

Re: Working character by character in Haskell
by Andre W B Furtado 19 Oct '01

19 Oct '01

Humn... I agree with both of you, Albert and Tom. I started it from the beginning, using map and don't using reverse anymore. But the C program is still 7x faster than the Haskell one. Here is the code of the Haskell program: main :: IO () main = do bmFile <- openFileEx "in.txt" (BinaryMode ReadMode) bmString <- hGetContents bmFile writeFile "out.txt" (map inc bmString) hClose bmFile inc :: Char -> Char inc a = toEnum ((fromEnum a) + 1) And now the C program: #include <stdio.h> void main() { FILE *in, *out; char ch; in = fopen("in.txt","rb"); out = fopen("out.txt","wb"); while ( (ch=getc(in)) != EOF) putc(ch + 1,out); fclose(out); fclose(in); } As you noticed, the main idea here is to increment the character by "one". Is the Haskell program now a nice translation of the C program? If it is (I think so...) why is the C program so much faster than it? Thanks again, -- Andre ----- Original Message ----- From: Albert Lai <trebla(a)vex.net> To: <glasgow-haskell-users(a)haskell.org> Sent: Thursday, October 18, 2001 9:42 PM Subject: Re: Working character by character in Haskell > "Andre W B Furtado" <awfurtado(a)uol.com.br> writes: > > [...] > > > For example, suppose function doSomeStuffWith returns its own parameter. > > Using a 1.5MB file in this case, the Haskell program ends in almost 5 > > seconds, while the C program ends in less than 0.5 seconds... Is my Haskell > > program too bad implemented? (I'm using GHC 4.08-1 under a Windows 98 > > platform.) > > I indeed think that your Haskell program is inefficient and is not a > translation of your C program. It reverses a huge string, which takes > not only execution time but also garbage collection time and memory, > which entails even more time for OS overhead and swapping out other > things in the physical memory. > > (Many programmers complain "my linear-time algorithm takes just 1 > second on a 100M list, so why is it taking 5 seconds on a 200M list?" > They forget that because of issues such as cache locality and virtual > memory, their computers do not scale.) > > I am wondering that if doSomeStuffWith is pure-functional, why are you > writing and using copyFile instead of just using map? I mean: > > main :: IO () > main = do > bmFile <- openFileEx "in.txt" (BinaryMode ReadMode) > bmString <- hGetContents bmFile > writeFile "out.txt" (map doSomestuffWith bmString) > hClose bmFile > > Because both hGetContents and map are lazy and use O(1) memory, this > program behaves exactly as your C program plus occasional garbage > collections that don't hurt too much. In partcular, the OS will see > no difference (although the cache does).

1 0

Working character by character in Haskell
by Andre W B Furtado 18 Oct '01

18 Oct '01

I'm trying to create a fast program in Haskell that reads the content of a file, do some stuff with its characters (one by one) an then save the final result (the modified characters) in another file. The fastest program I've developed so far is: main :: IO () main = do bmFile <- openFileEx "in.txt" (BinaryMode ReadMode) bmString <- hGetContents bmFile str <- copyFile bmString [] writeFile "out.txt" str hClose bmFile copyFile :: String -> String -> IO String copyFile [] s = return (reverse s) copyFile (a:as) s = copyFile as ( (doSomeStuffWith a):s) What I can't understand is why a similar program, written in C, is much faster than the Haskell program. Here you have the C program: void main() { FILE *in, *out; char ch; in = fopen("in.txt","rb"); out = fopen("out.txt","wb"); while ( (ch=getc(in)) != EOF) putc(doSomeStuffWith(ch),out); fclose(out); fclose(in); } For example, suppose function doSomeStuffWith returns its own parameter. Using a 1.5MB file in this case, the Haskell program ends in almost 5 seconds, while the C program ends in less than 0.5 seconds... Is my Haskell program too bad implemented? (I'm using GHC 4.08-1 under a Windows 98 platform.) Thanks, -- Andre

2 1

Constructor class
by Raul Sierra 18 Oct '01

18 Oct '01

Hi all, What is the difference between regular classes and constructor classes and how do you specify that a class is a constructor class? Thanks in advance, Raul

2 1

Large lists, heaps, stacks...
by Till Doerges 18 Oct '01

18 Oct '01

Hi everybody, I'm having to deal w/ rather long(*) lists. Unfortunately I stumbled across some problems in the process. I tried to implement a function that separates a list into two parts according to a list of indices given. (Does anything like that perhaps exist already in the Prelude?) --- snip --- -- Put elems at specified positions in 2nd list. -- Non-existant positions will be ignored. -- The order of the input list won't be altered. select :: [a] -> [Integer] -> ([a],[a]) select xs poss = sAcc xs (sort poss) 0 ([],[]) where sAcc :: [a] -> [Integer] -> Integer -> ([a],[a]) -> ([a],[a]) sAcc [] _ _ (ys,zs) = (ys,zs) sAcc xs [] _ (ys,zs) = (ys++xs, zs) sAcc (x:xs) (pos:poss) curpos (ys,zs) = if (pos == curpos) then sAcc xs poss (curpos+1) (ys, zs++[x]) else sAcc xs (pos:poss) (curpos+1) (ys++[x], zs) --- snap --- Calling a function like the following one, will result in a segfault both under Linux (2.4.7) and Solaris (2.8) w/ hugs-feb-2000. --- snip --- Crash> select [0..500000] [0,1,2,20,418,451596,451616] ( (11290502 reductions, 22129474 cells) Segmentation Fault --- snap --- I suspect it's the (++) that's causing problems here and that it's filling up my C-stack (like stated at http://www.cse.ogi.edu/PacSoft/projects/Hugs/pages/bugsandfeatures.htm) So I tried rewriting the function in order to get rid of the (++). --- snip --- -- Hopefully better implementation of select. select' :: [a] -> [Integer] -> ([a],[a]) select' xs poss = sAcc xs (sort poss) 0 ([],[]) where sAcc :: [a] -> [Integer] -> Integer -> (([a],[a]) -> ([a],[a])) sAcc [] _ _ = trace "hi1" $ id sAcc xs [] _ = trace "hi2" $ (\ (ys,zs) -> (ys++xs,zs)) sAcc (x:xs) (pos:poss) curpos = if (pos == curpos) then (\ (ys,zs) -> ( ys,x:zs)) . (sAcc xs poss (curpos+1)) else (\ (ys,zs) -> (x:ys, zs)) . (sAcc xs (pos:poss) (curpos+1)) --- snap --- Now, something like the above --- snip --- Crash> select' [0..500000] [0,1,2,20,418,451596,451616] (138397 reductions, 244907 cells) ERROR: Control stack overflow --- snap --- will not segfault, but it'll give me a control stack overflow. (Better than a segfault, but still rather undesirable). A second point I discovered is this one: --- snip --- Crash> select' "test" [0..] (35922 reductions, 63905 cells) ERROR: Control stack overflow --- snap --- Instead of just giving me '("","test")'. I considered this case being taken care of by the first pattern in sAcc. Obviously it isn't. So my questions are: 1) Could anybody please explain the behaviour of select and select' to me? To add the icing on the cake: How can I improve select? 2) Why does "select' "test" [0..]" not work? I hope my questions aren't too silly. Any hints would be greatly appreciated. Thanks -- Till (*) At the moment "rather long" means approx. 500,000 elems. But perhaps I'll need even more elements in a list. -- e-mail: reverse(net dot doerges at till) | ENCRYPTED | pgp/gpg: keys via keyserver or my homepage | MAIL IS | www: http://www.doerges.net | WELCOME! |

1 0

final test: Research Job in Compositional Reasoning and Analysis @ Heriot-Watt Univ., Scotland, UK
by Joe Wells 18 Oct '01

18 Oct '01

Research Position Useful Logics, Types, Rewriting, and their Automation (ULTRA) Group Computing and Electrical Engineering Department Heriot-Watt University Edinburgh, Scotland, UK Description of the Position A research position is available on an EC-funded project working under the supervision of Joe Wells. The position is in the ULTRA (Useful Logics, Types, Rewriting, and their Automation) group in the Department of Computing and Electrical Engineering at Heriot-Watt University in Edinburgh, the capital of Scotland. The work will be done in close coordination with the DART (Dynamic Assembly, Reconfiguration, and Type-checking) consortium (Genova Univ., HWU, Imperial Coll., and Torino Univ.) as well as the Church Project (Boston Coll., Boston Univ., Harvard Univ., HWU, Wellesley Coll., etc.). The researcher will probably help with some of the following tasks: * Designing new type systems for compositional (modular) analysis of systems that may involve one or more aspects of concurrency, mobility, modularity, objects, run-time code generation, etc. * Designing analysis algorithms for the new type systems. * Designing theories (e.g., "calculi") for reasoning about the meaning of dynamic software assembly, i.e., doing in a non-traditional order one or more of type checking, code generation, linking, loading, etc. * Making software systems incorporating the new type systems, algorithms, and calculi. * Writing scientific reports on the work done. The position is initially for 1 to 2 years, with extensions up to 3 years total possible depending on salary, experience, performance, and funding. Applications to spend a shorter period (e.g., the sabbatical leave of an established academic) will be considered, but the research area is pretty much predetermined. The salary will be commensurate with qualifications and experience in the range from 21290 GBP to 26229 GBP per year. It is preferred that the researcher will start in the period from 2002-01-01 to 2002-03-01. It is preferred that before starting the researcher will have completed a Ph.D. in a relevant discipline within Computer Science. Applicants from outside the European Economic Area (EEA) will be considered. The researcher will probably use some of the following knowledge areas: * Formal calculi for reasoning about the meaning of computer systems (including computer programs), especially those with aspects of (a) modules, linking, and loading, (b) concurrency, (c) mobility, (d) staged compilation, (e) objects, (f) resource usage, etc. * Analysis of systems represented in formal calculi. * Constraint solving and unification. * Type systems, especially those with intersection and union types. * Programming languages used for any of the above. Applying for the Position To formally apply for this position, please do the following before the closing date of 2001-11-02: * Arrange for 3 letters of reference to be sent as soon as possible. If (by mistake) someone tells you the letters are not needed yet, please have the letters sent anyway, because no one will be chosen for an interview until after we see the letters. See below for what we hope to see in a letter of reference. * Send the following yourself as soon as possible: + your complete curriculum vitae, + a brief statement (one paragraph is enough) explaining why you think your research accomplishments and interests would be a good match for the job, + web pointers to or paper copies of from 0 to 3 publications of yours which you think are relevant, and + contact details for the people writing your letters of reference. * Contact the Heriot-Watt Personnel Office and get them to send you an "application pack". This contains an application form, an equal opportunities monitoring form, information for applicants with disabilities, and some additional information about Heriot-Watt and the position. * Fill out and return the application form and the equal opportunities monitoring form. (If your curriculum vitae is well constructed, then some of the information requested on the application form will be redundant, in which case it is reasonable to just write "see c.v." in the blanks.) * Although not required, it will be appreciated if you inform Joe Wells as soon as possible that you are applying so that he knows to ask our personnel office for your application materials immediately after they arrive. * Anyone who might need a work permit if hired (usually someone who is not a citizen of an EEA country) should also do the following. In addition to possibly being e-mailed or faxed, each letter of reference should also be sent by post on official-looking stationery paper and should include details on your whereabouts over the last two years. A work permit application also needs copies of any degree certificates, so it is a good idea to send those also. Please include the reference code 133/01/L in all communications to help prevent your application from getting mixed up. Please convert Microsoft Word documents to a public, standard, and non-proprietary format, e.g., PDF, HTML, or PostScript. PDF is best, because some of our staff will encounter difficulties with HTML or PostScript. Please ask the people writing letters of reference for you to include details of: * the capacity in which they know you, * your skills, abilities and performance in relation to the post applied for, * your employment record including details of your role and service dates, * your record in terms of attendance, timeliness, and discipline, * their view of your suitability for the post as a whole, in light of the attached details and their knowledge of your experience and abilities, * any further relevant information which would assist us in making an appointment. Informal inquiries should be directed to Joe Wells at: web: http://www.cee.hw.ac.uk/~jbw/ e-mail: jbw(a)cee.hw.ac.uk fax: +44 131 449 3834 Formal applications and/or requests for materials for completing a formal application should be directed to the Heriot-Watt Personnel Office at: web: http://www.hw.ac.uk/personnel/ e-mail: personnel(a)hw.ac.uk voice mail: +44 131 451 3475 fax: +44 131 451 3475 minicom: +44 131 451 8212 post: The Personnel Office Lord Balerno Building Heriot-Watt University EDINBURGH EH14 4AS GREAT BRITAIN

1 0

Re: Haskell 98 - Standard Prelude - Floating Class
by Marcin 'Qrczak' Kowalczyk 18 Oct '01

18 Oct '01

Thu, 18 Oct 2001 13:49:11 +0200, Karl-Filip Faxen <kff(a)it.kth.se> pisze: > There are two solutions that I can see: Annotate classes in class > constraints with exactly which methods were used. Thus for the > expression "x+y" the inference algorithm would record the constraint > "Num{+} a" if x and y has type a in the type environment. Then if > an instance declaration for type Wurble omitted +, that instance > declaration would not allow us to simplify "Num{+} Wurble". This is equivalent to putting all methods in separate classes. IMHO missing method definitions should be detected where the instance is defined, not when it's used. You can still define diverging methods explicitly or manually split the class if you really want partial instances. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0