News aggregator

Darcs: Darcs News #112

Planet Haskell - Sun, 04/03/2016 - 2:29pm
News and discussions
  1. After 7 years of being the maintainer/Benevolent Dictator of Darcs, Eric Kow stepped down and offered me (Guillaume Hoffmann) to take over, which I accepted:
  2. The release process of Darcs 2.12 will start when GHC 8 is released:
  3. We had two new minor releases of Darcs 2.10, and in spite of being minor, they contain a few interesting changes and optimizations:
  4. In a span of 4 months we had two sprints, one in Paris in September and another another in Seville in January, check out the reports:
  5. Finally, Pierre-Étienne Meunier announced a Pijul sprint in may in Finland. Darcs hackers are welcome!
Issues resolved (7)
issue2269 Eric Kow
issue2276 Eric Kow
issue2400 Ben Franksen
issue2459 Ben Franksen
issue2479 Ben Franksen
issue2481 Ganesh Sittampalam
issue2489 Guillaume Hoffmann
Patches applied (176)
2016-03-26 Sergei Trofimovich
  • allow zip-archive-0.3
2016-03-22 Guillaume Hoffmann
  • remove failing-issue1609 from testsuite as property we don't want
2016-03-06 Ben Franksen
  • move command: fixed punctuation of error messages and added a comment
  • use bug from impossible.h instead of error
  • cleanup in Darcs.Patch.Merge: use case instead of fromJust (do return ...)
2016-02-12 Ganesh Sittampalam
  • Get rid of the need for DummyPatch in Darcs.Patch.Match
2016-03-05 Guillaume Hoffmann
  • move runHLint.sh to root and update to run outside of testsuite
2016-02-12 Ganesh Sittampalam
  • drop re-exports from Darcs.Patch.Rebase
  • abstract out checking whether a Named is internal
  • add versions of simplifyPush[es] for Suspended
  • move addFixup to Rebase.Container and give it a clearer name
  • add Repair instance for Suspended
  • Ignore the rebase internal patch when showing dependencies
  • simplify instance ShowPatchBasic (RebaseSelect p)
  • break out PatchInspect instance for Suspended
  • rename mkSuspended to mkRebase and make it work on 'Suspended'
  • use Suspended instead of FL RebaseItem in takeRebase
  • break out RepairToFL instance for Suspended
  • break out ReadPatch instance for Suspended
  • break out Check instance for Suspended
  • break out Show instances for Suspended
  • break out Conflict instance for Suspended
  • break out Effect instance for Suspended
  • add PrimPatchBase instance for Suspended
  • break out ShowPatch instance for Suspended
  • break out Apply instance for Suspended
  • refactor instance ShowPatch Rebasing a bit
  • inline a couple of defaults to simplify future refactoring
  • abstract out an instance ShowPatchBasic Suspended
  • Introduce a 'Suspended' type to encapsulate 'FL RebaseItem'
2016-03-18 Ben Franksen
  • skip ssh tests if ssh server is down
  • made network ssh tests more robust by passing --skip-long-comment
  • fix ssh network tests so they work in the test harness
  • skip http network tests when server does not respond
  • run network tests by default
  • resolve issue2479: root dir most not be among the sources of a move
  • accept issue2479: bug descending in modifyTree
2016-03-08 Guillaume Hoffmann
  • update failing-issue2219
  • acknowledge that issue1196 is solved
  • acknowledge a working case in failing-index-argument.sh
  • merge HACKING into README.md
2016-02-17 Ganesh Sittampalam
  • get rid of a couple of trailing newlines
2016-02-05 Guillaume Hoffmann
  • remove unused executable and testsuite dependencies
  • comment in cabal file workaround
  • group all non-optional build-depends
  • remove unused darcs-test dependencies
  • comment use of flag REENTRANT
  • drop definition of HAVE_SIGINFO_H unused since 2009
  • hlint Darcs.Util.Diff.Patience
  • format patch names within 20 characters in dependencies output
  • show dependencies up to last tag by default
  • further merge hashed-storage code and tests into darcs code
  • bump second html dependency
  • darcs show dependencies
  • implement function getDeps
