January 2010 - Haskell-Cafe

FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
by Will Ness 16 Jan '10

16 Jan '10

apfelmus <apfelmus <at> quantentunnel.de> writes: > ~~ This is a repost, with apologies to anyone who sees this twice (I've replied to a two years old thread, and it doesn't show up in GMANE as I thought it would). ~~ > Dave Bayer wrote: > > What I'm calling a "venturi" > > > > venturi :: Ord a => [[a]] -> [a] > > > > merges an infinite list of infinite lists into one list, under the > > assumption that each list, and the heads of the lists, are in > > increasing order. > > > > I wrote this as an experiment in coding data structures in Haskell's > > lazy evaluation model, rather than as explicit data. The majority of the > > work done by this code is done by "merge"; the multiples of each prime > > percolate up through a tournament consisting of a balanced tree of > > suspended "merge" function calls. In order to create an infinite lazy > > balanced tree of lists, the datatype > > > > data List a = A a (List a) | B [a] > > > > is used as scaffolding. One thinks of the root of the infinite tree as > > starting at the leftmost child, and crawling up the left spine as > > necessary. > > After some pondering, the List a data structure for merging is really > ingenious! :) Here's a try to explain how it works: > > The task is to merge a number of sorted and infinite lists when it's > known that their heads are in increasing order. In particular, we want > to write > > primes = (2:) $ diff [3..] $ venturi $ map multiple primes > > Thus, we have a (maybe infinite) list > > xss = [xs1, xs2, xs3, ...] > > of infinite lists with the following properties > > all sorted xss > sorted (map head xss) > > where sorted is a function that returns True if the argument is a > sorted list. A first try to implement the merging function is > > venturi xss = foldr1 merge xss > = xs1 `merge` (xs2 `merge` (xs3 `merge` ... > > where merge is the standard function to merge to sorted lists. > > However, there are two problems. The first problem is that this doesn't > work for infinite lists since merge is strict in both arguments. But > the property head xs1 < head xs2 < head xs3 < ... we missed to exploit > yet can now be used in the following way > > venturi xss = foldr1 merge' xss > > merge' (x:xt) ys = x : merge xt ys > > In other words, merge' is biased towards the left element > > merge' (x:_|_) _|_ = x : _|_ > > which is correct since we know that (head xs < head ys). > > The second problem is that we want the calls to merge to be arranged > as a balanced binary tree since that gives an efficient heap. It's not > so difficult to find a good shape for the infinite tree, the real > problem is to adapt merge' to this situation since it's not associative: > > ...... > > The problem is that the second form doesn't realize that y is also > smaller than the third argument. In other words, the second form has to > treat more than one element as "privileged", namely x1,x2,... and y. > This can be done with the aforementioned list data structure > > data People a = VIP a (People a) | Crowd [a] > > The people (VIPs and crowd) are assumed to be _sorted_. Now, we can > start to implement > > merge' :: Ord a => People a -> People a -> People a Hi, ... replying to a two-years-old post here, :) :) and after consulting the full "VIP" version in haskellwiki/Prime_Numers#Implicit_Heap ... It is indeed the major problem with the merged multiples removing code (similar one to Richard Bird's code from Melissa O'Neill's JFP article) - the linear nature of foldr, requiring an (:: a->b->b) merge function. To make it freely composable to rearrange the list into arbitrary form tree it must indeed be type uniform (:: a->a->a) first, and associative second. The structure of the folded tree should be chosen to better suit the primes multiples production. I guestimate the total cost as Sum (1/p)*d, where p is a generating prime at the leaf, and d the leaf's depth, i.e. the amount of merge nodes its produced multiple must pass on its way to the top. The structure used in your VIP code, 1+(2+(4+(8+...))), can actually be improved upon with another, (2+4)+( (4+8)+( (8+16)+...)), for which the estimated cost is about 10%-12% lower. This can be expressed concisely as the following: primes :: () -> [Integer] primes () = 2:primes' where primes' = [3,5] ++ drop 2 [3,5..] `minus` comps mults = map (\p-> fromList [p*p,p*p+2*p..]) $ primes' (comps,_) = tfold mergeSP (pairwise mergeSP mults) fromList (x:xs) = ([x],xs) tfold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` tfold f (pairwise f xs) pairwise f (x:y:ys) = f x y : pairwise f ys mergeSP (a,b) ~(c,d) = let (bc,b') = spMerge b c in (a ++ bc, merge b' d) where spMerge u@(x:xs) w@(y:ys) = case compare x y of LT -> (x:c,d) where (c,d) = spMerge xs w EQ -> (x:c,d) where (c,d) = spMerge xs ys GT -> (y:c,d) where (c,d) = spMerge u ys spMerge u [] = ([], u) spMerge [] w = ([], w) with ''merge'' and ''minus'' defined in the usual way. Its run times are indeed improved 10%-12% over the VIP code from the haskellwiki page. Testing was done by running the code, interpreted, inside GHCi. The ordered "split pairs" representing ordered lists here as pairs of a known, finite (so far) prefix and the rest of list, form a _monoid_ under mergeSP. Or with wheel, primes :: () -> [Integer] primes () = 2:3:5:7:primes' where primes' = [11,13] ++ drop 2 (rollFrom 11) `minus` comps mults = map (\p-> fromList $ map (p*) $ rollFrom p) $ primes' (comps,_) = tfold mergeSP (pairwise mergeSP mults) fromList (x:xs) = ([x],xs) rollFrom n = let x = (n-11) `mod` 210 (y,_) = span (< x) wheelSums in roll n $ drop (length y) wheel wheelSums = roll 0 wdiffs roll = scanl (+) wheel = wdiffs ++ wheel wdiffs = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2: 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wdiffs Now _this_, when tested as interpreted code in GHCi, runs about 2.5x times faster than Priority Queue based code from Melissa O'Neill's ZIP package mentioned at the haskellwiki/Prime_Numbers page, with about half used memory reported, in producing 10,000 to 300,000 primes. It is faster than BayerPrimes.hs from the ZIP package too, in the tested range, at about 35 lines of code in total. ~~ This is a repost, with apologies to anyone who sees this twice (I've replied to a two years old thread, and it doesn't show up in GMANE as I thought it would). ~~

