- Haskell - Haskell.org

Re: More Unicode nit-picking
by Marcin 'Qrczak' Kowalczyk 19 Oct '01

19 Oct '01

19 Oct 2001 06:09:09 +0100, Colin Paul Adams <colin(a)colina.demon.co.uk> pisze: > 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. Indeed, but there exists a default locale-independent case mapping. Language-specific mappings and irregular cases are described as deviations from it. > 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. Yes. > what should the primUnicodeToLower/ToUpper operations actually do? > Should they be locale sensitive? I don't think so: they are pure functions, so IMHO they should have a definition independent from the environment. Especially as a proper case mapping requires mapping a character to a few characters sometimes, so a more exact definition would require a different interface: either String -> IO String or IO (String -> String), perhaps taking the locale into account explicitly. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

list comprehension
by Stephanie Randles 19 Oct '01

19 Oct '01

Hi, I have a script here interleave :: [Integer] -> [Strings] -> [String] interleave (x:xs) (y:ys) = words [a | a <- (unwords [(show x), (filter (/= 1) y), "+"])] and the error message i receive is (Instance of Num Char required for definition of interleave) and I don't understand what this is asking of me. Please help if you are able to!!! Thanks.....Steph

3 2

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