September 2010 - Haskell-Cafe

Unnecessarily strict implementations
by Jan Christiansen 03 Sep '10

03 Sep '10

Hi, there is a new ticket that Data.List.intersperse is not as non-strict as possible (http://hackage.haskell.org/trac/ghc/ticket/4282) I have observed some other functions which are unnecessarily strict and it might be advantageous to change their definitions as well. I think it is known that the current implementations of inits and tails are too strict. At least I think I have once read a post to haskell-cafe about this topic. Furthermore intersect is too strict. We have intersect _|_ [] = _|_ and the current implementation is linear in the size of xs if we evaluate intersect xs []. I think simply adding a rule intersect _ [] = [] to the current implementation solves this issue. The implication (<=) :: Bool -> Bool -> Bool is too strict as well. We have False <= _|_ = _|_ as well as _|_ <= True = _|_ while one of these cases could yield True. The problem is that (<=) is defined by means of compare. This effect shows up for all data types with a least element if the default implementation of (<=) by means of compare is used. Furthermore there are a couple of functions which are too strict but whose minimally strict implementations do not provide benefits. For example, reverse is too strict as has already been observed by Olaf Chitil (http://www.cs.kent.ac.uk/people/staff/oc/Talks/ifl2006NonStrictProgramming.… ). Cheers, Jan

10 15

Ord instance of Bool (Was: Unnecessarily strict implementations)
by Henning Thielemann 03 Sep '10

03 Sep '10

Ivan Lazar Miljenovic schrieb: > On 3 September 2010 16:49, Henning Thielemann > <schlepptop(a)henning-thielemann.de> wrote: >> You might object, that it is seldom, that someone intentionally writes >> (a<b) if 'a' and 'b' are complex numbers. However imagine someone >> rewrites an algorithm for real numbers to complex numbers and he relies >> on the type system to catch all inconsistencies. The field operations >> can remain the same, but (<) has to be applied to results of 'abs', >> 'realPart' or other functions that yield a real. > > Fair enough, but on the other hand I don't think we should make a > fetish about enforcing _everything_ in the type system (non-empty > lists, etc.). I would like to express even more in type system. For instance I have recently invested several weeks for hunting space leaks in my code and I'm still not sure, I catched them all. A way to express absence of space leaks in the type system would save me a lot of time and would give me confidence. Regarding True=1 and False=0: Once I programmed in a language where True was represented by -1, because this is represented by bit pattern 1....1. The CPU has an instruction to fill a byte with the content of a flag and you can use this bit pattern for bitwise AND and OR operations. This makes this representation very efficient. This programming language also allowed comparison and conversion of True and False to their numeric representations. I used this intensively. Now imagine I port such programs to Haskell or C, I get lots of bugs for free.

1 0

Ord instance of Bool (Was: Unnecessarily strict implementations)
by Henning Thielemann 03 Sep '10

03 Sep '10

Henning Thielemann schrieb: > Ivan Lazar Miljenovic schrieb: >> On 3 September 2010 04:57, Arie Peterson <ariep(a)xs4all.nl> wrote: >>> On Thu, 2 Sep 2010 19:30:17 +0200, Daniel Fischer >>> <daniel.is.fischer(a)web.de> wrote: >>>> Why would one consider using Ord for Map an abuse? >>>> A kludge, for performance reasons, but an abuse? >>> Because it forces one to declare Ord instances for types which have no >>> natural ordering. It is useful to *not* have such instances, in order to >>> catch programming errors. >> What precisely do you mean by natural ordering? > > E.g. I wanted to have a Set of Gaussian (complex) integers, but I did > not want to define an Ord instance for them, because writing > a < (b :: Gaussian) > is a bug with high probability. I like to answer in advance to the objections that might come. :-) You might object, that it is seldom, that someone intentionally writes (a<b) if 'a' and 'b' are complex numbers. However imagine someone rewrites an algorithm for real numbers to complex numbers and he relies on the type system to catch all inconsistencies. The field operations can remain the same, but (<) has to be applied to results of 'abs', 'realPart' or other functions that yield a real.

