Functional Programming

Informatics Independence Referendum Debate

Planet Haskell - 11 hours 18 min ago
School of Informatics, University of EdinburghIndependence Referendum Debate4.00--5.30pm Monday 25 AugustAppleton Tower Lecture Room 2For the NAYs: Prof. Alan BundyFor the AYEs: Prof. Philip WadlerModerator: Prof. Mike FourmanAll members of the School of Informaticsand the wider university community welcome(This is a debate among colleagues and not a formal University event.All views expressed are those of the individuals who express them,and not the University of Edinburgh.)

Research funding in an independent Scotland

Planet Haskell - 11 hours 18 min ago
A useful summary, written by a colleague.In Summary: the difference between the Scottish tax contribution and RCUK spending in Scotland is small compared to savings that will be made in other areas such as defenceFunding levels per institution are actually similar in Scotland to those in the rest of the UK, it’s just that there are more institutions hereBecause of its relative importance any independent Scottish government would prioritise researchIf rUK rejects a common research area it would lose the benefits of its previous investments, and the Scottish research capacity, which is supported by the Scottish government and the excellence of our universitiesThere are significant disadvantages with a No vote, resulting from UK immigration policy and the possibility of exiting the EU

Scotland can't save England

Planet Haskell - 11 hours 18 min ago
Salmond concluded his debate with Darling by observing that for half his lifetime Scotland had been ruled by governments that Scotland had not elected. Many take this the other way, and fret that if Scotland leaves the UK, then Labour would never win an election. Wings Over Scotland reviews the figures. While Scotland has an effect on the size of the majority, elections would yield the same ruling party with or without Scotland in 65 of the last 67 years. To a first approximation, Scotland's impact over the rest of the UK is nil, while the rest of the UK overwhelms Scotland's choice half the time.1945 Labour govt (Attlee)————————————Labour majority: 146Labour majority without any Scottish MPs in Parliament: 143NO CHANGE WITHOUT SCOTTISH MPS1950 Labour govt (Attlee)————————————Labour majority: 5Without Scottish MPs: 2NO CHANGE1951 Conservative govt (Churchill/Eden)——————————————————–Conservative majority: 17Without Scottish MPs: 16NO CHANGE1955 Conservative govt (Eden/Macmillan)——————————————————–Conservative majority: 60Without Scottish MPs: 61NO CHANGE1959 Conservative govt (Macmillan/Douglas-Home)————————————————————————Conservative majority: 100Without Scottish MPs: 109NO CHANGE1964 Labour govt (Wilson)————————————Labour majority: 4Without Scottish MPs: -11CHANGE: LABOUR MAJORITY TO CONSERVATIVE MAJORITY OF 1(Con 280, Lab 274, Lib 5)1966 Labour govt (Wilson)————————————Labour majority: 98Without Scottish MPs: 77NO CHANGE1970 Conservative govt (Heath)——————————————–Conservative majority: 30Without Scottish MPs: 55NO CHANGE1974 Minority Labour govt (Wilson)————————————————Labour majority: -33Without Scottish MPs: -42POSSIBLE CHANGE – LABOUR MINORITY TO CONSERVATIVE MINORITY(Without Scots: Con 276, Lab 261, Lib 11, Others 16)1974b Labour govt (Wilson/Callaghan)—————————————————–Labour majority: 3Without Scottish MPs: -8CHANGE: LABOUR MAJORITY TO LABOUR MINORITY(Lab 278 Con 261 Lib 10 others 15)1979 Conservative govt (Thatcher)————————————————Conservative majority: 43Without Scottish MPs: 70NO CHANGE1983 Conservative govt (Thatcher)————————————————Conservative majority: 144Without Scottish MPs: 174NO CHANGE1987 Conservative govt (Thatcher/Major)——————————————————Conservative majority: 102Without Scottish MPs: 154NO CHANGE1992 Conservative govt (Major)———————————————Conservative majority: 21Without Scottish MPs: 71NO CHANGE1997 Labour govt (Blair)———————————–Labour majority: 179Without Scottish MPs: 139NO CHANGE2001 Labour govt (Blair)———————————–Labour majority: 167Without Scottish MPs: 129NO CHANGE2005 Labour govt (Blair/Brown)——————————————–Labour majority: 66Without Scottish MPs:  43NO CHANGE2010 Coalition govt (Cameron)——————————————Conservative majority: -38Without Scottish MPs: 19CHANGE: CON-LIB COALITION TO CONSERVATIVE MAJORITY

How Scotland will be robbed

Planet Haskell - 11 hours 18 min ago
Thanks to the Barnett Formula, the UK government provides more funding per head in Scotland than in the rest of the UK. Better Together touts this as an extra £1400 in each person's pocket that will be lost if Scotland votes 'Aye' (famously illustrated with Lego). Put to one side the argument as to whether the extra £1400 is a fair reflection of the extra Scotland contributes to the UK economy, through oil and other means. The Barnett Formula is up for renegotiation. Will it be maintained if Scotland votes 'Nay'?Wings over Scotland lays out the argument that if Scotland opts to stick with Westminster then Westminster will stick it to Scotland.The Barnett Formula is the system used to decide the size of the “block grant” sent every year from London to the Scottish Government to run devolved services. ...Until now, however, it’s been politically impossible to abolish the Formula, as such a manifestly unfair move would lead to an upsurge in support for independence. In the wake of a No vote in the referendum, that obstacle would be removed – Scots will have nothing left with which to threaten Westminster.It would still be an unwise move for the UK governing party to be seen to simply obviously “punish” Scotland after a No vote. But the pledge of all three Unionist parties to give Holyrood “more powers” provides the smokescreen under which the abolition of Barnett can be executed and the English electorate placated.The block grant is a distribution of tax revenue. The “increased devolution” plans of the UK parties will instead make the Scottish Government responsible for collecting its own income taxes. The Office of Budget Responsibility has explained in detail how “the block grant from the UK government to Scotland will then be reduced to reflect the fiscal impact of the devolution of these tax-raising powers.” (page 4).But if Holyrood sets Scottish income tax at the same level as the UK, that’ll mean the per-person receipts are also the same, which means that there won’t be the money to pay for the “extra” £1400 of spending currently returned as part-compensation for Scottish oil revenues, because the oil revenues will be staying at Westminster. ...We’ve explained the political motivations behind the move at length before. The above is simply the mechanical explanation of how it will happen if Scotland votes No. The“if” is not in question – all the UK parties are united behind the plan.A gigantic act of theft will be disguised as a gift. The victories of devolution will be lost, because there’ll no longer be the money to pay for them. Tuition fees and prescription charges will return. Labour’s “One Nation” will manifest itself, with the ideologically troublesome differences between Scotland and the rest of the UK eliminated.And what’s more, it’ll all have been done fairly and above-board, because the Unionist parties have all laid out their intentions in black and white. They’ll be able to say, with justification, “Look, you can’t complain, this is exactly what we TOLD you we’d do”.This analysis looks persuasive to me, and I've not seen it put so clearly elsewhere. Please comment below if you know sources for similar arguments.  

Transgressing the limits

Planet Haskell - 11 hours 18 min ago
Today, the 14th of January 2014, we had a special session of our Theory Lunch. I spoke about ultrafilters and how they allow to generalize the notion of limit. Consider the space of bounded sequences of real numbers, together with the … Continue reading →

The fundamental problem of programming language package management

