January 2012 - Haskell-Cafe

Some thoughts on Type-Directed Name Resolution
by Steve Horne 03 Feb '12

03 Feb '12

There's a proposal at the moment to add support for TDNR to Haskell - to leverage "the power of the dot" (e.g. for intellisense). http://hackage.haskell.org/trac/haskell-prime/wiki/TypeDirectedNameResoluti… I approve of the goal, but I'd like to suggest a different approach. My basic idea is stolen from Bertrand Meyer (Object-Oriented Software Construction, second edition). Basically, a class *is* both a module and a type. Quote... Classes as modules Object orientation is primarily an architectural technique: its major effect is on the modular structure of software systems. The key role here is again played by classes. A class describes not just a type of objects but also a modular unit. In a pure object-oriented approach: Classes should be the only modules. By the logic of equivalence relations, we can conclude that a type *is* a module. Only I'd adapt that a little. In C++, the following operators can all be used to access the "module" for some type or value... * :: Scope resolution * . Member dereference * -> Member dereference via a pointer * .* Member-pointer dereference * ->* Member-pointer dereference via a pointer In C++, a type and an instance each have their own modules. A (smart) pointer has its own module, separate from the module for the type it points to. And member-pointers exist because sometimes there's a need to reference a member without knowing or (yet) caring which instance. We already have member pointers - the functions that map an instance to the field value. It would make some sense if these could be placed in a module associated with the type (not the instance). When an instance is created of a type, that can effectively (without run-time overhead) create a new module associated with the new instance. This will contain the same field-access functions, but with the instance parameter already curried in. So there's no real need for any new meaning of the . operator - it's just access to names within a module. And there's no need for a new mechanism for accessing fields - only for a way to place them in that module scope, and a little sugar that gives us the same field-access function but with the instance parameter already curried in. Once we have these modules containing compiler-generated field-access functions, though, it makes some sense to allow additional functions (and perhaps types) to be added within that types module explicitly by the programmer. It may also make sense to allow functions to be explicitly defined which will be added to the instance-modules and support the prefix-instance-parameter sugar. Finally, as with C++, when dealing with IORef and similar, it make make sense to have a separate -> operator (spelled differently, of course). Or it could use the standard dot. C++ and D disagree in this (in C++, the smart pointer has its own module separate from the pointed-at instance - in D, there is no -> or equivalent). As an aside, Ada has already gone through a related transition. The original Ada 83 had variant records, but no "true classes". In Ada 95, "tagged types" were added which were like variant records, but which supported inheritance and run-time dispatch. The discriminant is replaced by a "tag" which is presumably implemented as a virtual table pointer. However, functions and procedures weren't members. The typical call of a "method" would be... packagename.procedure_name ( instance_arg, other_args ); Ada 2005 added some workarounds to allow conventional OOP call notation. See section 1.3 of the Ada 2005 rationale for details. However, it all feels a bit kludgy. In particular, the procedures and functions still aren't members - there are just some special rules for when they can be used as if they were. I've not actually used Ada 2005, but I'd bet some confusion can result from that. Personally, I think Meyer was at least partly right - if types (and instances) are modules, the kludge-factor is much lower. C++ actually doesn't get this quite right IMO (you can access static class members through the instance objects, for example, not just through the classes), but C++ classes *do* act mostly like modules and that is a very useful trait - particularly within the declarative sublanguage (templates etc).

6 13

ANN: combinatorics
by wren ng thornton 03 Feb '12

03 Feb '12

-------------------------------------------- -- combinatorics 0.1.0 -------------------------------------------- The combinatorics package offers efficient *exact* computation of common combinatorial functions like the binomial coefficients and factorial. (For fast *approximations*, see the math-functions package instead.) -------------------------------------------- -- Long Description -------------------------------------------- * Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.) * Math.Combinatorics.Binomial: offers a fast computation of the binomial coefficients based on the prime factorization of the result. As it turns out, it's easier to compute the prime factorization of the answer than it is to compute the answer directly! And you don't even need the factorial function to do so. Albeit, with a fast factorial function, the naive definition of binomial coefficients gives this algorithm a run for its money. * Math.Combinatorics.Factorial: offers a fast computation of factorial numbers. As Peter Luschny comments[1], the factorial function is often shown as a classic example of recursive functions, like addition of Peano numbers, however that naive way of computing factorials is extremely inefficient and does a disservice to those learning about recursion. The current implementation uses the split-recursive algorithm which is more than sufficient for casual use. I'm working on implementing the parallel prime-swing algorithm, which should be a bit faster still. [1] http://www.luschny.de/math/factorial/FastFactorialFunctions.htm -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/combinatorics Darcs: http://community.haskell.org/~wren/combinatorics Haddock (Darcs version): http://community.haskell.org/~wren/combinatorics/dist/doc/html/combinatorics -- Live well, ~wren

3 7

Re: [Haskell-cafe] strict version of Haskell - does it exist?
by Marc Weber 03 Feb '12

03 Feb '12