2016-01-28 Ganesh Sittampalam
  • fix git test involving deletions
2016-01-25 Guillaume Hoffmann
  • handle file moves and copies when importing from git
  • recommend using -M flag on git fast-export
  • tests related to git import of file moves
  • use F and T instead of From and To in whatsnew --machine-readable
  • bump dependencies lower bounds implied by requiring ghc 7.6
  • 2.10.3 changelog
2016-01-29 Ganesh Sittampalam
  • support transformers-compat 0.5.x
2016-01-25 Guillaume Hoffmann
  • avoid irrefutable pattern when importing unnamed commit
  • test for deleting empty directories on git import
  • delete empty directories on git import
  • rollback filename dequoting on import since now done during parsing
  • quoting and escaping of filenames in convert export and import
  • test for checking filepaths consistency with git
  • resolve issue2489: dequote filepaths while importing from git
2016-01-28 Ganesh Sittampalam
  • fix tests that use "git commit"
  • applyToTree is just a specialisation of applyToState
  • drop unnecessary constraint
  • simplify type
  • drop unused (and never defined) putApplyState
  • move the ObjectMap related code to the FileUUID patch type
  • disentangle the state-specific ApplyMonad methods
  • swap argument order to ApplyMonad/ApplyMonadTrans
  • Rename Prim.V3 to Prim.FileUUID
  • move listConflictedFiles out of Conflict class
  • Get rid of default implementation of conflictedEffect
  • Add some tests for how conflicts are reported
  • Drop an unnecessary call to patchcontents in applyAndFix
  • Drop unnecessary use of patchcontents in hunkmatch and touchmatch
2016-01-16 Guillaume Hoffmann
  • rename Patch and RealPatch to RepoPatchV1 and RepoPatchV2 in harness
  • rename Patch and RealPatch to RepoPatchV1 and RepoPatchV2 in darcs code
  • do not open patches uselessly when no file restriction given
  • add Darcs.Test.Patch.Selection and one unit test
  • convert import should be a RepoJob, not a V2Job
  • replace TaggedPatch by LabelledPatch in a comment
  • whatsnew --machine-readable help string update on file moves
  • --machine-readable flag for more parseable whatsnew
  • fix code inside of a comment
2016-01-16 Ganesh Sittampalam
  • resolve conflicts between changes to splitters and to hijacking
  • capture diffAlgorithm in splitters instead of passing it to SelectChanges unconditionally
  • drop unneeded export
  • simplify the PatchInspect (Rebasing p) instance
  • implement hunkMatches for PatchInfoAnd
  • move Rebasing out into its own module
  • break RebaseItem out into its own file
  • bump async dependency
  • conditionalise a couple of orphan instances
  • resolve conflict in build-tools removal
  • drop build-tools restriction
  • Bump time, HTTP dependencies
2016-01-15 Guillaume Hoffmann
  • set use-time-1point5 flag default to True to please stack
  • disable interfering env variable in issue1739 test
  • rename README to README.md to get it properly rendered
2016-01-15 Ganesh Sittampalam
  • resolve conflict between binary version bump and containers dep
  • bump binary, transformers and tar upper bounds
2016-01-14 Guillaume Hoffmann
  • make commit an alias for record
  • implement repoXor and show it in "show repo" output as "Weak Hash"
2015-12-28 Ganesh Sittampalam
  • Portability fix - #type nl_item isn't always Int32
  • add test that lost deps during rebase are reported on
  • remove unused fmapPIAP
2015-12-22 Guillaume Hoffmann
  • fix repo upgrade help string
2015-12-02 Ganesh Sittampalam
  • resolve issue2481: expose API for 'darcs diff' command
2015-11-20 Guillaume Hoffmann
  • remove a flag needed only for GHC < 7
  • remove -fno-warn-dodgy-imports from modules that were still using it
  • no longer hide catch from Prelude since we require ghc>=7.6
  • acknowledge -fno-warn-dodgy-imports is always needed
  • merge Darcs.Patch.ConflictMarking into Darcs.Patch.Conflict
2015-11-29 Ganesh Sittampalam
  • bump dependencies on vector, process, HUnit
  • force grep to treat output of locale as text