Planet Haskell - 11 hours 18 min ago
Why are there so many goddamn package managers? They sprawl across both operating systems (apt, yum, pacman, Homebrew) as well as for programming languages (Bundler, Cabal, Composer, CPAN, CRAN, CTAN, EasyInstall, Go Get, Maven, npm, NuGet, OPAM, PEAR, pip, RubyGems, etc etc etc). "It is a truth universally acknowledged that a programming language must be […]

SmartChecking Matt Might’s Red-Black Trees

Planet Haskell - 11 hours 18 min ago
Matt Might gave a nice intro to QuickCheck via testing red-black trees recently. Of course, QuickCheck has been around for over a decade now, but it’s still useful (if underused–why aren’t you QuickChecking your programs!?). In a couple of weeks, I’m presenting a paper on an alternative to QuickCheck called SmartCheck at the Haskell Symposium. SmartCheck […]

IAP: Speeding up conduit

Planet Haskell - 11 hours 18 min ago
This post contains fragments of active Haskell code, best viewed and executed at https://www.fpcomplete.com/blog/2014/08/iap-speeding-up-conduit As most of us know, performance isn't a one-dimensional spectrum. There are in fact multiple different ways to judge performance of a program. A commonly recognized tradeoff is that between CPU and memory usage. Often times, a program can be sped up by caching more data, for example.conduit is a streaming data library. In that sense, it has two very specific performance criterion it aims for:Constant memory usage.Efficient usage of scarce resources, such as closing file descriptors as early as possible.While CPU performance is always a nice goal, it has never been my top priority in the library's design, especially given that in the main use case for conduit (streaming data in an I/O context), the I/O cost almost always far outweighs any CPU overhead from conduit.However, for our upcoming Integrated Analysis Platform (IAP) release, this is no longer the case. conduit will be used in tight loops, where we do need to optimize for the lowest CPU overhead possible.This blog post covers the first set of optimizations I've applied to conduit. There is still more work to be done, and throughout this blogpost I'll be describing some of the upcoming changes I am attempting.I'll give a brief summary up front:Applying the codensity transform results in much better complexity of monadic bind.We're also less reliant on rewrite rules firing, which has always been unreliable (and now I know why).This change does represent a breaking API change. However, it only affects users of the Data.Conduit.Internal module. If you've just been using the public API, your code will be unaffected, besides getting an automatic speedup.These changes will soon be released as conduit 1.2.0, after a period for community feedback.Note that this blog post follows the actual steps I went through (more or less) in identifying the performance issues I wanted to solve. If you want to skip ahead to the solution itself, you may want to skip to the discussion on difference lists, or even straight to continuation passing style, church-encoding, codensity.By the way, after I originally wrote this blog post, I continued working on the optimizations I describe as possible future enhancements. Those are actually working out far better than I expected, and it looks like conduit 1.2.0 will be able to ship with them. I'll be writing a separate blog post detailing those changes. A bit of a teaser is: for vector-equivalent code, conduit now generates identical core as vector itself.The benchmarksBefore embarking on any kind of serious optimizations, it's important to have some benchmarks. I defined three benchmarks for the work I was going to be doing:A simple sum: adding up the numbers from 1 to 10000. This is to get a baseline of the overhead coming from conduit.A monte carlo analysis: This was based on a previous IAP blog post. I noticed when working on that benchmark that, while the conduit solution was highly memory efficient, there was still room to speed up the benchmark.Sliding vectors: Naren Sundar recently sent a sliding windows pull requests, which allow us to get a view of a fixed size of a stream of values. This feature is very useful for a number of financial analyses, especially regarding time series.Naren's pull request was based on immutable data structures, and for those cases it is highly efficient. However, it's possible to be far more memory efficient by writing to a mutable vector instead, and then taking immutable slices of that vector. Mihaly Barasz sent a pull request for this feature, and much to our disappointment, for small window sizes, it performed worse than sliding windows. We want to understand why.You can see the benchmark code, which stays mostly unchanged for the rest of this blog post (a few new cases are added to demonstrate extra points). The benchmarks always contain a low-level base case representing the optimal performance we can expect from hand-written Haskell (without resorting to any kind of FFI tricks or the like).You can see the first run results which reflect conduit 1.1.7, plus inlining of a few functions. Some initial analysis:Control.Monad.foldM is surpringly slow.Data.Conduit.List.foldM has a rather steep performance hit versus Data.Conduit.List.fold.There's a very high overhead in the monte carlo analysis.For sliding vector, the conduit overhead is more pronounced at smaller window sizes.But even with large window sizes, mutable vector conduits still have a large overhead. The sliding window/immutable approach, however, shows almost no overhead.That hopefully sets the scene enough for us to begin to dive in.Rewrite rules: liftGHC offers a very powerful optimization technique: rewrite rules. This allows you to tell the compiler that a certain expression can be rewritten to a more efficient one. A common example of a rewrite rule would be to state that map f . map g is the same as map (f . g). This can be expressed as:{-# RULES "map f . map g" forall f g. map f . map g = map (f . g) #-}Note that GHC's list rewrite rules are actually more complicated than this, and revolve around a concept called build/foldr fusion.Let's look at the implementation of the yield function in conduit (with some newtypes stripped away):yield :: Monad m => o -> ConduitM i o m () yield o = HaveOutput (Done ()) (return ()) o {-# INLINE [1] yield #-} {-# RULES "yield o >> p" forall o (p :: ConduitM i o m r). yield o >> p = HaveOutput p (return ()) o #-}The core datatype of conduit is recursive. The HaveOutput constructor contains a field for "what to do next." In the case of yield, there isn't anything to do next, so we fill that with Done (). However, creating that Done () value just to throw it away after a monadic bind is wasteful. So we have a rewrite rule to fuse those two steps together.But no such rewrite rule exists for lift! My first step was to add such a rule, and check the results. Unfortunately, the rule didn't have any real impact, because it wasn't firing. Let's put that issue to the side; we'll come back to it later.Cleanup, inliningOne of the nice features introduced in (I believe) GHC 7.8 is that the compiler will now warn you when a rewrite rule may not fire. When compiling conduit, I saw messages like:Data/Conduit/List.hs:274:11: Warning: Rule "source/map fusion $=" may never fire because ‘$=’ might inline first Probable fix: add an INLINE[n] or NOINLINE[n] pragma on ‘$=’ Data/Conduit/List.hs:275:11: Warning: Rule "source/map fusion =$=" may never fire because ‘=$=’ might inline first Probable fix: add an INLINE[n] or NOINLINE[n] pragma on ‘=$=’ Data/Conduit/List.hs:542:11: Warning: Rule "source/filter fusion $=" may never fire because ‘$=’ might inline first Probable fix: add an INLINE[n] or NOINLINE[n] pragma on ‘$=’ Data/Conduit/List.hs:543:11: Warning: Rule "source/filter fusion =$=" may never fire because ‘=$=’ might inline first Probable fix: add an INLINE[n] or NOINLINE[n] pragma on ‘=$=’ Data/Conduit/List.hs:552:11: Warning: Rule "connect to sinkNull" may never fire because ‘$$’ might inline first Probable fix: add an INLINE[n] or NOINLINE[n] pragma on ‘$$’This demonstrates an important interaction between inlining and rewrite rules. We need to make sure that expressions that need to be rewritten are not inlined first. If they are first inlined, then GHC won't be able to rewrite them to our more optimized version.A common approach to this is to delay inlining of functions until a later simplification phase. The GHC simplification process runs in multiple steps, and we can state that rules and inlining should only happen before or after a certain phase. The phases count down from 2 to 0, so we commonly want to delay inlining of functions until phase 0, if they may be subject to rewriting.Conversely, some functions need to be inlined before a rewrite rule can fire. In stream fusion, for example, the fusion framework depends on the following sequencing to get good performance:map f . map g -- inline map unstream . mapS f . stream . unstream . mapS g . stream -- rewrite stream . unstream unstream . mapS f . mapS g . stream -- rewrite mapS . mapS unstream . mapS (f . g) . streamIn conduit, we need to make sure that all of this is happening in the correct order. There was one particular complexity that made it difficult to ensure this happened. conduit in fact has two core datatypes: Pipe and ConduitM, with the latter being a more friendly newtype wrapper around the first. Up until this point, the code for the two was jumbled into a single internal module, making it difficult to track which things were being written in which version of the API.My next step was to split things into .Pipe and .Conduit internal modules, and then clean up GHC's warnings to get rules to fire more reliably. This gave a modest performance boost to the sliding vector benchmarks, but not much else. But it does pave the way for future improvements.Getting serious about sum, by cheatingThe results so far have been uninspiring. We've identified a core problem (too many of those Done data constructors being used), and noticed that the rewrite rules that should fix that don't seem to be doing their job. Now let's take our first stab at really improving performance: with aggressive rewrite rules.Our sum benchmark is really simple: use enumFromTo to create a stream of values, and fold (or foldM) to consume that. The thing that slows us down is that, in between these two simple functions, we end up allocating a bunch of temporary data structures. Let's get rid of them with rewrite rules!This certainly did the trick. The conduit implementation jumped from 185us to just 8.63us. For comparison, the low level approach (or vector's stream fusion) clocks in at 5.77us, whereas foldl' on a list is 80.6us. This is a huge win!But it's also misleading. All we've done here is sneakily rewritten our conduit algorithm into a low-level format. This solves the specific problem on the table (connecting enumFromTo with fold), but won't fully generalize to other cases. A more representative demonstration of this improvement is the speedup for foldM, which went from 1180us to 81us. The reason this is more realistic is that the rewrite rule is not specialized to enumFromTo, but rather works on any Source.I took a big detour at this point, and ended up writing an initial implementation of stream fusion in conduit. Unfortunately, I ran into a dead end on that branch, and had to put that work to the side temporarily. However, the improvements discussed in the rest of this blog post will hopefully reopen the door to stream fusion, which I hope to investigate next.Monte carlo, and associativityNow that I'd made the results of the sum benchmark thoroughly useless, I decided to focus on the results of monte carlo, where the low level implementation still won by a considerable margin (3.42ms vs 10.6ms). The question was: why was this happening? To understand, let's start by looking at the code:analysis = do successes <- sourceRandomN count $$ CL.fold (\t (x, y) -> if (x*x + y*(y :: Double) < 1) then t + 1 else t) (0 :: Int) return $ fromIntegral successes / fromIntegral count * 4 sourceRandomN :: (MWC.Variate a, MonadIO m) => Int -> Source m a sourceRandomN cnt0 = do gen <- liftIO MWC.createSystemRandom let loop 0 = return () loop cnt = do liftIO (MWC.uniform gen) >>= yield >> loop (cnt - 1) loop cnt0The analysis function is not very interesting: it simply connects sourceRandomN with a fold. Given that we now have a well behaved and consistently-firing rewrite rule for connecting to folds, it's safe to say that was not the source of our slowdown. So our slowdown must be coming from:liftIO (MWC.uniform gen) >>= yield >> loop (cnt - 1)This should in theory generate really efficient code. yield >> loop (cnt - 1) should be rewritten to \x -> HaveOutput (loop (cnt - 1)) (return ()) x), and then liftIO should get rewritten to generate:PipeM $ do x <- MWC.uniform gen return $ HaveOutput (loop $ cnt - 1) (return ()) xI added another commit to include a few more versions of the monte carlo benchmark (results here). The two most interesting are:Explicit usage of the Pipe constructors:sourceRandomNConstr :: (MWC.Variate a, MonadIO m) => Int -> Source m a sourceRandomNConstr cnt0 = ConduitM $ PipeM $ do gen <- liftIO MWC.createSystemRandom let loop 0 = return $ Done () loop cnt = do x <- liftIO (MWC.uniform gen) return $ HaveOutput (PipeM $ loop (cnt - 1)) (return ()) x loop cnt0This version ran in 4.84ms, vs the original conduit version which ran in 15.8ms. So this is definitely the problem!Explicitly force right-associated binding order:sourceRandomNBind :: (MWC.Variate a, MonadIO m) => Int -> Source m a sourceRandomNBind cnt0 = lift (liftIO MWC.createSystemRandom) >>= \gen -> let loop 0 = return () loop cnt = do lift (liftIO $ MWC.uniform gen) >>= (\o -> yield o >> loop (cnt - 1)) in loop cnt0Or to zoom in on the important bit:lift (liftIO $ MWC.uniform gen) >>= (\o -> yield o >> loop (cnt - 1))By the monad laws, this code is identical to the original. However, instead of standard left-associativity, we have right associativity or monadic bind. This code ran in 5.19ms, an approximate threefold speedup vs the left associative code!This issue of associativity was something Roman Cheplyaka told me about back in April, so I wasn't surprised to see it here. Back then, I'd looked into using Codensity together with ConduitM, but didn't get immediate results, and therefore postponed further research until I had more time.OK, so why exactly does left-associativity hurt us so much? There are two reasons actually:Generally speaking, many monads perform better when they are right associated. This is especially true for free monads, of which conduit is just a special case. Janis Voigtl ̈ander's paper Asymptotic Improvement of Computations over Free Monads and Edward Kmett's blog post series free monads for less do a far better job of explaining the issue than I could.In the case of conduit, left associativity prevented the lift and yield rewrite rules from firing, which introduced extra, unnecessary monadic bind operations. Forcing right associativity allows these rules to fire, avoiding a lot of unnecessary data constructor allocation and analysis.At this point, it became obvious at this point that the main slowdown I was seeing was driven by this problem. The question is: how should we solve it?Difference listsTo pave the way for the next step, I want to take a quick detour and talk about something simpler: difference lists. Consider the following code:(((w ++ x) ++ y) ++ z)Most experienced Haskellers will cringe upon reading that. The append operation for a list needs to traverse every cons cell in its left value. When we left-associate append operations like this, we will need to traverse every cell in w, then every cell in w ++ x, then every cell in w ++ x ++ y. This is highly inefficient, and would clearly be better done in a right-associated style (sound familiar?).But forcing programmers to ensure that their code is always right-associated isn't always practical. So instead, we have two common alternatives. The first is: use a better datastructure. In particular, Data.Sequence has far cheaper append operations than lists.The other approach is to use difference lists. Difference lists are functions instead of actual list values. They are instructions for adding values to the beginning of the list. In order to append, you use normal function composition. And to convert them to a list, you apply the resulting function to an empty list. As an example:type DList a = [a] -> [a] dlist1 :: DList Int dlist1 rest = 1 : 2 : rest dlist2 :: DList Int dlist2 rest = 3 : 4 : rest final :: [Int] final = dlist1 . dlist2 $ [] main :: IO () main = print finalBoth difference lists and sequences have advantages. Probably the simplest summary is:Difference lists have smaller constant factors for appending.Sequences allow you to analyze them directly, without having to convert them to a different data type first.That second point is important. If you need to regularly analyze your list and then continue to append, the performance of a difference list will be abysmal. You will constantly be swapping representations, and converting from a list to a difference list is an O(n) operation. But if you will simply be constructing a list once without any analysis, odds are difference lists will be faster.This situation is almost identical to our problems with conduit. Our monadic composition operator- like list's append operator- needs to traverse the entire left hand side. This connection is more clearly spelled out in Reflection without Remorse by Atze van der Ploeg and Oleg Kiselyov (and for me, care of Roman).Alright, with that out of the way, let's finally fix conduit!Continuation passing style, church-encoding, codensityThere are essentially two things we need to do with conduits:Monadically compose them to sequence two streams into a larger stream.Categorically compose them to connect one stream to the next in a pipeline.The latter requires that we be able to case analyze our datatypes, while theoretically the former does not: something like difference lists for simple appending would be ideal. In the past, I've tried out a number of different alternative implementations of conduit, none of which worked well enough. The problem I always ran into was that either monadic bind became too expensive, or categorical composition became too expensive.Roman, Mihaly, Edward and I discussed these issues a bit on Github, and based on Roman's advice, I went ahead with writing a benchmark of different conduit implementations. I currently have four implementations in this benchmark (and hope to add more):Standard, which looks very much like conduit 1.1, just a bit simplified (no rewrite rules, no finalizers, no leftovers).Free, which is conduit rewritten to explicitly use the free monad transformer.Church, which modifies Free to instead use the Church-encoded free monad transformer.Codensity, which is a Codensity-transform-inspired version of conduit.You can see the benchmark results, which clearly show the codensity version to be the winner. Though it would be interesting, I think I'll avoid going into depth on the other three implementations for now (this blog post is long enough already).What is Codensity?Implementing Codensity in conduit just means changing the ConduitM newtype wrapper to look like this:newtype ConduitM i o m r = ConduitM { unConduitM :: forall b. (r -> Pipe i i o () m b) -> Pipe i i o () m b }What this says is "I'm going to provide an r value. If you give me a function that needs an r value, I'll give it that r value and then continue with the resulting Pipe." Notice how similar this looks to the type signature of monadic bind itself:(>>=) :: Pipe i i o () m r -> (r -> Pipe i i o () m b) -> Pipe i i o () m bThis isn't by chance, it's by construction. More information is available in the Haddocks of kan-extension, or in the above-linked paper and blog posts by Janis and Edward. To see why this change is important, let's look at the new implementations of some of the core conduit functions and type classes:yield o = ConduitM $ \rest -> HaveOutput (rest ()) (return ()) o await = ConduitM $ \f -> NeedInput (f . Just) (const $ f Nothing) instance Monad (ConduitM i o m) where return x = ConduitM ($ x) ConduitM f >>= g = ConduitM $ \h -> f $ \a -> unConduitM (g a) h instance MonadTrans (ConduitM i o) where lift mr = ConduitM $ \rest -> PipeM (liftM rest mr)Instead of having explicit Done constructors in yield, await, and lift, we use the continuation rest. This is the exact same transformation we were previously relying on rewrite rules to provide. However, our rewrite rules couldn't fire properly in a left-associated monadic binding. Now we've avoided the whole problem!Our Monad instance also became much smaller. Notice that in order to monadically compose, there is no longer any need to case-analyze the left hand side, which avoids the high penalty of left association.Another interesting quirk is that our Monad instance on ConduitM no longer requires that the base m type constructor itself be a Monad. This is nice feature of Codensity.So that's half the story. What about categorical composition? That certainly does require analyzing both the left and right hand structures. So don't we lose all of our speed gains of Codensity with this? Actually, I think not. Let's look at the code for categorical composition:ConduitM left0 =$= ConduitM right0 = ConduitM $ \rest -> let goRight final left right = case right of HaveOutput p c o -> HaveOutput (recurse p) (c >> final) o NeedInput rp rc -> goLeft rp rc final left Done r2 -> PipeM (final >> return (rest r2)) PipeM mp -> PipeM (liftM recurse mp) Leftover right' i -> goRight final (HaveOutput left final i) right' where recurse = goRight final left goLeft rp rc final left = case left of HaveOutput left' final' o -> goRight final' left' (rp o) NeedInput left' lc -> NeedInput (recurse . left') (recurse . lc) Done r1 -> goRight (return ()) (Done r1) (rc r1) PipeM mp -> PipeM (liftM recurse mp) Leftover left' i -> Leftover (recurse left') i where recurse = goLeft rp rc final in goRight (return ()) (left0 Done) (right0 Done)In the last line, we apply left0 and right0 to Done, which is how we convert our Codensity version into something we can actually analyze. (This is equivalent to applying a difference list to an empty list.) We then traverse these values in the same way that we did in conduit 1.1 and earlier.The important difference is how we ultimately finish. The code in question is the Done clause of the goRight's case analysis, namely:Done r2 -> PipeM (final >> return (rest r2))Notice the usage of rest, instead of what we would have previously done: used the Done constructor. By doing this, we're immediately recreating a Codensity version of our resulting Pipe, which allows us to only traverse our incoming Pipe values once each, and not need to retraverse the outgoing Pipe for future monadic binding.This trick doesn't just work for composition. There are a large number of functions in conduit that need to analyze a Pipe, such as addCleanup and catchC. All of them are now implemented in this same style.After implementing this change, the resulting benchmarks look much better. The naive implementation of monte carlo is now quite close to the low-level version (5.28ms vs 3.44ms, as opposed to the original 15ms). Sliding vector is also much better: the unboxed, 1000-size window benchmark went from 7.96ms to 4.05ms, vs a low-level implementation at 1.87ms.Type-indexed sequencesOne approach that I haven't tried yet is the type-indexed sequence approach from Reflection without Remorse. I still intend to add it to my conduit benchmark, but I'm not optimistic about it beating out Codensity. My guess is that a sequence data type will have a higher constant factor overhead, and based on the way composition is implemented in conduit, we won't get any benefit from avoiding the need to transition between two representations.Edward said he's hoping to get an implementation of such a data structure into the free package, at which point I'll update my benchmark to see how it performs.To pursue next: streamProducer, streamConsumer, and moreWhile this round of benchmarking produced some very nice results, we're clearly not yet at the same level as low-level code. My goal is to focus on that next. I have some experiments going already relating to getting conduit to expose stream fusion rules. In simple cases, I've generated a conduit-compatible API with the same performance as vector.The sticking point is getting something which is efficient not just for functions explicitly written in stream style, but also provides decent performance when composed with the await/yield approach. While the latter approach will almost certainly be slower than stream fusion, I'm hoping we can get it to degrade to current-conduit performance levels, and allow stream fusion to provide a significant speedup when categorically composing two Conduits written in that style.The code discussed in this post is now available on the next-cps branch of conduit. conduit-extra, conduit-combinators, and a number of other packages either compile out-of-the-box with these changes, or require minor tweaks (already implemented), so I'm hoping that this API change does not affect too many people.As I mentioned initially, I'd like to have some time for community discussion on this before I make this next release.