> jsonLines :: C.Resource m => C.Conduit B.ByteString m Value > jsonLines = C.sequenceSink () $ do > val <- CA.sinkParser json' > CB.dropWhile isSpace_w8 > return $ C.Emit () [val] Adding a \state -> (the way Felipe Lessa told me) make is work and it runs in about 20sec and that although some conduit overhead is likely to take place. omitting my custom data type using bytestrings operating on Value of Aeson reduces running time to 16secs. PHP/C++ still wins: less than 12secs. Now I can imagine again that even a desktop multi core system is faster than a single threaded C application. Thanks for your help. Maybe I can setup profiling again to understand why its still taking little bit more time. Marc Weber

7 8

C++ Parser?
by Christopher Brown 02 Feb '12

02 Feb '12

Hi, I have stumbled across language-c on hackage and I was wondering if anyone is aware if there exists a full C++ parser written in Haskell? Many thanks, Chris.

8 13

[ANN] Crypto-API 0.9 Release
by Thomas DuBuisson 01 Feb '12

01 Feb '12

Crypto-API is a generic interface for cryptographic operations, defining classes for hashes, ciphers, and random number generation while also providing convenience functions such as block cipher modes and padding. Maintainers of hash and cipher implementations are encouraged to add instances for the classes defined in Crypto.Classes. Crypto users are similarly encouraged to use the interfaces defined in the Classes module. Release 0.9 Changes: * Crypto.Classes now exports 'Data.Serialize.encode' * AsymCipher now has proper fundeps * cpolysArr is no longer one big line Cheers, Thomas

2 2

Stuck on HXT basics
by Pēteris Paikens 01 Feb '12

01 Feb '12

I'm quite stuck on getting HXT working to do my xml parsing, can you help me to get started? Even in http://www.haskell.org/haskellwiki/HXT#Getting_started:_Hello_world_examples the basic filter example that's given there in section 6: import Text.XML.HXT.Core import Text.XML.HXT.DOM.XmlTreeFilter selectAllText :: ArrowXml a => a XmlTree XmlTree selectAllText = deep isXText fails with the following error message. What could I be doing wrong? Couldn't match expected type `Data.Tree.NTree.TypeDefs.NTree XNode' with actual type `hxt-8.5.4:Data.Tree.NTree.TypeDefs.NTree hxt-8.5.4:Text.XML.HXT.DOM.TypeDefs.XNode' Expected type: a (Data.Tree.NTree.TypeDefs.NTree XNode) XmlTree Actual type: Text.XML.HXT.DOM.XmlTreeTypes.XmlFilter In the first argument of `deep', namely `isXText' In the expression: deep isXText On the other hand, perhaps you can suggest something other than HXT - my needs would be taking "heavy" XML's (a lot of little-neccessary structure, but correctly validated), extracting text tokens from it and outputting them with some light tagsoup annotation. Regards, Peteris

4 4

Haskell User Group Hamburg - Meeting on 9th Feb.
by Andreas Baldeau 01 Feb '12

01 Feb '12

Hello cafe, in Hamburg this month a new Haskell User Group has formed. We are trying to establish a monthly meetup with hopefully interesting talks. For the start we are having our first regular meetup on the 9th of February, 19:00 in the betahaus hamburg. On this day I will give a talk about datastructures in Haskell and give some introduction into amortized O(1) queues and Tries. So if you are interested to come have a look at http://www.doodle.com/da9tr6zeynmcq3z6 (german). Further announcements will be made via Twitter, so you may want to follow https://twitter.com/hug_hh. Andreas Baldeau

1 0

help with safecopy + acid-state
by Johannes Waldmann 01 Feb '12

01 Feb '12

Dear all, I can't quite get safecopy to work with acid-state: old version of code : data T = T Foo $(deriveSafeCopy 0 'base ''T) new version : data T_orig = T_orig Foo $(deriveSafeCopy 0 'base ''T_orig) data T = T Foo Bar $(deriveSafeCopy 0 'extension ''T) instance Migrate T where type MigrateFrom T = T_Orig ... but when my (new) application reads the state from disk (written by the old application) I get "Could not parse saved checkpoint due to the following error: Failed reading: Duplicate version tags: [0,0]" When I change the version number in deriveSafeCopy, I get "Failed reading: safecopy: Map: Cannot find getter associated with this version number: Version {unVersion = 2}" I don't even know where the "2" comes from. Any hints appreciated - J.W.

3 5

Re: [Haskell-cafe] [Haskell] ANNOUNCE multiarg - parser combinators for command line parsing
by Henning Thielemann 01 Feb '12

01 Feb '12

On Sun, 29 Jan 2012, Simon Meier wrote: > I'm currently using Neil Mitchell's cmdargs package [1]. How does your > package compare to that? Last time I checked cmdargs it was not referential transparent. Is multiarg better in this respect?

3 2

Monad-control rant
by Mikhail Vorozhtsov 31 Jan '12

31 Jan '12

