- Haskell-Cafe - Haskell.org

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 29 Sep '04

29 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 29 Sep '04

29 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

Silly I/O question
by John Goerzen 29 Sep '04

29 Sep '04

I'm trying to write a program that will copy an arbitrarily large text file to a destination, and duplicate it 100 times. Thus: ./myprog < Input > Output would be the same as running: cat Input > Output # once cat Input >> Output # 99 times My first attempt was this: import IO main = disp 100 disp 0 = return () disp n = do c <- getContents putStr c hSeek stdin AbsoluteSeek 0 disp (n-1) That failed, though, because getContents closes the file after it's been completely read (ugh -- why?). So then I tried to work on various options around hGetLine and hPutStrLn. But I couldn't figure out a way to make this either properly tail-recursive while handling the exception, or to avoid polling for EOF each time through the function. I also don't want to store the entire file in memory -- the idea is to seek back to the beginning for each iteration. I'm assuming that stdin is a seekable fd. I checked the wiki for a pattern here but didn't see any. Suggestions?

5 7

GHC and OS X (10.4)
by Tom Davie 28 Sep '04

28 Sep '04

Hi, I've been attempting to use GHC on a beta copy of Mac OS X 10.4, I've been attmepting to use the panther version of the install package, but have hit a problem with tinkering with it - I get the following error when I attempt to run ghc: Verenia:~/Documents/Development/XBridgeAI tatd100$ ghc dyld: Library not found: HaskellSupport.framework/Versions/A/HaskellSupport Referenced from: /usr/local/lib/ghc-6.2.1/ghc-6.2.1 Reason: file not found Trace/BPT trap The framework is present in /Library/Frameworks, and /Library/Frameworks is in dyld's framework search path. Any Mac/Haskell gurus able to help I would much appreciate it. Thanks Tom Davie

2 2

Optmiization of recursion
by John Goerzen 28 Sep '04

28 Sep '04

Hello, As I'm investigating Haskell, it's occured to me that most of the Haskell tutorials out there have omitted something that was quite prominent in the OCaml material I had read: making functions properly tail-recursive. The OCaml compiler was able to optimize tail-recursive functions such that they could be compiled using a loop. This would achieve two main benefits: performance due to not needing to allocate/deallocate stack frames, and the ability to work on very large lists since each recursive call did not consume extra stack space. So I have several questions about Haskell: 1. Do Haskell interpreters/compilers perform similar optimizations? 2. If the answer to 1 is No, then am I correct in saying that my ability to handle very large lists in recursive functions is limited by the maximum stack size on my system? 3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? 4. Is a reference available documenting which Prelude/standard functions are properly tail-recursive (and thus suitable for very large lists) and which are not? (OCaml system docs generally specify when a function is not tail-recursive... for instance, one of foldr/foldl is and the other isn't.) 5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? Thanks!

7 8