Continuations and Exceptions

Planet Haskell - 11 hours 18 min ago
Summary: In moving Shake to continuations, exceptions were the biggest headache. I figured out how to somewhat integrate continuations and exception handling.The git repo for Shake now suspends inactive computations by capturing their continuation instead of blocking their thread, based on the continuations I described in a previous blog post. The most difficult part was managing exceptions. I needed to define a monad where I could capture continuations and work with exceptions, requiring the definitions:data M a = ... deriving (Functor, Applicative, Monad, MonadIO)throwM :: SomeException -> M acatchM :: M a -> (SomeException -> M a) -> M acaptureM :: ((a -> IO ()) -> IO ()) -> M aI'm using M as the name of the monad. I want equivalents of throwIO and catch for M, along with a function to capture continuations.The first observation is that since catchM must catch any exceptions, including those thrown by users calling error, then throwM can be defined as:throwM = liftIO . throwIOUsing throwIO gives better guarantees about when the exception is raised, compared to just throw.The second observation is that sometimes I want to raise an exception on the continuation, rather than passing back a value. I can build that on top of captureM with:captureM' :: ((Either SomeException a -> IO ()) -> IO ()) -> M acaptureM' k = either throwM return =<< captureM kThe third observation (which I observed after a few weeks trying not to follow it) is that the continuation may never be called, and that means you cannot implement a robust finallyM function. In particular, if the person who was intending to run the continuation themselves raises an exception, the continuation is likely to be lost. I originally tried to come up with schemes for defining the function passed the continuation to guarantee the continuation was called, but it became messy very quickly.The properties we expect of the implementation, to a rough approximation, include:catchM (x >> throwM e) (\_ -> y) >> z === x >> y >> z -- if you throw an exception inside a catchM, you must run the handler.captureM (\k -> x) >>= y === x -- if you execute something not using the continuation inside captureM it must behave like it does outside captureM. In particular, if the captureM is inside a catchM, that catchM must not catch the exception.captureM (\k -> k x) >>= y === x >>= y -- if you capture the continuation then continue that must be equivalent to not capturing the continuation.captureM (\k -> k x >> k x) >>= y === (x >>= y) >> (x >>= y) -- if you run the continuation twice it must do the same IO actions each time. In particular, if the first gets its exceptions caught, the second must do also.These properties are incomplete (there are other things you expect), and fuzzy (for example, the second property isn't type correct) - but hopefully they give an intuition.The implementation was non-trivial and (sadly) non-elegant. I suspect a better implementation is known in the literature, and I'd welcome a pointer. My implementation defines M as:type M a = ContT () (ReaderT (IORef (SomeException -> IO ())) IO) aHere we have a continuation monad wrapping a reader monad. The reader contains an IORef which stores the exception handler. The basic idea is that whenever we start running anything in M we call the Haskell catch function, and the exception handler forwards to the IORef. We can define catchM as:catchM :: M a -> (SomeException -> M a) -> M acatchM m hdl = ContT $ \k -> ReaderT $ \s -> do old <- liftIO $ readIORef s writeIORef s $ \e -> do s <- newIORef old hdl e `runContT` k `runReaderT` s `catch` \e -> ($ e) =<< readIORef s flip runReaderT s $ m `runContT` \v -> do s <- ask liftIO $ writeIORef s old k vWe store the previous exception handler as old, and insert a new one. After the code has finished (we have left the catchM block) we restore the old exception handler. In effect, we have a stack of exception handlers.When running the handler we pop off the current exception handler by restoring old, then since we have already used up our catch, we add a new catch to catch exceptions in the handler.We then define captureM as:captureM :: ((a -> IO ()) -> IO ()) -> M acaptureM f = ContT $ \k -> ReaderT $ \s -> do old <- readIORef s writeIORef s throwIO f $ \x -> do s <- newIORef old flip runReaderT s (k x) `E.catch` \e -> ($ e) =<< readIORef s writeIORef s throwIOWe make sure to switch the IORef back to throwIO before we start running the users code, and after we have finished running our code and switch back to user code. As a result, if the function that captures the continuation throws an exception, it will be raised as normal.When running the continuation we create a new IORef for the handler, since the continuation might be called twice in parallel, and the separate IORef ensures they don't conflict with each other.Finally, we need a way to run the computation. I've called that runM:runM :: M a -> (Either SomeException a -> IO ()) -> IO ()runM m k = do let mm = do captureM $ \k -> k () catchM (Right <$> m) (return . Left) s <- newIORef throwIO mm `runContT` (liftIO . k) `runReaderT` sThe signature of runM ends up being the only signature the makes sense given the underlying mechanisms. We define mm by using the facilities of captureM to insert a catch and catchM to ensure we never end up in an exception state from runM. The rest is just matching up the types.Stack depth could potentially become a problem with this solution. If you regularly do:captureM (\k -> k ())Then each time a catch will be wrapped around the function. You can avoid that by changing captureM to throw an exception:captureM :: ((a -> IO ()) -> IO ()) -> M acaptureM f = ContT $ \k -> ReaderT $ \s -> do old <- readIORef s writeIORef s $ \_ -> f $ \x -> do s <- newIORef old flip runReaderT s (k x) `E.catch` \e -> ($ e) =<< readIORef s throwIO anyExceptionHere we unwind the catch by doing a throwIO, after installing our exception handler which actually passes the continuation. It is a bit ugly, and I haven't checked if either the catch is a problem, or that this solution solves it.The implementation in Shake is a bit different to that described above. In Shake I know that captured continuations are never called more than once, so Ican avoid creating a new IORef in captureM, and I can reuse the existing one. Since I never change the handler, I can use a slightly less powerful definition of M:type M a = ReaderT (IORef (SomeException -> IO ())) (ContT () IO) aThe resulting code is Development.Shake.Monad, which implements the RAW monad, and also does a few extra things which are irrelevant to this post.The cool thing about Haskell is that I've been able to completely replace the underlying Shake Action monad from StateT/IO, to ReaderT/IO, to ReaderT/ContT/IO, without ever breaking any users of Shake. Haskell allows me to produce effective and flexible abstractions. 2014-08-20T17:39:00Z Neil Mitchell noreply@blogger.com