2015-11-20 Guillaume Hoffmann
  • Rename Darcs.Repository.LowLevel to Darcs.Repository.Pending
2012-08-09 Eric Kow
  • Haddock the pending patch parts of Darcs.Repository.State.
  • Make Darcs.Repository.isSimple apply over a whole list.
2015-11-09 Guillaume Hoffmann
  • rename NEWS to CHANGELOG to please hackagedb
  • fix release date of 2.10.2
  • update NEWS for 2.10.1 and 2.10.2
  • fix two tests after stopping using the word changes in pull message
  • shorter README with quickstart instructions
2015-11-06 Ganesh Sittampalam
  • add comments about the rejected 'hasDuplicate' cases
  • "Fix" some intermittent QuickCheck failures
  • disambiguate imports in some test code
  • Add an option to control the number of QuickCheck iterations
  • make test-framework imports explicit
2015-11-05 Guillaume Hoffmann
  • refactor breakAfterNthNewline and breakBeforeNthNewline
  • refactor clone code
  • download patches pack asynchronously
  • ignore meta- files in packs when cloning
  • comment in doOptimizeHTTP
2015-06-28 Ben Franksen
  • remove race from D.R.Packs, further simplify the code
2015-10-31 Guillaume Hoffmann
  • replace changes by log in release.sh
  • remove darcs.spec.in file from 2008
  • replace changes by log in Setup.lhs
  • update upload.cgi with new command names
  • update buildbot-try.sh with new command names
  • update cygwin-wrapper file with new commands names and flags
  • remove annotate xml schema no longer needed
  • remove patch index correctness and timing scripts from contrib
  • adapt tests to using patches word instead of changes
  • update commands names in help strings
2015-10-28 Ganesh Sittampalam
  • split issue1932 test up into a network and non-network part
  • Avoid subshells in amend-unrecord test
  • disable issue2086 test on Windows - umasks don't really work there
  • using mmap on Windows was causing test failures
  • warn when suspending "hijacked" patches in rebase pull and apply
  • be a bit clearer about patch names in hijack test
2015-09-20 Eric Kow
  • resolve issue2269: push hijack test to suspend time
  • resolve issue2276: Keep track of patch hijack decisions
  • Generalise hijack warning to support use in other commands
  • Helper to capitalize a sentence
2015-06-24 Ben Franksen
  • resolve issue2459: fall back to writing the file if createLink fails
  • resolve issue2400: use async package to keep track of unpack threads
  • removed special handling of --to-match from cloneRepository
2015-10-16 Guillaume Hoffmann
  • remove redundant import
2015-10-15 Ganesh Sittampalam
  • drop sandi lower bound to support GHC 7.4 and add an upper bound
2015-10-03 Daniil Frumin
  • Switch from dataenc (deprecated) to sandi
2015-10-09 Guillaume Hoffmann
  • replace changes by log in two help strings
2015-09-18 Eric Kow
  • Refactor darcs send patch count text snippet
  • Tidy darcs send msg code (shorter lines)
  • Fix typo in darcs send message
2015-09-19 Guillaume Hoffmann
  • make patch selection lazier in presence of matchers
  • get rid of selectChanges
  • inline patchSetToPatches in the only place where it is used
See darcs wiki entry for details.
Categories: Offsite Blogs

Fastest way to calculate all the ways to interleavetwo lists

haskell-cafe - Sun, 04/03/2016 - 4:05am
I ran into a fun question today: http://stackoverflow.com/q/36342967/1477667 Specifically, it asks how to find all ways to interleave lists so that the order of elements within each list is preserved. The most efficient way I found is copied below. It's nicely lazy, and avoids left-nested appends. Unfortunately, it's pretty seriously ugly. Does anyone have any idea of a way to do this that's both efficient and elegant? {-# LANGUAGE BangPatterns #-} import Data.Monoid import Data.Foldable (toList) import Data.Sequence (Seq, (|>))
Categories: Offsite Discussion

Names for Data.Sequence pattern synonyms

