- Haskell-Cafe - Haskell.org

What's going on here?
by michael rice 17 Jan '10

17 Jan '10

I don't see anything wrong with this function, which just subtracts 1 from the first element of an Int list (if there is a first element). Michael My function: dropFirst :: [Int] -> [Int] dropFirst [] = [] dropFirst (x:xs) = (x-1) : xs My output: > :l dropfirst [1 of 1] Compiling Main ( dropfirst.hs, interpreted ) Ok, modules loaded: Main. *Main> dropFirst [3 4 5 6] <interactive>:1:11: No instance for (Num (t -> t1 -> t2 -> Int)) arising from the literal `3' at <interactive>:1:11-17 Possible fix: add an instance declaration for (Num (t -> t1 -> t2 -> Int)) In the expression: 3 4 5 6 In the first argument of `dropFirst', namely `[3 4 5 6]' In the expression: dropFirst [3 4 5 6] *Main>

3 3

ANNOUNCE: nntp 0.0.3
by Maciej Piechotka 17 Jan '10

17 Jan '10

Rather a 'bug-fix' release. Intended to add additional symbols to group names. I'd like to add support for explicit fetching some headers only and giving the message a more MIME-like behaviour but I'm afraid there is nowhere written how XHDR/HDR would behave with multiline headers nor I found a suitable package (mime[1] seems to not include even parsing the headers only and mime-string[2] does not take into account comments which may or may not be a problem with Message-ID comparaison). Regards [1] http://hackage.haskell.org/package/mime [2] http://hackage.haskell.org/package/mime-string

1 0

RFC: Space-leak-free, efficient symbol table implementation.
by Thomas Schilling 16 Jan '10

16 Jan '10