Maniac week postmortem

Planet Haskell - 11 hours 18 min ago
My maniac week was a great success! First things first: here’s a time-lapse video1 (I recommend watching it at the full size, 1280×720). Some statistics2: Total hours of productive work: 55.5 (74 pings) Average hours of work per day3: 11 … Continue reading →

Bluetooth on Haskell

Planet Haskell - 11 hours 18 min ago
I'm presenting a very early draft of my bluetooth library. As its name suggests, bluetooth is a Haskell frontend to low-level Bluetooth APIs, making it similar in spirit to Python's PyBluez and Java's BlueCove. What it can doCurrently, bluetooth only supports Linux. It has the capability of running an RFCOMM server and client. Theoretically, it should also support L2CAP servers and clients, although this has not been tested yet. What it will eventually doI plan to have bluetooth support each of the GHC Tier 1 platforms—that is, Windows, OS X, Linux, and FreeBSD. I want to have the capability to run the full gamut of L2CAP and RFCOMM-related functions on each OS, as well as any additional OS-specific functionality. MotivationBluetooth programming on Haskell is currently in a very primitive state. As of now, there are only two packages on Hackage that make any mention of Bluetooth (as far as I can tell):network hints in its Network.Socket module that there is an AF_BLUETOOTH socket address family. However, trying to use it with network will fail, since there is no corresponding Bluetooth SockAddr.simple-bluetooth by Stephen Blackheath offers some of what my own bluetooth package offers (namely, RFCOMM client capability on Windows and Linux).However, there is currently no comprehensive, cross-platform Haskell Bluetooth library à la PyBluez or BlueCove. I want bluetooth to fill that niche. How bluetooth worksbluetooth can be thought of as a wrapper around network. After all, Bluetooth programming is socket-based, so Network.Socket already provides most of what one needs to implement a Bluetooth server or client. There are several gotchas with Bluetooth programming, however: Every major OS has a completely different Bluetooth software stack. For example, Linux uses BlueZ, and Windows has several different stacks, including Winsock and Widcomm. Therefore, bluetooth is not likely to work identically on every OS.Windows in particular is challenging to support since several Winsock functions do not work correctly on the version of MinGW-w64 that is currently shipped with GHC for Windows (only the 64-bit version, no less). For this reason, I probably won't develop a Windows version of bluetooth until this issue is resolved.It is recommended that you have a basic understanding of Bluetooth programming before attempting to use bluetooth. I recommend this introduction by Albert Huang. ExamplesThe following are abridged examples of the RFCOMM client and server examples from the bluetooth repo. RFCOMM servermodule Main whereimport Data.Setimport Network.Bluetoothimport Network.Socketmain :: IO ()main = withSocketsDo $ do let uuid = serviceClassToUUID SerialPort proto = RFCOMM settings = defaultSDPInfo { sdpServiceName = Just "Roto-Rooter Data Router" , sdpProviderName = Just "Roto-Rooter" , sdpDescription = Just "An experimental plumbing router" , sdpServiceClasses = singleton SerialPort , sdpProfiles = singleton SerialPort } handshakeSock <- bluetoothSocket proto btPort <- bluetoothBindAnyPort handshakeSock anyAddr bluetoothListen handshakeSock 1 service <- registerSDPService uuid settings proto btPort (connSock, connAddr) <- bluetoothAccept handshakeSock putStrLn $ "Established connection with address " ++ show connAddr message <- recv connSock 4096 putStrLn $ "Received message! [" ++ message ++ "]" let response = reverse message respBytes <- send connSock response putStrLn $ "Sent response! " ++ show respBytes ++ " bytes." close connSock close handshakeSock closeSDPService serviceRFCOMM clientmodule Main whereimport Network.Bluetoothimport Network.Socketimport System.IOmain :: IO ()main = withSocketsDo $ do let addr = read "12:34:56:78:90:00" port = 1 sock <- bluetoothSocket RFCOMM bluetoothConnect sock addr port putStrLn "Established a connection!" putStr "Please enter a message to send: " hFlush stdout message <- getLine messBytes <- send sock message response <- recv sock 4096 putStrLn $ "Received reponse! [" ++ reponse ++ "]" close sock SyntaxHighlighter.highlight(); 2014-08-18T21:04:00Z Ryan Scott noreply@blogger.com