5 69

Arch Haskell News: Nov 23 2008
by Don Stewart 16 Jan '10

16 Jan '10

News about Haskell on Arch Linux * Arch now has 734 Haskell packages now * That’s an increase of 29 new packages in the last 8 days! * 3.6 new Haskell releases are occuring each day. Noteworthy, * haskell-hledger-0.2: “A ledger-compatible text-based accounting tool.” * gitit-0.3.1: “Wiki using HAppS, git, and pandoc.” * lhc-20081121: “Lhc Haskell Compiler” * haskell-hosc-0.6: “Haskell Open Sound Control” * haskell-flickr-0.3.2: “Haskell binding to the Flickr API” * haskell-delicious-0.3.2: “Accessing the del.icio.us APIs from Haskell (v2)” * haskell-mediawiki 0.2.3: “Interfacing with the MediaWiki API” * darcs-2.1.2.2: “a distributed, interactive, smart revision control system” Full update list, http://archhaskell.wordpress.com/2008/11/24/arch-haskell-news-nov-23-2008/ -- Don

24 56

addFinalizer to which object?
by Henning Thielemann 16 Jan '10

16 Jan '10

The documentation of System.Mem.Weak.addFinalizer suggests to me, that this function is very fragile, because the object we track, might be optimized away. In my case this applies. I have a resource that is needed for generating chunks of a lazy byte string. If the byte string is created completely or the byte string cannot be accessed anymore, this resource must be freed. It must also be freed within Haskell code, thus addForeignPtrFinalizer does not help. To illustrate that I have attached a small example, where I use a StablePtr as resource, that points to a list. This Haskell list is read from C code and written to a chunk of a lazy ByteString. A Haskell function creates the ByteString lazily and calls the C function for every new chunk. I have added a finalizer to the StablePtr itself. That works without optimization, but using optimization the finalizer is run immediately and the program aborts with segmentation fault. Thus my question: How to get reliable finalization? #include "ProcessList_stub.h" /* The function copies elements from a Haskell list to a piece of memory and returns the number of bytes that could be fetched. */ int copy_list_to_chunk (unsigned long int n, HsStablePtr list, char *p) { unsigned long int k = n; while (k>0) { if (!get_next_element(list, p)) {break; } p++; k--; } return (n-k); } {- # generate C stubs ghc -c ProcessList.hs # generate executable ghc -O --make ProcessChunk.c ProcessList.hs -} {- Use a C function for filling chunks of a lazy ByteString with data from a Haskell list. A StablePtr is needed to pass the list to C and back to Haskell. Somehow we must assert that the StablePtr is deleted and the list can be garbage collected, once the ByteString is constructed. We concatenate infinitely many such lists, thus many StablePtrs and referenced lists must be freed. Use addFinalizer? To which object shall I add the finalizer? Without optimization adding the finalizer to the StablePtr works, with optimization, its finalizer is run too early. I also tried to add the finalizer to the end of the list, which is not quite correct, but then the finalizer is run never. Whatever I tried: Finalizer is run immediately or never. What is the right way? -} {-# LANGUAGE ForeignFunctionInterface #-} module Main where import qualified Data.ByteString as B import qualified Data.ByteString.Internal as BI import qualified Data.ByteString.Lazy as BL import qualified Data.ByteString.Lazy.Internal as BLI import System.IO.Unsafe (unsafePerformIO, unsafeInterleaveIO, ) import System.Mem.Weak (addFinalizer, ) import Foreign.StablePtr (StablePtr, newStablePtr, freeStablePtr, deRefStablePtr, ) import Foreign.Storable (poke, ) import Foreign.C.Types (CULong, ) import Foreign.Ptr (FunPtr, Ptr, nullPtr, castPtr, ) import Data.IORef (IORef, newIORef, readIORef, writeIORef, ) import Data.Word (Word8, Word32, ) import Control.Monad (liftM2, ) getNextElement :: StablePtr (IORef [Word8]) -> Ptr Word8 -> IO Bool getNextElement stable elemPtr = do listRef <- deRefStablePtr stable xt <- readIORef listRef case xt of [] -> return False x:xs -> do poke elemPtr x writeIORef listRef xs return True foreign export ccall "get_next_element" getNextElement :: StablePtr (IORef [Word8]) -> Ptr Word8 -> IO Bool foreign import ccall "copy_list_to_chunk" copyListToChunk :: CULong -> StablePtr (IORef [Word8]) -> Ptr Word8 -> IO CULong chunkSize :: Int chunkSize = 13 byteStringFromList :: [Word8] -> BL.ByteString byteStringFromList list = unsafePerformIO $ do stable <- newStablePtr =<< newIORef list addFinalizer stable (putStrLn "free stable pointer" >> freeStablePtr stable) let go = unsafeInterleaveIO $ do v <- BI.createAndTrim chunkSize $ fmap fromIntegral . copyListToChunk (fromIntegral chunkSize) stable fmap (BLI.chunk v) $ if B.length v < chunkSize then return BL.empty else go go main :: IO () main = print $ BL.unpack $ -- BL.take 1000 $ BL.concat $ map (BL.take 42 . byteStringFromList . iterate (1+)) (iterate (1+) 0)