libraries list - Sun, 04/03/2016 - 1:07am
Milan Straka and I agree that we want Data.Sequence to offer pattern synonyms to make it more convenient to work with the ends of sequences. I wanted to check with everyone here what names to use. Relevant names already exposed: 1. <|, |>, and empty for cons, snoc, and empty 2. data ViewL a = EmptyL | a :< Seq a, and the equivalent on the right. I suggested Empty, :<<, and :>> as the pattern synonyms, the latter chosen for the relative convenience of the double tap. Milan suggested (correctly, I suspect) that the greater clarity of Empty, :<|, and :|> is worth the price in typing. _______________________________________________ Libraries mailing list Libraries< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Categories: Offsite Discussion

Roman Cheplyaka: Descending sort in Haskell

Planet Haskell - Sat, 04/02/2016 - 2:00pm

When confronted with a problem of sorting a list in descending order in Haskell, it is tempting to reach for a “lazy” solution reverse . sort.

An obvious issue with this is efficiency. While sorting in descending order should in theory be exactly as efficient as sorting in ascending order, the above solution requires an extra list traversal after the sorting itself is done.

This argument can be dismissed on the grounds that reverse’s run time, \(\Theta(n)\), is, in general, less than sort’s run time, \(O(n \log n)\), so it’s not a big deal. Additionally, one could argue that, unlike more complex solutions, this one is “obviously correct”.

As the rest of this article explains, neither of these claims holds universally.

Proper solutions

Here are the two ways to sort a list in descending order that I am aware of. Both require the more general sortBy function

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

The first argument to sortBy is the comparison function. For each pair of arguments it returns a value of type

data Ordering = LT | EQ | GT

which describes the ordering of those arguments.

The “standard” ordering is given by the compare function from the Ord typeclass. Thus, sort is nothing more than

sort = sortBy compare

The first solution to the descending sort problem exploits the fact that, to get the opposite ordering, we can simply swap around the two arguments to compare:

sortDesc = sortBy (flip compare)

The second solution relies on the comparing function from Data.Ord, which gives a particular way to compare two values: map them to other values which are then compared using the standard Ord ordering.

comparing :: Ord a => (b -> a) -> b -> b -> Ordering

This trick is often used in mathematics: to maximize a function \(x\mapsto f(x)\), it suffices to minimize the function \(x \mapsto -f(x)\). In Haskell, we could write

sortDesc = sortBy (comparing negate)

and it would work most of the time. However,

> sortDesc [1,minBound::Int] [-9223372036854775808,1]

Besides, negation only works on numbers; what if you want to sort a list of pairs of numbers?

Fortunately, Data.Ord defines a Down newtype which does exactly what we want: it reverses the ordering between values that it’s applied to.

> 1 < 2 True > Down 1 < Down 2 False

Thus, the second way to sort the list in descending order is

sortDesc = sortBy (comparing Down) Asymptotics <figure> </figure>

Thanks to Haskell’s laziness in general and the careful implementation of sort in particular, sort can run in linear time when only a fixed number of first elements is requested.

So this function will return the 10 largest elements in \(\Theta(n)\) time:

take 10 . sortBy (comparing Down)

While our “lazy” solution

take 10 . reverse . sort

(which, ironically, turns out not to be lazy enough – in the technical sense of the word “lazy”) will run in \(O(n \log n)\) time. This is because it requests the last 10 elements of the sorted list, and in the process of doing so needs to traverse the whole sorted list.

This may appear paradoxical if considered outside of the context of lazy evaluation. Normally, if two linear steps are performed sequentially, the result is still linear. Here we see that adding a linear step upgrades the overall complexity to \(O(n \log n)\).

Semantics

As I mentioned in the beginning, the simplicity of reverse . sort may be deceptive. The semantics of reverse . sort and sortBy (comparing Down) differ in a subtle way, and you probably want the semantics of sortBy (comparing Down).

This is because sort and sortBy are stable sorting functions. They preserve the relative ordering of “equal” elements within the list. Often this doesn’t matter because you cannot tell equal elements apart anyway.

It starts to matter when you use comparing to sort objects by a certain feature. Here we sort the list of pairs by their first elements in descending order:

> sortBy (comparing (Down . fst)) [(1,'a'),(2,'b'),(2,'c')] [(2,'b'),(2,'c'),(1,'a')]