Fame at last!

Planet Haskell - 11 hours 18 min ago
I was reading the book "Haskell Data Analysis Cookbook" when suddenly, my name pops up! Funny to see a link to a 7 year old blog entry, who knew I would go down in history for a few line of codes for a perceptron? It's deep in Chapter 7, for those interested. Maybe this is a sign that I should abandon everything else and spend my time on AI, since it's obviously where fame and riches abound! Right...

Algebraic Effect Handlers, Twice

Planet Haskell - 11 hours 18 min ago
I have two new papers on algebraic effect handlers:Effect Handlers in ScopeNicolas Wu, Tom Schrijvers, Ralf Hinze.To appear at the Haskell Symposium 2014.Algebraic effect handlers are a powerful means for describing effectful computations. They provide a lightweight and orthogonal technique to define and compose the syntax and semantics of different effects. The semantics is captured by handlers, which are functions that transform syntax trees.Unfortunately, the approach does not support syntax for scoping constructs, which arise in a number of scenarios. While handlers can be used to provide a limited form of scope, we demonstrate that this approach constrains the possible interactions of effects and rules out some desired semantics.This paper presents two different ways to capture scoped constructs in syntax, and shows how to achieve different semantics by reordering handlers. The first approach expresses scopes using the existing algebraic handlers framework, but has some limitations. The problem is fully solved in the second approach where we introduce higher-order syntax.Heuristics Entwined with Handlers CombinedTom Schrijvers, Nicolas Wu, Benoit Desouter, Bart Demoen.To appear at the PPDP Symposium 2014.A long-standing problem in logic programming is how to cleanly separate logic and control. While solutions exist, they fall short in one of two ways: some are too intrusive, because they require significant changes to Prolog’s underlying implementation; others are lacking a clean semantic grounding. We resolve both of these issues in this paper.We derive a solution that is both lightweight and principled. We do so by starting from a functional specification of Prolog based on monads, and extend this with the effect handlers approach to capture the dynamic search tree as syntax. Effect handlers then express heuristics in terms of tree transformations. Moreover, we can declaratively express many heuristics as trees themselves that are combined with search problems using a generic entwining handler. Our solution is not restricted to a functional model: we show how to implement this technique as a library in Prolog by means of delimited continuations.

