- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results]
by Greg Buchholz 30 Sep '04

30 Sep '04

Sam Mason wrote: > > You probably want some strictness annotations in there. . . Now we're getting somewhere. When I replace the tuples with my own (strict) data structure, it gets about 7.5 times faster than the original shootout example (or about 24 times faster than the version with tuples). I get another 2x speedup when I pass '+RTS -G1' to the executable. So the version below is about 15 times faster than the original using the 3MB data file from the shootout. (Now we're only about 40x slower than ocaml). Don't forget to turn on '-funbox-strict-fields' for an additional improvement. -- Compile with... -- ghc -O2 -ddump-simpl -fvia-c -funbox-strict-fields -o wc_fold2 wc_fold2.hs -- execute as... ./wc_fold2 +RTS -G1 <input.txt import IO main = do file <- getContents putStrLn $ show (foldl wc (St 0 0 0) file) data Stuple = St !Int !Int !Int deriving Show wc (St l w c) '\n' = St (l+1) w (c+1) wc (St l w c) ' ' = St l (w+1) (c+1) wc (St l w c) x = St l w (c+1) ...It still seems like it's using a lot of memory (or at least doing a lot of garbage collecting). But it it still vastly better than before. Is there any way to reduce this more? (60,000,000 bytes divided by 3,000,000 chars = 20 bytes per char). Here's the memory usage report... 61,387,752 bytes allocated in the heap 11,837,148 bytes copied during GC 99,780 bytes maximum residency (234 sample(s)) 234 collections in generation 0 ( 0.11s) 1 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 0.15s ( 0.15s elapsed) GC time 0.11s ( 0.14s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.26s ( 0.29s elapsed) %GC time 42.3% (48.3% elapsed) Alloc rate 409,251,680 bytes per MUT second Productivity 57.7% of total user, 51.7% of total elapsed Greg Buchholz

1 0

RE: Simple example using Parsec (was: [Haskell-cafe] Rethinking O O idioms)
by Bayley, Alistair 30 Sep '04

30 Sep '04

Sure. Learning Parsec took me a few hours, whereas John's parsing task might be done in much less time, if it's simple enough. OTOH, there's value in being able to use Parsec, so it's a good excuse to learn. > -----Original Message----- > From: Graham Klyne [mailto:GK@ninebynine.org] > Sent: 30 September 2004 10:34 > To: Bayley, Alistair; 'John Goerzen'; haskell-cafe(a)haskell.org > Subject: Simple example using Parsec (was: [Haskell-cafe] > Rethinking OO idioms) > > At 09:01 30/09/04 +0100, Bayley, Alistair wrote: > >Ben suggested using Parsec for reading the config file. > Parsec is a fine > >library, but there is a learning curve, and you might find > it quicker to do > >the parsing yourself, if it's very simple. Your call. > > Hmmm... Parsec *can* be simple too. Here's one I did earlier: > http://www.ninebynine.org/Software/HaskellUtils/RegexParser.hs > > #g ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

Simple example using Parsec (was: [Haskell-cafe] Rethinking OO idioms)
by Graham Klyne 30 Sep '04

30 Sep '04

At 09:01 30/09/04 +0100, Bayley, Alistair wrote: >Ben suggested using Parsec for reading the config file. Parsec is a fine >library, but there is a learning curve, and you might find it quicker to do >the parsing yourself, if it's very simple. Your call. Hmmm... Parsec *can* be simple too. Here's one I did earlier: http://www.ninebynine.org/Software/HaskellUtils/RegexParser.hs #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Seeking reference(s) relating to FP performance
by Graham Klyne 30 Sep '04

30 Sep '04