Hello Café, Symbol tables are a very common data structure in compilers but the most common implementation uses a hash table as a global variable which results in a space leak. If we decide to use several symbol tables we still cannot join different symbol tables. After some Googling I found the following implementation. It could still be argued that there are some smaller space leaks left, but decide for yourself. The use case I have in mind is a collection of several long-running compiler worker threads, that for the most part write their result to disk but may occasionally need to communicate with each other (and agree on symbol identities.) I'd appreciate comments / code review on the following code. I think it's fairly well-commented. Thanks, / Thomas {-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -funbox-strict-fields #-} -- | -- Module : Data.Atom.UF -- Copyright : (c) Thomas Schilling 2010 -- License : BSD-style -- -- Maintainer : nominolo(a)gmail.com -- Stability : experimental -- Portability : portable -- -- Symbols without a central symbol table. -- -- Symbols provide the following efficient operations: -- -- - /O(1)/ equality comparison (in practise) -- - /O(1)/ ordering comparison (in practise) -- - /O(n)/ creation -- -- This can be implemented by using a global variable mapping strings -- to symbols and a counter assigning ids to symbols. However, this -- has two problems: -- -- 1. It has a space leak. No symbols can ever be removed from this -- table. For example, if we add the symbol @\"foo\"@ the first -- time it might get assigned id 1, if we then delete it and -- insert it again it might get assigned id 42. However, there -- may still be symbols in memory which got assigned id 1. -- Instead, symbols should be garbage collected like other data. -- Using weak pointers has bad effects on performance due to -- garbage collector overhead. -- -- 2. It is not reliable to compare symbols created using different -- symbol tables. They would most likely get assigned different -- ids. -- -- This implementation of symbols allows *optional* use of a symbol -- table. If a symbol table is used, this implementation will tend to -- use less memory and its operations will be a little bit faster at -- the beginning. For longer runs, it won't make a big difference -- though, since the representation is self-optimising. -- -- Inspired by Richard O'Keefe's message to Erlang's eeps mailing list -- <http://www.erlang.org/cgi-bin/ezmlm-cgi/5/057>, which in turn was -- inspired by the Logix implementation of Flat Concurrent Prolog. -- -- -- * Implementation -- -- Each symbol is represented a pointer to the symbol info, which -- consists of: -- -- * a 'String' -- * a 'Hash' -- * a null-able parent pointer to an equivalent symbol info -- -- Creating the same symbol twice will at first be represented as two -- different entities. -- -- @ -- .----+-------+-----. -- A -----> | 42 | "foo" | nil | -- '----+-------+-----' -- B --. -- '--> .----+-------+-----. -- C -----> | 42 | "foo" | nil | -- '----+-------+-----' -- @ -- -- (Note that @A@, @B@ and @C@ are @IORefs@.) -- -- When comparing @A@ and @B@ we use the following properties: -- -- 1. If @A@ and @B@ are identical then they must be equal. -- -- 2. If they point to the same object, they must equal. -- -- 3. If they have different hashes, they are different. -- -- Unless there is a hash collision, we can decide equality and -- ordering for all symbols that have been built with the same hash -- table. -- -- If the two objects have no parent, have the same hash, and the same -- string, we now make one the first the parent of the other and -- update the pointer of @B@ accordingly. If there are no references -- to the second object left it can now be garbage collected. -- -- If an object already has a parent pointer we follow each object's -- parents to the roots and compare the roots. This process might -- again result in updates to @A@ or @B@ and various parent pointers. -- -- In the example above, after @A == B@ we have: -- -- @ -- .----+-------+-----. -- A -----> | 42 | "foo" | nil | -- .--> '----+-------+-----' -- B --' ^ -- .----+-------+--|--. -- C -----> | 42 | "foo" | * | -- '----+-------+-----' -- @ -- -- After @C == A@ or @C == B@ we have. -- -- @ -- A -----> .----+-------+-----. -- .--> | 42 | "foo" | nil | -- B --'.-> '----+-------+-----' -- | ^ -- | .----+-------+--|--. -- C ---' | 42 | "foo" | * | -- '----+-------+-----' -- @ -- -- The second object will now be garbage collected. -- -- In fact, after the first @A == B@, the remaining updates could use -- some help from the garbage collector. This could be done by -- somehow forcibly (and unsafely) replacing the second object by an -- update frame and then rely on the GC's indirection shortening -- feature. This is /very/ unsafe, since some code may rely \"know\" -- that the object is already evaluated. E.g., C's pointer could be -- tagged (c.f. \"Faster Laziness Using Dynamic Pointer Tagging\"). -- It /might/ work if we can match the physical layout of both -- structures, but it's equally likely that hell freezes over, so I'll -- leave that as an exercise for more braver hackers. -- -- * TODO -- -- - generalise to arbitrary hashable objects. need not be -- restricted to 'String'. -- -- - make thread-safe. (we only need a lock for the uncommon cases) -- -- - make sure the pointer update code is correct and has no bad -- cases -- -- - implement IntMap variant\/wrapper that respects that two -- different objects may have the same key (however unlikely). -- module Data.Atom.UF ( Symbol, intern, internInto, SymTab(..) ) where import Data.Word ( Word32 ) import Data.Char ( ord ) import Data.Bits ( xor ) import Data.IORef import System.IO.Unsafe import Control.Monad -- ( unless ) import System.Mem.Weak import System.Mem import Data.Maybe -- ------------------------------------------------------------------- -- Public API: -- | A symbol. newtype Symbol = Symbol (IORef SymbolInfo) instance Eq Symbol where x == y = cmpSymbol x y == EQ instance Ord Symbol where compare = cmpSymbol instance Show Symbol where show = showSym -- | Create a new local symbol. For best performance use -- 'internInto' together with a symbol table / map. intern :: String -> Symbol class SymTab s where lookupSymbol :: s -> String -> Maybe Symbol insertSymbol :: String -> Symbol -> s -> s -- | Insert a symbol into an existing table. internInto :: SymTab s => s -> String -> (s, Symbol) -- ------------------------------------------------------------------- -- Internals data SymbolInfo = SymInfo {-# UNPACK #-} !Word32 -- hash {-# UNPACK #-} !(IORef Link) -- parent [really unpack]? String type Link = Maybe SymbolInfo internInto st str = case lookupSymbol st str of Just sym -> (st, sym) _ -> let sym = intern str in (insertSymbol str sym st, sym) showSym :: Symbol -> String showSym (Symbol r) = unsafePerformIO $ do -- dupable/inline is fine, too, since the string never changes (SymInfo _ _ str) <- readIORef r return str intern s = unsafePerformIO $ do lnk <- newIORef Nothing r <- newIORef $ SymInfo (hash s) lnk s return (Symbol r) mkSymbolInfo :: String -> SymbolInfo mkSymbolInfo s = unsafePerformIO $ do lnk <- newIORef Nothing return $ SymInfo (hash s) lnk s cmpSymbol :: Symbol -> Symbol -> Ordering cmpSymbol (Symbol r1) (Symbol r2) | r1 == r2 = EQ | otherwise = unsafePerformIO $ do -- We only read. It should be safe to use unsafeInlineIO for -- the two reads. sym1@(SymInfo h1 l1 s1) <- readIORef r1 sym2@(SymInfo h2 l2 s2) <- readIORef r2 case h1 `compare` h2 of -- If the hashes are different they cannot be the same symbol LT -> return LT GT -> return GT EQ | sameSym sym1 sym2 -> -- The two references are not the same, but they point to -- the same object. That's fine, we can't optimise any -- further. return EQ -- END OF COMMON CASE -- -- If the symbols have been built using the same symbol table -- we will only reach this case if we have a hash collision or -- the symbols were built from different symbol tables. -- -- TODO: Extract into NOINLINE function, wrap unsafePerformIO, -- and use an MVar-based lock. | otherwise -> do -- The hashes are the same. It could be a collision, or the -- symbol was created using a different symbol table. -- -- Case 1: The symbols have already be joined, but this -- Symbol's IORef still points to the old version. We can -- determine this by following the union/find structure. rep1 <- repr sym1 rep2 <- repr sym2 let string_cmp = s1 `compare` s2 -- lazy! if sameSym rep1 rep2 || string_cmp == EQ then do -- They should in fact be the same symbol. Update the -- atoms and the symbol infos if necessary. -- TODO: Use MVar / lock. unless (sameSym sym1 rep1) $ do writeIORef r1 rep1 writeIORef l1 (Just rep1) -- path shortening unless (sameSym sym2 rep1) $ do writeIORef r2 rep1 writeIORef l2 (Just rep1) return EQ else do -- They are not the same, and they shouldn't return string_cmp {-# NOINLINE cmpSymbol #-} -- We abuse the fact that IORefs give us an identity (i.e., observable -- sharing) and that we need the IORef anyway. sameSym :: SymbolInfo -> SymbolInfo -> Bool sameSym (SymInfo _ r1 _) (SymInfo _ r2 _) = r1 == r2 repr :: SymbolInfo -> IO SymbolInfo repr sym@(SymInfo _ r _) = do parent <- readIORef r -- TODO: perform path shortening. case parent of Nothing -> return sym Just sym' -> repr sym' test1 = do let s1@(Symbol r1) = intern "foo" s2@(Symbol r2) = intern "foo" print $ r1 == r2 -- should be False -- create a weak reference to the second symbol, so we can observe -- when it is garbage collected w <- mk_weak =<< readIORef r2 print $ s1 == s2 -- should print True print =<< liftM2 sameSym (readIORef r1) (readIORef r2) -- should print True putStrLn "GCing" performGC -- this should print goodbye, representing the -- fact that the second symbol has been garbage -- collected. print . isJust =<< deRefWeak w -- should print False (object has been collected) where mk_weak o = mkWeakPtr o (Just (putStrLn "goodbye")) -- ------------------------------------------------------------------- -- Fowler / Noll / Vo (FNV) hash. Original code expected 'unsigned -- char' input. Don't know whether it behaves worse for unicode -- chars. hash :: String -> Word32 hash str = go magic_start (map ord str) where magic_start = 2166136261 :: Word32 go :: Word32 -> [Int] -> Word32 go !h [] = h go !h (c:cs) = go ((h * 16777619) `xor` fromIntegral c) cs

2 1

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