Haskell development job at Standard Chartered

Planet Haskell - 11 hours 18 min ago
The Strats team at Standard Chartered is hiring expert typed FP developers for Haskell dev roles in London. This is a “front office” finance role – meaning you will work directly with traders building software to automate and improve their efficiency. The role is very development focused, and you will use Haskell for almost all tasks: data analysis, DSLs, market data publishing, […]

xml-to-json – new version released, constant memory usage

Planet Haskell - 11 hours 18 min ago
I’ve released a new version (1.0.0) of xml-to-json, which aims to solve memory issues encountered when converting large XML files. The new version includes two executables: the regular (aka “classic”) version, xml-to-json, which includes the various features, and the newly added executable xml-to-json-fast, which runs with constant memory usage and can process files of arbitrary […]

Citation, Recitation, and Resuscitation

Planet Haskell - 11 hours 18 min ago
Citation is a necessary practice for any sort of intellectual engagement, whether formal or colloquial, and whether academic or activistic. It is crucial to give credit to the originators of ideas— for ethical honesty: to acknowledge those who've enlightened you; for professional honesty: to make clear where your contributions begin; and for intellectual honesty: to allow others to read the sources for themselves and to follow up on other extensions and criticisms of that work. When encountering a new idea or text, I often engage in a practice I call "encitation". In order to more thoroughly understand and ingrain a text's intellectual content, I try (temporarily) to view all other ideas and arguments through its lens. This is why when I was reading Whipping Girl I was citing it left and right, just as when I was reading Killing Rage I quoted it incessantly. To understand structuralism, I embraced the structuralist theory and viewed all things in structuralist terms; to understand functionalism, or Marxism, or Freudianism, or performativity, I did the same. Of course, every framework is incomplete and emphasizes certain things to the exclusion of observing others; so viewing the world entirely from within any single framework distorts your perception of reality. The point of the exercise is not to embrace the framework per se, it's to roleplay the embracing of it. The point of this roleplay is to come to understand the emphases and limitations of the framework— not abstractly but specifically. This is especially important for trying to understand frameworks you disagree with. When we disagree with things, the instinct is to discount everything they say. But it's intellectually dishonest to refuse to understand why you disagree. And it's counterproductive, since you cannot debunk the theory nor convince people to change their minds without knowing and addressing where they're coming from. I engage in encitation not only for anthropological or philosophical ideas, I also do it for mathematical ideas. By trying to view all of mathematics through a particular idea or framework, you come to understand both what it's good at and what it cannot handle. That's one of the things I really love about the way Jason Eisner teaches NLP and declarative methods. While it's brutal to give people a framework (like PCFGs or SAT solving) and then ask them to solve a problem just barely outside of what that framework can handle, it gives you a deep understanding of exactly where and why the framework fails. This is the sort of knowledge you usually have to go out into industry and beat your head against for a while before you see it. But certain fields, like anthropology and writing, do try to teach encitation as a practice for improving oneself. I wonder how much of Jason's technique comes from his background in psychology. Regardless, this practice is one which should, imo, be used (and taught explicitly) more often in mathematics and computer science. A lot of the arguing over OO vs FP would go away if people did this. Instead, we only teach people hybridized approaches, and they fail to internalize the core philosophical goals of notions like objects, functions, types, and so on. These philosophical goals can be at odds, and even irreconcilable, but that does not make one or the other "wrong". The problem with teaching only hybridized approaches is that this irreconcilability means necessarily compromising on the full philosophical commitment to these goals. Without understanding the full philosophical goals of these different approaches, we cannot accurately discuss why sometimes one philosophy is more expedient or practical than another, and yet why that philosophy is not universally superior to others. The thing to watch out for, whether engaging in the roleplay of encitation or giving citations for actual work, is when you start reciting quotes and texts like catechisms. Once things become a reflexive response, that's a sign that you are no longer thinking. Mantras may be good for meditation, but they are not good critical praxis. This is, no doubt, what Aoife is referring to when she castigates playing Serano says. This is also why it's so dangerous to engage with standardized narratives. The more people engage in recitations of The Narrative, the more it becomes conventionalized and stripped of whatever humanity it may once have had. Moreover, reiterating The Narrative to everyone you meet is the surest way to drive off anyone who doesn't believe in that narrative, or who believes the content but disagrees with the message. Even if I was "born this way", saying so doesn't make it any more true or any more acceptable to those who who would like Jesus to save me from myself. More to the point, saying so places undue emphasis on one very tiny aspect of the whole. I'd much rather convince people of the violent nature of gender enculturation, and get them to recognize the psychological damage that abuse causes, than get them to believe that transgender has a natal origin. As time goes on, we ask different questions. Consequently, we end up discarding old theories and embracing new ones when the old theory cannot handle our new questions. In our tireless pursuit of the "truth", educators are often reticent to teach defunct theories because we "know" they are "wrong". The new theory is "superior" in being able to address our new questions, but we often lose track of the crucial insights of the old theory along the way. For this reason, it's often important to revive old theories in order to re-highlight those insights and to refocus on old questions which may have become relevant once more. In a way, this revitalization is similar to encitation: the goal is not to say that the old theory is "right", the goal is to understand what the theory is saying and why it's important to say those things. But again, one must be careful. When new theories arise, practitioners of the immediately-old theory often try to derail the asking of new questions by overemphasizing the questions which gave rise to the preceding theory. This attempt to keep moribund theories on life support often fuels generational divides: the new theoreticians cannot admit to any positives of the old theory lest they undermine their own work, while the old theoreticians feel like they must defend their work against the unrelenting tide lest it be lost forever. I think this is part of why radfems have been spewing such vitriol lately. The theoretical framework of radical feminism has always excluded and marginalized trans women, sex workers, and countless others; but the framework does not justify doxxing, stalking, and harassing those women who dare refute the tenets of The Doctrine. This reactionary violence bears a striking resemblance to the violence of religious fundamentalists1. And as with the religious fundamentalists, I think the reactionary violence of radfems stems from living in a world they can no longer relate to or make sense of. Major changes in mathematics often result in similar conflicts, though they are seldom so violent. The embracing/rejection of constructivism as a successor to classical mathematics. The embracing/rejection of category theory as an alternative to ZFC set theory. Both of these are radical changes to the philosophical foundations of mathematical thought, and both of these are highly politicized, with advocates on both sides who refuse to hear what the other side is saying. Bob Harper's ranting and railing against Haskell and lazy evaluation is much the same. Yes, having simple cost models and allowing benign side effects is important; but so is having simple semantic models and referential transparency. From where we stand now, those philosophical goals seem to be at odds. But before we can make any progress on reconciling them, we must be willing to embrace both positions long enough to understand their crucial insights and to objectively recognize where and how both fail. [1] To be clear: I do not draw this analogy as a way of insulting radfems; only to try and make sense of their behavior. There are many religious people (even among those who follow literalist interpretations of their religious texts) who are not terrorists; so too, there are women who believe in the radfem ideology and don't support the behavior of TERFs, SWERFs, etc. It is important to recognize both halves of each community in order to make sense of either side's reactions; and it's important to try to understand the mechanism that leads to these sorts of splits. But exploring this analogy any further is off-topic for this post. Perhaps another time. ↩ Twitter Facebook Google+ Tumblr WordPress comments 2014-08-16T00:26:08Z