I've taken it as an article of faith that performance of FP language implementations has been improving quite steadily over the past few years. I'd like to assert this, but I can't find any clear evidence to support such an assertion. I note that the "about Haskell" page makes a similar assertion, but it doesn't offer any hint of supporting evidence: [[ Aren't functional programs very slow? They used to be, but the compilers have now caught up. Haskell programs run fast enough for all but the most performance-demanding applications. ]] -- http://www.haskell.org/aboutHaskell.html I'm looking for a reference -- informal will be enough -- that can give an perspective of progress in functional language implementation performance. I'm not looking for a single benchmark that shows a case of blindingly-fast functional code, but a pointer to trends of improving performance. It would also serve my purpose to have indications based on languages other than Haskell (e.g. ML and friends). Any ideas, please? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 3

RE: [Haskell-cafe] Rethinking OO idioms
by Bayley, Alistair 30 Sep '04

30 Sep '04

There are three pieces to this story: - read a config file into some structure - query/modify elements of that structure - write structure out to a file Create a data structure (analogous to a class with no methods) and functions to query/manipulate that structure. Nested FiniteMaps might be a good, simple, first attempt. Unlike the functions to read and write the file (which must be in the IO monad), the functions to query and manipulate the structure can (and probably should) be non-monadic. Ben suggested using Parsec for reading the config file. Parsec is a fine library, but there is a learning curve, and you might find it quicker to do the parsing yourself, if it's very simple. Your call. > ... Haskell has no mutable variables. A call like > config.setOption("main", "initpath", "/usr") in Python -- which alters > the state of the config object and returns nothing -- would be > impossible in Haskell (unless perhaps the FiniteMaps are mutable > somehow?) When you "modify" a structure, you return a new copy of it, where the bit that you wanted to change is replaced by the new value. For example, this is what happens when you call addToFM/delFromFM for FiniteMaps. This isn't necessarily as expensive as it sounds, as there's a lot of data sharing going on in Haskell programs, due to the fact that everything /is/ immutable. If it does turn out to be too expensive, then you could look at using a state monad. But assuming you need one immediately looks like premature optimisation to me. Alistair. ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

Rethinking OO idioms
by John Goerzen 30 Sep '04

30 Sep '04

I've worked with languages with object-oriented features for awhile now. Python and OCaml, the two with which I work the most, both have OO. One of my first projects in Haskell would be to write a Haskell version of Python's ConfigParser[1] class. I wrote[2],[3] a version of this for OCaml that works very well. In a nutshell, ConfigParser is a utility for working with sectioned configuration files in a style similar to the familiar .ini files from Windows. It has methods to read a configuration file, get/set the items that are being configured, and write a new file back out. This, then, is a fairly typical metaphor for OO programs: an instance of a class has some state that can be accessed or modified, and possibly stored and retrieved. So I am thinking about a ConfigParser for Haskell. The first thing that occured to me is that Haskell has no OO features, so I'm not sure what is the best way to handle the "class" and its various methods. The next thing that occured to me is that, unlike OCaml and Python classes, Haskell has no mutable variables. A call like config.setOption("main", "initpath", "/usr") in Python -- which alters the state of the config object and returns nothing -- would be impossible in Haskell (unless perhaps the FiniteMaps are mutable somehow?) I guess I'm having trouble translating this common OO language paradigm into the Haskell world. Thanks for any insight. -- John BTW, if I get a working ConfigParser for Haskell, I will publish it under the GPL like all the rest of my code. [1] http://www.python.org/doc/current/lib/RawConfigParser-objects.html [2] http://gopher.quux.org:70/devel/missinglib/html/ConfigParser.html [3] http://gopher.quux.org:70/devel/missinglib/html/ConfigParser.rawConfigParse…

8 9

Re: OCaml list sees abysmal Language Shootout results
by Aaron Denney 30 Sep '04

30 Sep '04

On 2004-09-29, Tomasz Zielonka <t.zielonka(a)students.mimuw.edu.pl> wrote: > I remember SPJ's motto: ,,Avoid success at all cost''. Is this motto > still valid? Maybe. The existing user-base is being used as an argument for not "doing the right thing" with regards to binary-IO, strings, localization and text IO. -- Aaron Denney -><-

1 0

Question about function on data type
by Peter Robinson 30 Sep '04

30 Sep '04

Hello! My question concerns a general term datatype: data Term = Not Term | Term :&&: Term | Term :||: Term | Literal Char Is it somehow possible to write a generic function that applies the associativity rules on a "Term" (by using pattern matching) and works with both data constructors or is it necessary to write one for :&&: and :||: ? Something like: assoc :: Term -> Term assoc ((t1 `op` t2) `op` t3) = .... -- this doesn't work Regards, Peter

2 1

Strings - why [Char] is not nice
by Einar Karttunen 29 Sep '04

29 Sep '04

Hello Strings in haskell seem to be one major source of problems. I try to outline some of the problems I have faced and possible solutions. Size Handling large amounts of text as haskell strings is currently not possible as the representation (list of chars) is very inefficient. Serialization Most of the time when serializing a string, we want to handle it as an array of Word8. With lists one has to account for cycles and infinite length which make the encoding much more verbose and slow. The problem is not that some strings may not be trivially serializable, but rather that it is hard to find the easy cases. Typeclass instances It is currently hard to define typeclass instances for strings as String ( = [Char]) overlaps with [a]. Implementations provide solutions for this, but there should not be a need for workarounds in the first place. Show/Read The current Show/Read implementation makes it impossible to use with large strings. A read implementation needs to traverse the file looking for the terminating '"' and handling escape codes. A better solution would be to have an efficient (size prefixed) representation, maybe in a separate Serializable typeclass. But this would need the ablity to derive Serializable instances for algebraic datatypes automatically to avoid lots of useless code. Possible solutions The optimal solution should be compact and fast. A list of chunks is one solution - it would make it possible to e.g. mmap files (modulo encoding) and support fast concatenation. In addition one would need to support infinite and cyclic structures. Adding an alternative which corresponds to the current string abstraction would be sufficient. type CharT = Word8 data Str = S [(Ptr CharT, Int)] | I [CharT] A major problem is breaking old code. The main problem is that many functions are defined only on lists which forces strings to be lists. Making the functions polymorphic would solve a lot of problems and not only for Strings. There should be no performance penalty (at least in theory) when the compiler knows which instance is used at compile time. - Einar Karttunen

5 7

k-th floorRoot
by fool＠sdf-eu.org 29 Sep '04

29 Sep '04

Hi. > floorRootDef, floorRoot :: Integer -> Integer -> Integer > > floorRootDef k n | k>=1 && n>=1 = last (takeWhile (\x->x^k<=n) [1..]) > > floorRoot k n | k>=1 && n>=1 = h n where > h x = let y=((k-1)*x+n`div`x^(k-1))`div`k in if y<x then h y else x (Oddly enough, you get an iteration formula for the _floor_ of the k-th root just by putting _floor_ brackets around every quotient in Newton's iteration formula for the k-th root.) Exercise: Transform floorRootDef into floorRoot by extensional-equality-preserving steps. I don't know how to do this. To conventionally prove the correctness of floorRoot, it suffices to show for all integers k>=1, n>=1, x>=1, y:=[((k-1)*x+[n/x^(k-1)])/k], r:=[n^(1/k)] ([] denoting floor): (1) r<=y (so r<=x is preserved in the iteration) and (2) x<=y --> x<=r (so r<=x<=r when the break condition is met). Using a<=[b] <--> a<=b for all integers a and reals b, (2) is straightforward and (1) is equivalent to k*r-(k-1)*x <= n/x^(k-1), which by r^k<=n can be sharpened to (3) k*(r-x)+x <= r^k/x^(k-1), which is true by induction over k if (3) implies k*(r-x)+x + r-x <= r^k/x^(k-1) * r/x, which indeed by (3) can be sharpened to k*(r-x)+r <= (k*(r-x)+x)*r/x, equivalently (multiply by x and collect terms) 0 <= k*(r-x)^2, done. -- fool(a)sdf-eu.org SDF-EU Public Access UNIX System - http://sdf-eu.org

1 0