1 0

Re: [Haskell-cafe] Unnecessarily strict implementations
by Alexander Solla 03 Sep '10

03 Sep '10

On Sep 2, 2010, at 11:35 PM, Henning Thielemann wrote: > But in the lattice example the roles of 0 and 1 are interchangeable, > aren't they? Sort of. If you try to interchange the roles of 0 and 1, you are interchanging the roles of the meet and join operations. In short, you are constructing the dual lattice. A mirror image is a good analogy for this construction. So, 0 and 1 are interchangeable. In the same way that "True" and "False" are. And "Top" and "Bottom". And "Left" and "Right". Arbitrary structurally, but with a history of consistency across domains.

1 0

On to applicative
by michael rice 02 Sep '10

02 Sep '10

This may be a dumb question, but here goes. Types Maybe, Either, List, are types and also instances of Functor (and Monad). Assuming (->) is also a type, where can I find its type definition? Michael

2 2

creating a type based on a string
by Andrew U. Frank 02 Sep '10

02 Sep '10

I have a user input (string) and need to select one of two types. depending what the input is. is this possible? data A data B data X n = X String op :: String -> X n op "a" = X "a" :: X A op "b" = X "b" :: X B this does obviously not compile. is there a way to achieve that the type X A is produced when the input is "a" and X B when the input is "b"? thank you for help! andrew

5 4

On to applicative
by michael rice 02 Sep '10

02 Sep '10

"Learn You a Haskell ..." says that (->) is a type just like Either. Where can I find its type definition? Michael

8 24

Re: [Haskell-cafe] ANNOUNCE: Haddock version 2.8.0
by David Waern 02 Sep '10

02 Sep '10

2010/9/2 Daniel Peebles <pumpkingod(a)gmail.com>: > Mmm, delicious! Thanks to all involved! Any idea how long it'll take for > this to make it to hackage and regenerate all the documentation up there? > It'd be wonderful to do the same to the GHC documentation too. I don't actually know yet if it's possible to regenerate the documentation on hackage. We're looking into the matter. David

1 0

Multicore speedup and spark conversion with ghc HEAD
by Eric Rannaud 02 Sep '10

02 Sep '10