According to our criterion, the elements (2,'b') and (2,'c') are considered equal, but we can see that their ordering has been preserved.

The revese-based solution, on the other hand, reverses the order of equal elements, too:

> (reverse . sortBy (comparing fst)) [(1,'a'),(2,'b'),(2,'c')] [(2,'c'),(2,'b'),(1,'a')]

Sort with care!

A note on sorted lists

Added on 2016-04-03

The original version of this article said that sort runs in \(\Theta(n \log n)\) time. @obadzz points out that this is not true: sort is implemented in such a way that it will run linearly when the list is already almost sorted in any direction. Thus I have replaced \(\Theta(n \log n)\) with \(O(n \log n)\) when talking about sort’s complexity.

<figure> </figure>
Categories: Offsite Blogs

Brent Yorgey: CCSC-Midsouth conference and programming contest

Planet Haskell - Sat, 04/02/2016 - 12:56pm

I’m in Memphis (again!) this weekend attending the 2016 CCSC Midsouth Regional Conference, which also has a student programming contest attached. I’m very proud of the two teams from Hendrix, who placed first and fifth out of 17 teams. This is now the third year in a row that a team from Hendrix has won the contest (though I had nothing to do with the first two!). The members of the winning team are all graduating this year, but each of the members of the other team will be around at least one more year, and I have talked to quite a few other students who are interested. I’m excited to continue building up a programming team with a tradition of excellence.


Categories: Offsite Blogs

Month in Haskell Mode March 2016

haskell-cafe - Fri, 04/01/2016 - 7:37pm
Welcome Haskell Mode users, Haskell Mode progress report for March 2016. For previous issue see February 2016 <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-February-2016>. Reddit discussion <https://www.reddit.com/r/haskell/comments/4cx7hc/month_in_haskell_mode_march_2016/> . <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-March-2016#what-is-haskell-mode>What is Haskell Mode? Haskell Mode is an umbrella project for multiple Emacs tools for efficient Haskell development. Haskell Mode is an open source project developed by a group of volunteers constantly looking for contributions. For more information how to help see https://github.com/haskell/haskell-mode. <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-March-2016#important-developments>Important developments We have noticed that haskell-mode project on Github is steadily growing in popularity and that is clearly visible on historical growth graph: [image: History of stars on github leading to
Categories: Offsite Discussion

Haskell hacking internships at LANL (Fall 2016,undergraduate)

