September 2004 - Haskell-Cafe

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

Re: [Haskell-cafe] Re: Strings - why [Char] is not nice
by MR K P SCHUPKE 28 Sep '04

28 Sep '04

Can this not be handled in a nicer way by the compiler? What if the compiler tried to allocate the lists in chunks? For example when dealing with strings, why cant the compiler allocate the string as a fixed length unit, terminated with a link to the next unit. (IE allow the atoms in the list to be variable size). In this way functions which return blocks of data (for example reading a file in 8k buffers) can be treated just like reading a normal list. This would not only save memory, but would make IO more efficient, whilst retaining a Haskell-like style of coding. Keean.

1 0

Re: [Haskell-cafe] mutually recursive modules
by Henning Thielemann 28 Sep '04

28 Sep '04

On Fri, 24 Sep 2004, Malcolm Wallace wrote: > Hugs doesn't support mutually-recursive modules at all. Ghc and nhc98 > support them only if you hand-write a .hi-boot file to bootstrap the > compilation. I would guess that better support from the mainstream > implementations is unlikely, because it would be a large amount of > effort for a situation which occurs only very rarely, and for which > there is a relatively easy workaround. Namely? The only workaround I know of is putting all type declarations and functions that depend on each other into one module, import them in the modules they logically belong to and document that the objects should be imported from the redirecting modules rather than from the modules they are defined in. I know of two projects where different tasks had to be merged into one module because of the lack of mutually recursive imports, namely functionalMetaPost and Haskore. It's interesting how other languages solve this problem. In Modula-3 it is solved by explicit module interfaces and partial revelation. One can define type T in module A and type T in module B very abstractly as pointers to something and the complete data structures (which may contain references to either interface) are usually revealed in the implementations of the modules. I'm curious how Oberon solves it, because it doesn't need explicit interfaces but derives them from the implementation files. Probably one can say that Oberon extracts something like a .hiboot file from every module file automatically. Why can't GHC and Hugs go this way?

11 14

job ads I saw on DICE
by Christopher Milton 25 Sep '04

25 Sep '04

It is rare to see ads looking for Haskell programming experience... http://seeker.dice.com/jobsearch/servlet/JobSearch?op=1002&dockey=xml/6/2/6… http://seeker.dice.com/jobsearch/servlet/JobSearch?op=1002&dockey=xml/b/8/b…

1 0

Re: [Haskell-cafe] mutually recursive modules
by Malcolm Wallace 24 Sep '04

24 Sep '04

Henning Thielemann <iakd0(a)clusterf.urz.uni-halle.de> writes: > As far as can see neither Hugs or GHC really support them. Is this still > on the to-do list or is it almost dropped due to implementation > difficulties? Hugs doesn't support mutually-recursive modules at all. Ghc and nhc98 support them only if you hand-write a .hi-boot file to bootstrap the compilation. I would guess that better support from the mainstream implementations is unlikely, because it would be a large amount of effort for a situation which occurs only very rarely, and for which there is a relatively easy workaround. Some lesser-known Haskell implementations do fully support mutually-recursive modules however. hhc (formerly Freja, from Henrik Nilsson) allows multiple modules to be stored in a single file, and hence mutual recursion can be achieved by ensuring all the recursive modules are compiled simultaneously from the same file. The PacSoft Haskell system (from the Programatica project at OGI) also fully supports mutually recursive modules, and I believe they can even be in separate files. Regards, Malcolm

1 0

mutually recursive modules
by Henning Thielemann 24 Sep '04

24 Sep '04

As far as can see neither Hugs or GHC really support them. Is this still on the to-do list or is it almost dropped due to implementation difficulties?

1 0