Follows three runs of a stupid program that should see a speedup (I believe). 1. Compiled with ghc-6.12.3. Run on 1 thread, 4.0 s (real). 2. Compiled with ghc-6.12.3. Run on 2 threads, spark converted, 5.4 s (real), 7.7 s (user). 3. Compiled with ghc-6.13.20100831. Run on 2 threads, but spark *not* converted 4.1 s (real). All runs with disabled parallel GC, which negatively impacts -N2 runs (whether the spark is converted or not). Two questions: A. Why is run (2) slower than (1)? GC is a bit more expensive, as one would expect, but not enough to explain the difference (only explains 0.3 s). B. ghc HEAD doesn't convert the spark. Why is that? Thanks. ---- module Main where import Control.Parallel fac :: Integer -> Integer fac n = aux n 1 where aux 0 _ = 0 aux 1 m = m aux n m = let p = n * m in p `pseq` aux (n - 1) p main = do let x = fac 100000 y = fac 100001 in print (x `par` y `pseq` (x + y)) ---- $ ghc-6.12.3 -O2 -threaded -rtsopts Test.hs --make $ time ./Test +RTS -N1 -qg -sstderr > /dev/null ./Test +RTS -N1 -qg -sstderr 20,460,660,928 bytes allocated in the heap 2,492,368 bytes copied during GC 462,128 bytes maximum residency (3 sample(s)) 76,576 bytes maximum slop 4 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 35093 collections, 0 parallel, 0.14s, 0.17s elapsed Generation 1: 3 collections, 0 parallel, 0.00s, 0.00s elapsed MUT time (elapsed) GC time (elapsed) Task 0 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 1 (worker) : 0.00s ( 3.84s) 0.00s ( 0.00s) Task 2 (bound) : 3.87s ( 3.84s) 0.14s ( 0.17s) SPARKS: 1 (0 converted, 1 pruned) INIT time 0.00s ( 0.00s elapsed) MUT time 3.83s ( 3.84s elapsed) GC time 0.14s ( 0.17s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 3.97s ( 4.02s elapsed) %GC time 3.6% (4.3% elapsed) Alloc rate 5,345,814,403 bytes per MUT second Productivity 96.4% of total user, 95.2% of total elapsed gc_alloc_block_sync: 0 whitehole_spin: 0 gen[0].steps[0].sync_large_objects: 0 gen[0].steps[1].sync_large_objects: 0 gen[1].steps[0].sync_large_objects: 0 real 0m4.022s user 0m3.970s sys 0m0.051s $ time ./Test +RTS -N2 -qg -sstderr > /dev/null ./Test +RTS -N2 -qg -sstderr 20,600,461,512 bytes allocated in the heap 3,585,432 bytes copied during GC 458,480 bytes maximum residency (14 sample(s)) 76,576 bytes maximum slop 5 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 34803 collections, 0 parallel, 0.43s, 0.48s elapsed Generation 1: 14 collections, 0 parallel, 0.00s, 0.00s elapsed MUT time (elapsed) GC time (elapsed) Task 0 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 1 (worker) : 3.72s ( 4.91s) 0.24s ( 0.25s) Task 2 (bound) : 3.91s ( 4.91s) 0.19s ( 0.23s) Task 3 (worker) : 0.00s ( 4.91s) 0.00s ( 0.00s) SPARKS: 1 (1 converted, 0 pruned) INIT time 0.00s ( 0.00s elapsed) MUT time 7.29s ( 4.91s elapsed) GC time 0.43s ( 0.48s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 7.72s ( 5.39s elapsed) %GC time 5.6% (8.9% elapsed) Alloc rate 2,824,733,790 bytes per MUT second Productivity 94.4% of total user, 135.2% of total elapsed gc_alloc_block_sync: 0 whitehole_spin: 0 gen[0].steps[0].sync_large_objects: 0 gen[0].steps[1].sync_large_objects: 0 gen[1].steps[0].sync_large_objects: 0 real 0m5.397s user 0m7.724s sys 0m0.443s $ ghc-6.13.20100831 -O2 -threaded -rtsopts Test.hs $ time ./Test +RTS -N2 -qg -sstderr > /dev/null ./Test +RTS -N2 -qg -sstderr 20,458,286,584 bytes allocated in the heap 2,705,816 bytes copied during GC 463,520 bytes maximum residency (3 sample(s)) 73,032 bytes maximum slop 5 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 35088 collections, 0 parallel, 0.19s, 0.22s elapsed Generation 1: 3 collections, 0 parallel, 0.00s, 0.00s elapsed MUT time (elapsed) GC time (elapsed) Task 0 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 1 (worker) : 0.00s ( 3.92s) 0.00s ( 0.00s) Task 2 (bound) : 3.90s ( 3.92s) 0.19s ( 0.22s) Task 3 (worker) : 0.00s ( 3.92s) 0.00s ( 0.00s) SPARKS: 1 (0 converted, 1 pruned) INIT time 0.00s ( 0.00s elapsed) MUT time 3.84s ( 3.92s elapsed) GC time 0.19s ( 0.22s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 4.03s ( 4.14s elapsed) %GC time 4.7% (5.2% elapsed) Alloc rate 5,329,874,595 bytes per MUT second Productivity 95.3% of total user, 92.7% of total elapsed gc_alloc_block_sync: 0 whitehole_spin: 0 gen[0].sync_large_objects: 0 gen[1].sync_large_objects: 0 real 0m4.144s user 0m4.027s sys 0m0.059s

1 0

First questions!
by Eoin C. Bairéad 02 Sep '10

02 Sep '10

Example 2 Prelude> let fac n = if n == 0 then 1 else n * fac (n-1) How does it know to stop ? and why does fac 2.5 hang? thanks Eoin -- -- Eoin C. Bairéad Dublin, Ireland Áth Cliath, Éire

5 4