1 0

Naïve Parallelization: C++ vs Haskell
by Jon Harrop 16 Jan '10

16 Jan '10

I felt the previous comparison left a little to be desired so I have repeated the experiment on 8 cores using the original Haskell code and giving results for 9, 12 and 13 levels of spheres: http://flyingfrogblog.blogspot.com/2010/01/naive-parallelization-c-vs-haske… -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e

1 0

From records to a type class
by Taru Karttunen 16 Jan '10

16 Jan '10

Hello I am wrapping Fuse in a pure Haskell binding and have some issues with the interface. Currently I am using a record for managing the callback functions, but I think there may be a more elegant formulation. Any ideas how to formulate the Fuse record as a typeclass elegantly? Some notes: + TFs not FDs. + Separate fh* implementations (raw/stableptr/custom implemented by user) easily selected by the library user. + Readable type errors. + One large typeclass + overlapping instances works, but seems hacky. + MPTCs will probably work but is it good form to use them with TFs? + Or is using a record better currently? ps. Note that the interface is very much simplified for the sake of the discussion. (e.g. [Word8] instead of ByteString). > import Data.Word > > data IsDir > data IsFile > > type Ino = Word32 > data Attr = Attr {} > > data Fuse (fh :: * -> *) = Fuse { > open :: Ino -> IO (fh IsFile) > , read :: Ino -> fh IsFile -> Word64 -> Word32 -> IO [Word8] > , opendir :: Ino -> IO (fh IsDir) > , getattr :: forall fileOrDir. Ino -> fh fileOrDir -> IO Attr > -- ... > > -- File handle management > , fhFree :: Word64 -> IO () > , fhAlloc :: forall any. fh any -> IO Word64 > , fhRef :: forall any. Word64 -> IO (fh any) > } > > -- Optimally get rid of this wrapping... > newtype RawFH t = R { r :: Word64 } > noFhEmpty :: Fuse RawFH > noFhEmpty = Fuse { fhFree = \_ -> return () > , fhAlloc = return . r > , fhRef = return . R > } > > stablePtrEmpty :: Fuse anyfh > stablePtrEmpty = Fuse {} -- implement fh* with StablePtrs (omitted) > > -- User file handle type might be like this: > > data Obj t where > Dir :: {} -> Obj IsDir > File :: {} -> Obj IsFile - Taru Karttunen