[leuzkdqp] Units

Planet Haskell - 11 hours 18 min ago
Some notes on dimensional quantities and type systems:Addition, subtraction, assignment, and comparison should fail if the units are incompatible.Multiplication, division, and exponentiation by a rational dimensionless power always work.  These operations assume commutativity.Distinguishing addition from multiplication vaguely reminds me of the difference between floating point and fixed point. Unit conversion: a quantity can be read in one set of units then shown in another set.  Abstractly it does not exist as a real number in either.Converting between different families of units requires exact linear algebra on rational numbers.In some functions, units pass through just fine.  Others, e.g., trigonometric, require dimensionless numbers.Not all dimensionless numbers are the same unit: adding an angle to the fine structure constant seems as meaningless as adding a foot to a volt.  But multiplying them could be reasonable.One can take any compound type with a dimensionless internal type and turn it into a new compound type with that internal type having units.  But should this be considered a "new" type?  Of course, this is useless unless the internal type defined arithmetic operations: "True" miles per hour seems meaningless.Creating such compound types is analogous to the "function" idea above by viewing a compound type as a data constructor function of a base type.  Constructors do not do operations which can fail, like addition, so the function always succeeds.Creating a list populated by successive time derivatives of position seems like a useful thing to be able do.  But every element of the list will have different dimensions, which violates the naive idea of a list being items all of the same type.We would like to catch all dimensionality errors at compile time, but this may not be possible.  The extreme example would be implementing the "units" program.  Is that an anomaly?It is OK to add a vector to a coordinate (which has an origin) but not a coordinate to a coordinate.  There seems to be a concept of units and "delta" units.It is OK to subtract coordinates to get a delta.Maybe multiplying coordinates is also illegal.Coordinates versus vectors, units versus delta units, seems like an orthogonal problem to "regular" units.  Separate them in software so one can use either concept independently, for example, distinguishing dimensionless from delta dimensionless.Go further than just "delta" to distinguish first, second, etc., differences.An X component and Y component of a vector might have the same units, say, length, but one wants to avoid adding them, as this is typically a typo.  But sometimes, for rotations, one does add them.A Haskell Wiki page: http://www.haskell.org/haskellwiki/Physical_units. The units package seems promising.

Announcing Stackage Server