On 11/12/2011 07:34 AM, Bas van Dijk wrote: >> Are you going to release a new version of monad-control right away > > Not just yet. I've split `monad-control` into two packages: > > * `monad-control`: just exports `Control.Monad.Trans.Control`. This part is finished. > * `lifted-base`: wraps all modules of the `base` package which export `IO` computations and provides > lifted version instead. For example we have `Control.Exception.Lifted`, `Control.Concurrent.Lifted`, etc. > > As you can imagine the latter is a lot of boring work. Fortunately it's easy to do so will probably > not take a lot of time. BTW if by any chance you want to help out, that will be much appreciated! > > The repos can be found [here](https://github.com/basvandijk/lifted-base) Maybe I should elaborate on why I stopped using monad-control and rolled out my own version of lifted Control.Exception in monad-abort-fd package. I'm CC-ing the Cafe just in case someone else might be interested in the matter of IO lifting. Imagine we have a monad for multiprogramming with shared state: -- ContT with a little twist. Both the constructor and runAIO -- are NOT exported. newtype AIO s α = AIO { runAIO ∷ ∀ β . (α → IO (Trace s β)) → IO (Trace s β) } runAIOs ∷ MonadBase IO μ ⇒ s -- The initial state → [AIO s α] -- The batch of programs to run. -- If one program exits normally (without using -- aioExit) or throws an exception, the whole batch -- is terminated. → μ (s, Maybe (Attempt α)) -- The final state and the result. -- "Nothing" means deadlock or that -- all the programs exited with -- aioExit. runAIOs = liftBase $ mask_ $ ... bloody evaluation ... data Trace s α where -- Finish the program (without finishing the batch). TraceExit ∷ Trace s α -- Lift a pure value. TraceDone ∷ α → Trace s α -- A primitive to execute and the continuation. TraceCont ∷ Prim s α → (α → IO (Trace s β)) → Trace s β -- Primitive operations data Prim s α where -- State retrieval/modification PrimGet ∷ Prim s s PrimSet ∷ s → Prim s () -- Scheduling point. The program is suspended until -- the specified event occurs. PrimEv ∷ Event e ⇒ e → Prim s (EventResult e) -- Scheduling point. The program is suspended until the state -- satisfies the predicate. PrimCond ∷ (s → Bool) → Prim s () -- Run computation guarded with finalizer. PrimFin ∷ IO (Trace s α) → (Maybe α → AIO s β) → Prim s (α, β) -- Run computation guarded with exception handler. PrimHand ∷ IO (Trace s α) → (SomeException → AIO s α) → Prim s α aioExit ∷ AIO s α aioExit = AIO $ const $ return TraceExit aioAfter ∷ (s → Bool) → AIO s () aioAfter cond = AIO $ return . TraceCont (PrimCond cond) aioAwait ∷ Event e ⇒ e → AIO s (EventResult e) aioAwait e = AIO $ return . TraceCont (PrimEv e) runAIOs slices the programs at scheduling points and enqueues the individual pieces for execution, taking care of saving/restoring the context (finalizers and exception handlers). The Functor/Applicative/Monad/MonadBase/etc instances are pretty trivial: instance Functor (AIO s) where fmap f (AIO g) = AIO $ \c → g (c . f) instance Applicative (AIO s) where pure a = AIO ($ a) (<*>) = ap instance Monad (AIO s) where return = pure AIO g >>= f = AIO $ \c → g (\a → runAIO (f a) c) instance MonadBase IO (AIO s) where liftBase io = AIO (io >>=) instance MonadState s (AIO s) where get = AIO $ return . TraceCont PrimGet put s = AIO $ return . TraceCont (PrimSet s) instance MonadAbort SomeException (AIO s) where abort = liftBase . throwIO trace ∷ AIO s α → IO (Trace s α) trace (AIO g) = g (return . TraceDone) instance MonadRecover SomeException (AIO s) where recover m h = AIO $ return . TraceCont (PrimHand (trace m) h) instance MonadFinally (AIO s) where finally' m f = AIO $ return . TraceCont (PrimFin (trace m) f) -- finally m = fmap fst . finally' m . const -- No async exceptions in AIO instance MonadMask () (AIO s) where getMaskingState = return () setMaskingState = const id Now we have a problem: we can throw/catch exceptions and install finalizers in AIO, but we can't use Control.Exception.Lifted because we can't declare a MonadBaseControl instance for our "ContT with limited interface". So now, instead of trying to wrap IO control operations uniformly, I just reimplement them in terms of the classes I mentioned above (MonadAbort+MonadRecover+MonadFinally+MonadMask), for example: bracket ∷ (MonadFinally μ, MonadMask m μ) ⇒ μ α → (α → μ β) → (α → μ γ) → μ γ bracket acq release m = mask $ \restore → do a ← acq finally (restore $ m a) (release a) It requires more typing (more classes => more instances), but it works for a broader class of monads and I get proper side affects in finalizers for a bonus. The code is on Hackage (monad-abort-fd) and on the GitHub (https://github.com/mvv/monad-abort-fd/blob/master/src/Control/Monad/Excepti…)

4 24