General haskell list - Fri, 04/01/2016 - 4:12pm
We have an ongoing project developing an auto-parallelizing pure functional language implementation using GHC as the front end to dump Core or STG (much like Intel's approach here http://www.leafpetersen.com/leaf/publications/hs2013/hrc-paper.pdf). If you are a United States citizen or permanent resident alien studying computer science or mathematics at the undergraduate level with strong interests in Haskell programming, compiler/runtime development, and pursuing a fall semester (2016) internship at Los Alamos National Laboratory this could be for you. We don't expect applicants to necessarily already be highly accomplished Haskell programmers--such an internship is expected to be a combination of (further) developing your programming/Haskell skills and putting them to good use. If you're already a strong C hacker we could use that too. The application deadline is May 31, 2016. It's a bit of a process so don't leave inquiries until the last day. Email me if interested in more information,
Categories: Incoming News

[TFP 2016] Final call for papers

haskell-cafe - Fri, 04/01/2016 - 4:06pm
----------------------------- C A L L F O R P A P E R S ----------------------------- ======== TFP 2016 =========== 17th Symposium on Trends in Functional Programming June 8-10, 2016 University of Maryland, College Park Near Washington, DC http://tfp2016.org/ The symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming, taking a broad view of current and future trends in the area. It aspires to be a lively environment for presenting the latest research results, and other contributions (see below). Authors of draft papers will be invited to submit revised papers based on the feedback receive at the symposium. A post-symposium refereeing process will then select a subset of these articles for formal publication. TFP 201
Categories: Offsite Discussion

[TFP 2016] Final call for papers

General haskell list - Fri, 04/01/2016 - 4:06pm
----------------------------- C A L L F O R P A P E R S ----------------------------- ======== TFP 2016 =========== 17th Symposium on Trends in Functional Programming June 8-10, 2016 University of Maryland, College Park Near Washington, DC http://tfp2016.org/ The symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming, taking a broad view of current and future trends in the area. It aspires to be a lively environment for presenting the latest research results, and other contributions (see below). Authors of draft papers will be invited to submit revised papers based on the feedback receive at the symposium. A post-symposium refereeing process will then select a subset of these articles for formal publication. TFP 201
Categories: Incoming News

ARRAY 2016 extended deadline: April 11

General haskell list - Fri, 04/01/2016 - 2:53pm
*************************************************************************** CALL FOR PAPERS ARRAY 2016 3rd ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming Santa Barbara, CA, USA June 14, 2016 http://conf.researchr.org/home/array-2016/ EXTENDED DEADLINE: April 11, 2016 (FIRM!) *************************************************************************** ARRAY 2016 is part of PLDI 2016 37th Annual ACM SIGPLAN Conference on Programming Language Design and Implementation June 13-17, 2016 http://conf.researchr.org/home/pldi-2016/ *************************************************************************** About: Array-oriented pro
Categories: Incoming News

introspection -- towards type algebra

haskell-cafe - Fri, 04/01/2016 - 4:12am
I am looking for how far algebra on types in the manner of "set theory as an algebra" ¹ is possible. So for example in set theory one can compute for sets S, T S∪T, S∩T, S-T etc Is something similar possible for types? Say I have data Primary = Red|Green|Blue data Othercolors = Violet|Indigo|Yellow|Orange I want something like Rainbow = Primary ∪ Othercolors Equivalently if Rainbow and Primary had been defined, how to get/compute Rainbow - Primary? ------------------------- I thought the first-class types in Idris would be a good bet to try out at least a trivial prototype. Seems not... So asking here. Clearly and obviously one can use haskell to implement any language. My question is what/which are the introspective libraries/features of modern haskell that make this easy and lightweight. Thanks Rusi ¹ Yeah the term 'type algebra' may be taken in the sense of algebraic data types Cant think of a better one _______________________________________________ Haskell-Cafe mailing list Haskell-
Categories: Offsite Discussion

A better type signature for `forM_`

libraries list - Fri, 04/01/2016 - 12:21am
Hi all, I was recently faced with some unexpected behaviour from a piece of code that type checks and has zero warnings (even with -Wall). The code is below (and depends on the hashtables package). The error was using the <$> operator instead of the =<< operator. Using the former, it just builds up a list of IO actions that never get run. As pointed out to me on IRC (thanks pjdeport), chaning the type signature of `forM_` to forM_' :: (Monad m, Foldable t) => t a -> (a -> m ()) -> m () would have resulted in an error. Yes, this change would break existing code (breaking code would require an explicit `void $` inside the `forM_`) but does anyone else think this is a good idea? Erik import Control.Monad import qualified Data.HashTable.IO as HT type EvenCache = HT.BasicHashTable Int Bool main :: IO () main = do ht <- buildTable xs <- HT.toList ht putStrLn $ "cache: length " ++ show (length xs) buildTable :: IO EvenCache buildTable = do ht <- HT.new forM_ pairs $ \ (k,v) -
Categories: Offsite Discussion

Postdoc ad: quantum-computing programming languages

haskell-cafe - Thu, 03/31/2016 - 9:05pm
My institution just bought a D-Wave 2X adiabatic quantum computer. The problem is, no one really has a grasp on how to *program* an adiabatic quantum computer. It's a totally different beast from the gate-model quantum computers that most people imply when they talk about quantum computing. I'm looking to hire a postdoc to work with me on designing and implementing programming models suitable for execution on D-Wave-style quantum computers. The formal job ad can be found at http://tinyurl.com/jdlo556 or go to http://jobs.lanl.gov/ and look up job IRC49031. Disclaimer: This is not specifically a Haskell-hacking position, although you can use any language you want for the classical-side development. I'm posting here because a key skill I'm looking for is breadth of language knowledge. I see a candidate who knows nonstrict functional programming, declarative programming, and maybe a few "fringe" programming models as more valuable than one who knows only a dozen isomorphic imperative languages.
Categories: Offsite Discussion

Postdoc ad: quantum-computing programming languages

General haskell list - Thu, 03/31/2016 - 9:04pm
My institution just bought a D-Wave 2X adiabatic quantum computer. The problem is, no one really has a grasp on how to *program* an adiabatic quantum computer. It's a totally different beast from the gate-model quantum computers that most people imply when they talk about quantum computing. I'm looking to hire a postdoc to work with me on designing and implementing programming models suitable for execution on D-Wave-style quantum computers. The formal job ad can be found at http://tinyurl.com/jdlo556 or go to http://jobs.lanl.gov/ and look up job IRC49031. Disclaimer: This is not specifically a Haskell-hacking position, although you can use any language you want for the classical-side development. I'm posting here because a key skill I'm looking for is breadth of language knowledge. I see a candidate who knows nonstrict functional programming, declarative programming, and maybe a few "fringe" programming models as more valuable than one who knows only a dozen isomorphic imperative languages.
Categories: Incoming News

Type Checking Modular Multiple Dispatch with Parametric Polymorphism and Multiple Inheritance

Lambda the Ultimate - Thu, 03/31/2016 - 7:25pm

Type Checking Modular Multiple Dispatch with Parametric Polymorphism and Multiple Inheritance by Eric Allen, Justin Hilburn, Scott Kilpatrick, Victor Luchangco, Sukyoung Ryu, David Chase, Guy L. Steele Jr.:

In previous work, we presented rules for defining overloaded functions that ensure type safety under symmetric multiple dispatch in an object-oriented language with multiple inheritance, and we showed how to check these rules without requiring the entire type hierarchy to be known, thus supporting modularity and extensibility. In this work, we extend these rules to a language that supports parametric polymorphism on both classes and functions.

In a multiple-inheritance language in which any type may be extended by types in other modules, some overloaded functions that might seem valid are correctly rejected by our rules. We explain how these functions can be permitted in a language that additionally supports an exclusion relation among types, allowing programmers to declare “nominal exclusions” and also implicitly imposing exclusion among different instances of each polymorphic type. We give rules for computing the exclusion relation, deriving many type exclusions from declared and implicit ones.

We also show how to check our rules for ensuring the safety of overloaded functions. In particular, we reduce the problem of handling parametric polymorphism to one of determining subtyping relationships among universal and existential types. Our system has been implemented as part of the open-source Fortress compiler.

Fortress was briefly covered here a couple of times, as were multimethods and multiple dispatch, but this paper really generalizes and nicely summarizes previous work on statically typed modular multimethods, and does a good job explaining the typing rules in an accessible way. The integration with parametric polymorphism I think is key to applying multimethods in other domains which may want modular multimethods, but not multiple inheritance.

The Formalization in COQ might also be of interest to some.

Also, another interesting point is Fortress' use of second-class intersection and union types to simplify type checking.

Categories: Offsite Discussion

Yesod Web Framework: Fixing the Monad instance for Either

Planet Haskell - Thu, 03/31/2016 - 6:00pm

Over the years, much has been said about Either-like Monad instances. To summarize our history, we've had:

  • No Monad instance at all for Either
  • An orphan Monad instance in transformers that used the Error class
  • A Monad instance for Either in base without an Error constraint
  • The ErrorT transformer, which introduces the Error class constraints
  • The EitherT transformer from the eithert package
  • The newer ExceptT transformer, which greatly improves on EitherT by giving it a more intuitive name

I'm not going to dive into all of these points, I merely raise them to stress the idea of how many approaches have been attempted to get this right. I'd like to explain how our current situation is wrong, how we can do much better, and propose that – despite the large impact on all Haskell users out there to make such a change – we should finally fix our library ecosystem correctly, once and for all.

The broken fail function

The real crux of the matter here is that, as everyone knows, the Monad instance for Either is exclusively used for representing some kind of error/failure/exception/etc (all those terms are, of course, synonymous). In the past, with the Error constraint, we had a valid implementation of the fail method for Either, which meant this vital method was properly implemented. Unfortunately now, we have fail = error for Either, preventing us from doing proper exception handling without resorting to more complex tricks.

The problem with Error

If we look at the definition of the Error typeclass, we'll see two methods:

class Error a where noMsg :: a strMsg :: String -> a

However, there's a perfectly good implementation of noMsg in terms of strMsg: noMsg = strMsg "". So really, our Error typeclass boils down to just one method of type String -> a. Once we realize that, it turns out that there's a far more appropriate typeclass already present in base to represent errors:

class IsString a where fromString :: String -> aThe proper Monad Either instance

So now we can define a proper Monad instance for Either:

instance IsString e => Monad (Either e) where return = ... (>>=) = ... fail = Left . fromString

This allows us to recover a properly behaving fail function, restoring sanity to our world.

Either for arbitrary error types

The final issue we may wish to address is allowing Either to work for arbitrary types. We can do so by leveraging overlapping instances, one of the most powerful and ubiquitous language extensions available in GHC. Using Typeable, we can generate truly beautiful error messages for our usage of Either. Below is a proof of concept demonstrating how we can fully fix our Either situation in GHC.

{-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-} import Data.String import Data.Typeable data Either' a b = Left' a | Right' b deriving (Functor, Show) instance Applicative (Either' a) where pure = Right' Left' a <*> _ = Left' a Right' _ <*> Left' a = Left' a Right' f <*> Right' x = Right' (f x) instance IsString a => Monad (Either' a) where return = pure (>>) = (*>) Left' e >>= _ = Left' e Right' x >>= f = f x fail = Left' . fromString instance {-# OVERLAPPABLE #-} Typeable a => IsString a where fromString s = res where res = error $ concat [ "No specific IsString instance for " , show $ typeRep $ Just res , ", when converting string: " , s ] main :: IO () main = do print (fail "failure 1" :: Either' String Int) print ((do Just x <- return Nothing return x) :: Either' String Int) print ((do Just x <- return Nothing return x) :: Either' Int Int)What's next

I'm sure most of you are in full agreement with me at this point that this is our only way forward. Hopefully we can have a quick discussion period on the libraries@ list, and get this into base in time for GHC 8, which is currently on release candidate 37.

Categories: Offsite Blogs

hslua and language-lua need new maintainers

haskell-cafe - Thu, 03/31/2016 - 5:18pm
Hi all, I need new maintainers for my packages hslua[1] and language-lua[2]. None of these packages is super popular so it's not going to be a lot of work. I just need someone to take care of new issues and pull requests. + points if the maintainer is a user of the library :-) I just don't have time and motivation to maintain those as I'm not a user anymore. Some background, lanugage-lua was the first Haskell program I've written (according to git logs, 3 years 6 months ago). I maintained it over the years and used in some projects. Currently Eric Mertens (glguy) is also a maintainer who occasionally sends some patches, but I need someone to take care of the new issues and pull requests. One thing you may want to do is to merge Eric's patch that ports the parser to Happy (currently it's Parsec) and improves the performance significantly. hslua was originally written by Gracjan Polak. I was using it and sending some patches and eventually I became the maintainer, created a Git repo, wrote some blogs post
Categories: Offsite Discussion

Deriving Eq and Show instances for testing

haskell-cafe - Thu, 03/31/2016 - 4:43pm
I have datatypes for which I need an Eq and Show instance only for testing. I could derive those instances in the datatype declaration but I prefer not to add unnecessary functionality. With StandaloneDeriving extension I can derive the instances in the test module but this produces many warning about orphan instances. Is there a better approach or a way to stop reports about orphan instance warnings? Regards _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

ghc 7.10.3 crashes frequently on Windows

haskell-cafe - Thu, 03/31/2016 - 4:37pm
I have installed ghc from Haskell Platform version 7.10.3. When I run QuickCheck or HSpec tests interactively, every so often ghc crashes when I reload a file form withing Emacs and haskell mode. This problem manifested in earlier versions as well. Loading a file which does not contain tests never crashes ghc so far. How could I try to identify the cause of the crash? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Douglas M. Auclair (geophf): March 2016 1HaskellADay Problems and Solutions

Planet Haskell - Thu, 03/31/2016 - 12:54pm

Categories: Offsite Blogs