Planet Haskell - 11 hours 18 min ago
A New ServiceA couple months ago I made a post explaining Stackage server, its motivations and use-cases, and that it would be available in the coming months. It's now officially available in beta!Stackage server.As a quick recap: the essence of Stackage is that rather than publishing at the granularity of packages, like Hackage, it publishes at the granularity of package sets: Either everything builds together, or nothing is published until it does. We call these published things “snapshots.”Note: A snapshot is an exact image that can be reproduced at any time. With the snapshot's digest hash, you can download and install the same index and install packages based on that index all the time. Subsequently generated snapshots have no effect on previous ones.I've been using it for a couple months for every project I've worked on, private and public. It's perfect for application developers and teams who want to share a common always-building package set. Provided you're using one of the 500+ packages we're publishing in the snapshots, there will always be a build plan for the package you want to use in your project.And if your library is in Stackage, as explained in the previous post, you will get a heads up on Github if your updates or other people's updates cause a build failure related to your library.How it WorksSnapshots are built every couple days. It takes about 16 hours to complete a build. You can view the build progress at jenkins.stackage.org.There are two types of snapshots published by FP Complete:Exclusive: this excludes packages not specified in the Stackage configuration. This means anything that you try to install from this snapshot will have a build plan.Inclusive: this includes Hackage packages not known to build. If you try to install a package not tracked by Stackage, it may or may not build.You can use whichever suites your needs. If you want everything to always build, the former is an attractive choice. If you need to use a package not currently on Stackage, the latter choice makes sense.Try it Right NowChoose a snapshot. Each snapshot applies to a specific GHC version. For example, the latest (as of writing) GHC 7.8 build. You'll see something like this:To use, copy the following to your ~/.cabal/config:remote-repo: stackage:http://www.stackage.org/stackage/604a3649795771f6dd8b80bfd4eeb748e1d97599Note: Remove or comment out any existing remote-repo line.Run the following to update your packages:$ cabal updateIf you already have installed some packages, it's better to clear out your package set. See this page in the FAQ for how to do that.SandboxesHow does this interact with sandboxes? Good question. Here's the rundown:hsenv: Yes, works fine. Edit the .hsenv/cabal/config file and off you go.cabal sandbox: Not yet! There is an open issue about this. But I have tried cabal sandboxes inside hsenv, which worked.We've added this to the FAQ on the wiki. Contributions to this wiki page are welcome!FeedbackPersonally, I'm very satisfied with this service so far. I just use my existing tools with a different remote-repo.Others familiar with Nix have asked how they compare. They are very similar solutions in terms of versioning and curation (although Stackage has full-time maintenance); the main advantage to Stackage is that it just uses existing tools, so you don't have to learn a new tool and way of working to have a better user experience.We'd like feedback on a few points:Is the inclusive/exclusive separation useful?Is the process of using Stackage in an existing system (clearing the package set and starting fresh) easy?Should we establish a convention for storing Stackage snapshot hashes in projects source-tracking repositories?And any other feedback you come up with while using it.Stackage for businessesAs part of my last announcement for Stackage I mentioned there will also be custom services for businesses looking to build their development platform on Stackage.These commercial services include:Premium support - FP Complete will quickly respond and make improvements or fixes to the public Stackage server as they need to happen.Private snapshots with premium support - very helpful for commercial users looking to add proprietary or custom libraries.Validated pre-compiled build images based on public or private snapshots. These can be used on developer systems or automated build systems.Packaged Jenkins server using the pre-compiled build images.All these additional commercial services are meant to be helpful add-ons and we look forward to hearing more about what features you think would be beneficial to you. For more information email us at: sales@fpcomplete.com

Safe library - generalising functions

Planet Haskell - 11 hours 18 min ago
Summary: The Safe library now has exact versions of take/drop, with twelve functions implemented on top of a generalised splitAt. The Safe library is a simple Haskell library that provides versions of standard Prelude and Data.List functions that usually throw errors (e.g. tail), but wrapped to provide better error messages (e.g. tailNote), default values (e.g. tailDef) and Maybe results (e.g. tailMay).I recently released version 0.3.5, which provides a new module Safe.Exact containing crashing versions of functions such as zip/zipWith (which error if the lists are not equal length) and take/drop/splitAt (which error if there are not enough elements), then wraps them to provide safe variants. As an example, the library provides:takeExact :: Int -> [a] -> [a]takeExactMay :: Int -> [a] -> Maybe [a]These are like take, but if the Int is larger than the length of the list it will throw an error or return Nothing. Some sample evaluations:takeExactMay 2 [1,2,3] == Just [1,2]takeExact 2 [1,2,3] == [1,2]takeExactMay 2 [1] == NothingtakeExact 2 [1] == 1:error "Safe.Exact.takeExact, index too large, index=2, length=1"take 1 (takeExact 2 [1]) == [1]So takeExactMay computes up-front whether the whole computation will succeed, and returns a Nothing if it will fail. In contrast, takeExact produces elements while they are present, but if you demand an additional element that is missing it will result in an error. All the exceptions in the Safe library are designed to provide the maximum level of detail about what went wrong, here telling us the index we were after and the length of the list.The library provides takeExact, dropExact and splitAtExact, plus Def/May/Note versions, resulting in twelve similar functions. While the implementation of any one function is reasonably short (although not that short, once proper error messages are provided), I didn't want to write the same code twelve times. However, generalising over functions that check up-front and those that check on-demand requires a bit of thought. In the end I settled for:splitAtExact_ :: (String -> r) -> ([a] -> r) -> (a -> r -> r) -> Int -> [a] -> rsplitAtExact_ err nil cons o xs | o < 0 = err $ "index must not be negative, index=" ++ show o | otherwise = f o xs where f 0 xs = nil xs f i (x:xs) = x `cons` f (i-1) xs f i [] = err $ "index too large, index=" ++ show o ++ ", length=" ++ show (o-i)Here the splitAtExact_ function has a parameterised return type r, along with three functional arguments that construct and consume the r values. The functional arguments are:err :: String -> r, says how to convert an error into a result value. For up-front checks this produces a Nothing, for on-demand checks this calls error.nil :: [a] -> r, says what to do once we have consumed the full number of elements. For take we discard all the remaining elements, for drop we are only interested in the remaining elements.cons :: a -> r -> r, says how to deal with one element before we reach the index. For take this will be (:), but for functions producing a Maybe we have to check the r parameter first.With this generalisation, I was able to write all twelve variants. As a few examples:addNote fun msg = error $ "Safe.Exact." ++ fun ++ ", " ++ msgtakeExact = splitAtExact_ (addNote "takeExact") (const []) (:)dropExact = splitAtExact_ (addNote "dropExact") id (flip const)takeExactMay = splitAtExact_ (const Nothing) (const $ Just []) (\a -> fmap (a:))dropExactMay = splitAtExact_ (const Nothing) Just (flip const)splitAtExact = splitAtExact_ (addNote "splitAtExact") (\x -> ([], x)) (\a b -> first (a:) b)splitAtExactMay = splitAtExact_ (const Nothing) (\x -> Just ([], x)) (\a b -> fmap (first (a:)) b)Normally I would have defined takeExact and dropExact in terms of fst/snd on top of splitAtExact. However, in the Safe library error messages are of paramount importance, so I go to additional effort to ensure the error says takeExact and not splitAtExact. 2014-08-12T21:08:00Z Neil Mitchell noreply@blogger.com

Similarities: Monoid, MonadPlus, Category

Planet Haskell - 11 hours 18 min ago
This is perhaps obvious to anyone who has thoroughly studied category theory, but the similarities between Monoid, MonadPlus, and Category, have really struck me lately. I’m going to take a smidgeon of artistic license to present this train of thought. … Continue reading → 2014-08-11T21:41:28Z 2014-08-11T21:41:28Z Dan Burton
Syndicate content