2 2

Capped lists and |append|
by John Millikin 15 Jan '10

15 Jan '10

Earlier today I uploaded the capped-list package; I didn't think there would be any interest, since it's a relatively trivial data structure, but already there's been three emails and an IRC convo about it. In short, this is Heinrich Apfelmus's "Train" type from <http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html>, which showed up in a thread I posted regarding lazy error handling <http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html>. The structure of a Train / CappedList (I like my name better) is: data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it. append :: CappedList cap a -> CappedList cap a -> CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost This problem can be solved using an unusual type signature for |append|, such as: append :: CappedList cap1 a -> CappedList cap2 a -> (cap1, CappedList cap2 a) or by declaring that a capped list is truly "capped": append :: CappedList cap a -> CappedList cap2 b -> CappedList cap a but these makes defining a reasonable |concat| difficult. Any ideas? This seems like a useful structure, since several people have described it, but some of the semantics seem troublesome.

6 7

ANN: haskell-src-exts 1.7.0
by Niklas Broberg 15 Jan '10

15 Jan '10

Fellow Haskelleers, As I was asked to start spamming again, I'm hereby pleased to announce the release of haskell-src-exts-1.7.0! * On hackage: http://hackage.haskell.org/package/haskell-src-exts * Via cabal: cabal install haskell-src-exts * Darcs repo: http://code.haskell.org/haskell-src-exts For users of hsx, this version works fine with hsx-0.6.1. Since I haven't sent out one of these announcements in a while, here's the complete CHANGELOG since the previous announcement: ** 1.7.x 1.6.1 --> 1.7.0 =============== * Operators defined on the form (a `op` b) c = ... could not be handled by the (annotated) AST, nor the parser. I had to change the definition of the AST node for InfixMatch to allow a list of right-hand subpatterns, i.e. InfixMatch l (Pat l) (Name l) (Pat l) ... has become InfixMatch l (Pat l) (Name l) [Pat l] ... I also had an epiphany and fixed the issue that would arise with exact printing of prefix definitions including parentheses (e.g. (foo x) y = ...), so that now works too! ** 1.6.x 1.6.0 --> 1.6.1 =============== * UnicodeSyntax now works not only for identifiers, but also for ->, <- and =>, as well as Arrows arrows and kind stars. (And before you send me bug reports for this one, do check that your version of readFile is Unicode aware, i.e. you use GHC 6.12 or the utf8-string version). 1.5.3 --> 1.6.0 =============== * (=~=) turns out to be too general at Functor (for intuitive and not technical reasons), so is specialised to Annotated to closer mirror the original intention. * applyFixities is hoisted to a monad, and now fails on ambiguous infix expressions. ** 1.5.x 1.5.2 --> 1.5.3 =============== * Several small bug fixes in the exact printer, and fail more gracefully if the number of srcInfoPoints doesn't match the needs of the node. 1.5.1 --> 1.5.2 =============== * Fix a bug in the exact printer that made it always print the first token at position (0,0). * In fixing the above, Annotated is now a superclass of ExactP. It was already a superclass in spirit, and nothing can break from this since ExactP is only exported abstractly. 1.5.0 --> 1.5.1 =============== * The pretty printer now introduces parentheses for non-atomic arguments to function application. Note that infix applications are left untouched, no parentheses will be inserted there, as it is assumed that fixities are already properly resolved. * Fix a bug in the pretty printer where view patterns and n+k patterns were not properly parenthesised. 1.4.0 --> 1.5.0 =============== * Add support for acting on LINE pragmas while parsing, i.e. updating the source position according to info given in LINE pragmas. This is done conditionally based on a new flag ignoreLinePragmas in the ParseMode, hence the need to increase the major version. ** 1.4.x 1.3.5 --> 1.4.0 =============== * The AST node for Proc in the simple AST is changed to include a SrcLoc argument, to make it consistent with similar nodes e.g. Lambda. This is specifically needed for transformation of patterns in HSX. ** 1.3.x 1.3.4 --> 1.3.5 =============== * Added an entry point in the parser for statements, and an instance Parseable Stmt to go with it. * Ensured that .Annotated exports all relevant parseXXX(WithYYY) functions. 1.3.3 --> 1.3.4 =============== * Operator fixities are now resolved in patterns. 1.3.2 --> 1.3.3 =============== * Fixes a bug where qualified keywords are rejected even if the extension that enables the keyword in question is not turned on. 1.3.0 --> 1.3.2 =============== (Let's forget 1.3.1 ever existed.) * Fix a bug where declarations of infix operators were not properly merged as FunBinds.

2 3

Re: [Haskell] ANN: Streaming Component Combinators 0.4
by Mario Blažević 15 Jan '10

15 Jan '10

Henning Thielemann wrote: > Mario Blažević schrieb: >> Version 0.4 of Streaming Component Combinators, or SCC for short, has >> been released on Hackage. Get it at >> >> http://hackage.haskell.org/package/scc >> >> There isn't much new high-level functionality compared to the >> previous version, but the implementation has been heavily refactored and >> the foundations completely replaced. > > Stupid question: Is it related to Arrows? Not really. You might say it's more general than arrows, because the streaming components are not restricted to a single input and single output type. On the other hand, they are all specific to stream processing, much like Fudgets and Yampa which are arrow-based. I suppose the Transducer data type [1] could be made an Arrow instance, which would let me rename the 'connect' combinator [2] to (>>>). I'll have a look at Yampa to see if I can harvest more combinator names, thank you! [1] http://hackage.haskell.org/packages/archive/scc/0.4/doc/html/Control-Concur… [2] http://hackage.haskell.org/packages/archive/scc/0.4/doc/html/Control-Concur…

2 1

Haddock question: hiding internal instances
by Niklas Broberg 15 Jan '10

15 Jan '10

Hi all, The question I have is this: How can I get Haddock to omit listing instances of package-internal data types for exported classes? Here's an example of what I mean: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.6.0/doc/html… At the very end of the rather extensive list of instances, you'll find the following: SrcInfo loc => Pretty (PAsst loc) SrcInfo loc => Pretty (PType loc) SrcInfo loc => Pretty (PContext loc) SrcInfo loc => Pretty (ParseXAttr loc) SrcInfo loc => Pretty (PFieldUpdate loc) SrcInfo loc => Pretty (PExp loc) All these data types are internal to the package, and the module they live in is marked with 'hide'. As expected no links are generated to any documentation for these data types, but I want them removed from this list entirely. They are internal after all, so what's the point of listing them? How can I achieve this? Cheers, /Niklas

3 3

Hackage strangeness
by Roel van Dijk 15 Jan '10

15 Jan '10

I wrote a small cronjob to update my hackage reverse-deps. When checking if it worked I noticed that my hackage appears to be more up-to-date than the real thing! Compare the "What's new" of both: Real hackage: http://hackage.haskell.org/packages/archive/recent.html Play thing: http://bifunctor.homelinux.net/~roel/hackage/packages/archive/recent.html At the time of writing this message the newest package on Hackage is dated Tue Jan 12 16:24:18 UTC 2010. The newest on my mirror is Thu Jan 14 20:07:04 UTC 2010. I thought that possibly the recent.html page wasn't being built, but when I follow an actual package, like vacuum-opengl the most recent version on hackage is 0.0.2 while on my mirror it is 0.0.3. Is this a case of data loss or something else?

3 4