News aggregator

Haskell Introduction - YouTube

del.icio.us/haskell - Mon, 10/13/2014 - 10:08pm
Categories: Offsite Blogs

online tutorial

haskell-cafe - Mon, 10/13/2014 - 6:13pm
Hello, I want to learn haskell by using the fpcomplete site. Now I wonder if this ( https://www.fpcomplete.com/school/starting-with-haskell/haskell-fast-hard) is a good tutorial for a beginner. Roelof
Categories: Offsite Discussion

New Functional Programming Job Opportunities

haskell-cafe - Mon, 10/13/2014 - 5:00pm
Here are some functional programming job opportunities that were posted recently: Functional Software Engineer at Cake Solutions Ltd http://functionaljobs.com/jobs/8755-functional-software-engineer-at-cake-solutions-ltd Software Engineer / Developer at Clutch Analytics/ Windhaven Insurance http://functionaljobs.com/jobs/8753-software-engineer-developer-at-clutch-analytics-windhaven-insurance Cheers, Sean Murphy FunctionalJobs.com
Categories: Offsite Discussion

Proposal: Add isSubsequenceOf to Data.List

libraries list - Mon, 10/13/2014 - 4:34pm
Data.List has `subsequences`, calculating all subsequences of a list, but it doesn't provide a function to check whether a list is a subsequence of another list. `isSubsequenceOf` would go into the "Predicates" section (http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html#g:12) which already contains: * isPrefixOf (dual of inits) * isSuffixOf (dual of tails) * isInfixOf With this proposal, we would add * isSubsequenceOf (dual of subsequences) Suggested implementation:
Categories: Offsite Discussion

Getting the haddocks back (was: documentation buildfailing in hackage?)

haskell-cafe - Mon, 10/13/2014 - 4:25pm
On Sun, Oct 12, 2014 at 4:50 AM, Mateusz Kowalczyk <fuuzetsu< at >fuuzetsu.co.uk> wrote: I agree! My understanding (which is at /least/ 2nd or 3rd hand) is that the doc builds were turned off intentionally because it was a security issue, and that they are unlikely to come back. Now, assuming that is the case, how can we solve the "there is no documentation" issue? Some ideas to kick-start discussion: - Provide an option to include haddocks in the sdist bundle, and extract them on Hackage for display. - Add a 'cabal uploadHaddock' - Run all haddock builds in a VM/docker container / etc.. that mitigates the security concerns. - ??? --Rogan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Neil Mitchell: Shake's Internal State

Planet Haskell - Mon, 10/13/2014 - 2:53pm

Summary: Shake is not like Make, it has different internal state, which leads to different behaviour. I also store the state in an optimised way.

Update: I'm keeping an up to date version of this post in the Shake repo, which includes a number of questions/answers at the bottom, and is likely to evolve over time to incorporate that information into the main text.

In order to understand the behaviour of Shake, it is useful to have a mental model of Shake's internal state. To be a little more concrete, let's talk about Files which are stored on disk, which have ModTime value's associated with them, where modtime gives the ModTime of a FilePath (Shake is actually generalised over all those things). Let's also imagine we have the rule:

file *> \out -> do
need [dependency]
run

So file depends on dependency and rebuilds by executing the action run.

The Make Model

In Make there is no additional state, only the file-system. A file is considered dirty if it has a dependency such that:

modtime dependency > modtime file

As a consequence, run must update modtime file, or the file will remain dirty and rebuild in subsequent runs.

The Shake Model

For Shake, the state is:

database :: File -> (ModTime, [(File, ModTime)])

Each File is associated with a pair containing the ModTime of that file, plus a list of each dependency and their modtimes, all from when the rule was last run. As part of executing the rule above, Shake records the association:

file -> (modtime file, [(dependency, modtime dependency)])

The file is considered dirty if any of the information is no longer current. In this example, if either modtime file changes, or modtime dependency changes.

There are a few consequences of the Shake model:

  • There is no requirement for modtime file to change as a result of run. The file is dirty because something changed, after we run the rule and record new information it becomes clean.
  • Since a file is not required to change its modtime, things that depend on file may not require rebuilding even if file rebuilds.
  • If you update an output file, it will rebuild that file, as the ModTime of a result is tracked.
  • Shake only ever performs equality tests on ModTime, never ordering, which means it generalises to other types of value and works even if your file-system sometimes has incorrect times.

These consequences allow two workflows that aren't pleasant in Make:

  • Generated files, where the generator changes often, but the output of the generator for a given input changes rarely. In Shake, you can rerun the generator regularly, and using a function that writes only on change (writeFileChanged in Shake) you don't rebuild further. This technique can reduce some rebuilds from hours to seconds.
  • Configuration file splitting, where you have a configuration file with lots of key/value pairs, and want certain rules to only depend on a subset of the keys. In Shake, you can generate a file for each key/value and depend only on that key. If the configuration file updates, but only a subset of keys change, then only a subset of rules will rebuild. Alternatively, using Development.Shake.Config you can avoid the file for each key, but the dependency model is the same.

Optimising the Model

The above model expresses the semantics of Shake, but the implementation uses an optimised model. Note that the original Shake paper gives the optimised model, not the easy to understand model - that's because I only figured out the difference a few days ago (thanks to Simon Marlow, Simon Peyton Jones and Andrey Mokhov). To recap, we started with:

database :: File -> (ModTime, [(File, ModTime)])

We said that File is dirty if any of the ModTime values change. That's true, but what we are really doing is comparing the first ModTime with the ModTime on disk, and the list of second ModTime's with those in database. Assuming we are passed the current ModTime on disk, then a file is valid if:

valid :: File -> ModTime -> Bool
valid file mNow =
mNow == mOld &&
and [fst (database d) == m | (d,m) <- deps]
where (mOld, deps) = database file

The problem with this model is that we store each File/ModTime pair once for the file itself, plus once for every dependency. That's a fairly large amount of information, and in Shake both File and ModTime can be arbitrarily large for user rules.

Let's introduce two assumptions:

Assumption 1: A File only has at most one ModTime per Shake run, since a file will only rebuild at most once per run. We use Step for the number of times Shake has run on this project.

Consequence 1: The ModTime for a file and the ModTime for its dependencies are all recorded in the same run, so they share the same Step.

Assumption 2: We assume that if the ModTime of a File changes, and then changes back to a previous value, we can still treat that as dirty. In the specific case of ModTime that would require time travel, but even for other values it is very rare.

Consequence 2: We only use historical ModTime values to compare them for equality with current ModTime values. We can instead record the Step at which the ModTime last changed, assuming all older Step values are unequal.

The result is:

database :: File -> (ModTime, Step, Step, [File])

valid :: File -> ModTime -> Bool
valid file mNow =
mNow == mOld &&
and [sBuild >= changed (database d) | d <- deps]
where (mOld, sBuilt, sChanged, deps) = database file
changed (_, _, sChanged, _) = sChanged

For each File we store its most recently recorded ModTime, the Step at which it was built, the Step when the ModTime last changed, and the list of dependencies. We now check if the Step for this file is greater than the Step at which dependency last changed. Using the assumptions above, the original formulation is equivalent.

Note that instead of storing one ModTime per dependency+1, we now store exactly one ModTime plus two small Step values.

We still store each file many times, but we reduce that by creating a bijection between File (arbitrarily large) and Id (small index) and only storing Id.

Implementing the Model

For those who like concrete details, which might change at any point in the future, the relevant definition is in Development.Shake.Database:

data Result = Result
{result :: Value -- the result when last built
,built :: Step -- when it was actually run
,changed :: Step -- when the result last changed
,depends :: [[Id]] -- dependencies
,execution :: Float -- duration of last run
,traces :: [Trace] -- a trace of the expensive operations
} deriving Show

The differences from the model are:

  • ModTime became Value, because Shake deals with lots of types of rules.
  • The dependencies are stored as a list of lists, so we still have access to the parallelism provided by need, and if we start rebuilding some dependencies we can do so in parallel.
  • We store execution and traces so we can produce profiling reports.
  • I haven't shown the File/Id mapping here - that lives elsewhere.
  • I removed all strictness/UNPACK annotations from the definition above, and edited a few comments.

As we can see, the code follows the optimised model quite closely.

Categories: Offsite Blogs

I'll give a brief talk about Haskell for a group of students, but my code is too slow. How can I improve it, without making it less elegant?

Haskell on Reddit - Mon, 10/13/2014 - 2:40pm

Hello, there is a class assignment on my school where teams must implement a graph library in a language of choice. Most of them are using C/C++/Java, so I find it a great opportunity to talk about Haskell. After all, seeing a problem you struggled to solve in 50 lines of C, in a single line of Haskell, certainly causes an impact. The idea is to define a single graphAlgorithm function, from which every other function on the assignment will be specialized in a single liner. Unfortunately, the performance of such approach will probably make Haskell look bad: calling a BFS takes ~14 seconds, while the same function, as I implemented in JavaScript, takes ~0.5 seconds. That is a 28x slowdown. Of course, the Haskell code is ridiculously high level and clean, whereas my JS implementation shuffled bits for performance. But the audience don't care about that. So, is there any way I can improve the performance of this code without altering it a lot?

module Graph (adjacencyListGraph, breadthFirstSearch) where import qualified Data.List as List import qualified Data.IntSet as Set import qualified Data.PriorityQueue.FingerTree as Queue import Data.Array type Node = Int type Weight = Int type Edge = (Node,Weight) type Graph = Node -> [Edge] data Queue element = Queue { insert :: element -> Queue element, extract :: (element, Queue element), empty :: Bool } stack :: Queue a stack = listToStack [] where listToStack container = Queue { insert = \node -> listToStack (node : container), extract = (head container, listToStack (tail container)), empty = List.null container } adjacencyListGraph :: Array Node [Edge] -> Graph adjacencyListGraph edgesArray node = edgesArray ! node neighbors :: Node -> Graph -> [Node] neighbors node graph = map fst (graph node) graphAlgorithm :: Queue Node -> Graph -> Node -> [Node] graphAlgorithm queue graph node = walk (insert queue node) Set.empty [] where walk queue visited result | empty queue = result | Set.member node visited = walk queueWithoutNode visited result | otherwise = walk queueWithNeighbors (Set.insert node visited) (node : result) where (node,queueWithoutNode) = extract queue queueWithNeighbors = List.foldl' insert queue (neighbors node graph) breadthFirstSearch :: Graph -> Node -> [Node] breadthFirstSearch = graphAlgorithm stack

Code on GitHub - run test.hs.

Profile info.

submitted by SrPeixinho
[link] [25 comments]
Categories: Incoming News

:sprint behaves differently in ghc 7.8.3 ?

Haskell on Reddit - Mon, 10/13/2014 - 1:30pm

In ghci, :sprint does not seem to work anymore:

@arch-docker ~ > ghci GHCi, version 7.8.3: http://www.haskell.org/ghc/ :? for help Prelude> let x = 1 + 2 Prelude> :sprint x x = _ Prelude> x 3 Prelude> :sprint x x = _

I have tried to google about this but could not find any pointer.

By the way, what would be the most appropriate place for this kind of question ?

submitted by pi3r
[link] [4 comments]
Categories: Incoming News

Kevin Reid (kpreid): Game idea: “Be Consistent”

Planet Haskell - Mon, 10/13/2014 - 11:46am

Here’s another idea for a video game.

The theme of the game is “be consistent”. It's a minimalist-styled 2D platformer. The core mechanic is that whatever you do the first time, the game makes it so that that was the right action. Examples of how this could work:

  • At the start, you're standing at the center of a 2×2 checkerboard of background colors (plus appropriate greebles, not perfect squares). Say the top left and bottom right is darkish and the other quadrants are lightish. If you move left, then the darkish stuff is sky, the lightish stuff is ground, and the level extends to the left. If you move right, the darkish stuff is ground, and the level extends to the right.

  • The first time you need to jump, if you press W or up then that's the jump key, or if you press the space bar then that's the jump key. The other key does something else. (This might interact poorly with an initial “push all the keys to see what they do”, though.)

  • <o>You meet a floaty pointy thing. If you walk into it, it turns out to be a pickup. If you shoot it or jump on it, it turns out to be an enemy.
  • If you jump in the little pool of water, the game has underwater sections or secrets. If you jump over the little pool, water is deadly.

Categories: Offsite Blogs

The New Haskell.org

Haskell on Reddit - Mon, 10/13/2014 - 11:31am
Categories: Incoming News

Questions about edX FP101x Introduction to Functional Programming

Haskell on Reddit - Mon, 10/13/2014 - 10:48am

I enrolled to FP101x which starts in a few days.

Since I signed up, I never seen the contests/syllabus does anybody know it?

In the MOOC says that the estimated effort is from 4-6 hours, is this accurate, I have my full time job and I wonder if I'll be able to keep up.

EXTRA: I tried to install Haskell Evaluation Virtual Machine but it alwasys fails/stalls anybody knows an alternate way to get it, or another vagrant VM for a good haskell environment?

thanks!

submitted by orlybg
[link] [15 comments]
Categories: Incoming News

value vs object orientation

haskell-cafe - Mon, 10/13/2014 - 4:36am
I was trying to explain to a colleague the difference in outlook between value and object orientation. I find some references like C#'s 'value-objects' vs the more usual 'reference-objects' But these kinds of references are very OOP-tilted. OTOH there are a few writings eg by Peter Wegner argung that the millennial philosophy divide between 'rationalism' and 'empiricism' corresponds to the division in programming between FP and OOP. Im looking for some more middle ground stuff -- not too stuck on one technological platform and yet not overly philosophical _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Tom Schrijvers: Mathematics of Program Construction (MPC 2015): first call for papers

Planet Haskell - Mon, 10/13/2014 - 2:30am
FIRST CALL FOR PAPERS

12th International Conference on Mathematics of Program Construction, MPC 2015
Königswinter, Germany, 29 June - 1 July 2015
http://www.cs.ox.ac.uk/conferences/MPC2015/


BACKGROUND

The MPC conferences aim to promote the development of mathematical principles
and techniques that are demonstrably practical and effective in the process
of constructing computer programs, broadly interpreted.

The 2015 MPC conference will be held in Königswinter, Germany, from 29th June
to 1st July 2015. The previous conferences were held in Twente, The
Netherlands (1989), Oxford, UK (1992), Kloster Irsee, Germany (1995),
Marstrand, Sweden (1998), Ponte de Lima, Portugal (2000), Dagstuhl, Germany
(2002), Stirling, UK (2004, colocated with AMAST), Kuressaare, Estonia (2006,
colocated with AMAST), Marseille, France (2008), Québec City, Canada (2010,
colocated with AMAST), and Madrid, Spain (2012).


TOPICS

Papers are solicited on mathematical methods and tools put to use in program
construction. Topics of interest range from algorithmics to support for
program construction in programming languages and systems. The notion of
"program" is broad, from algorithms to hardware. Some typical areas are type
systems, program analysis and transformation, programming-language semantics,
security, and program logics. Theoretical contributions are welcome, provided
that their relevance to program construction is clear. Reports on
applications are welcome, provided that their mathematical basis is evident.

We also encourage the submission of "pearls": elegant, instructive, and fun
essays on the mathematics of program construction.


IMPORTANT DATES

   * Submission of abstracts:      26 January 2015
   * Submission of full papers:     2 February 2015
   * Notification to authors:      16 March 2015
   * Final version:                13 April 2015


SUBMISSION

Submission is in two stages. Abstracts (plain text, 10 to 20 lines) must be
submitted by 26 January 2015. Full papers (pdf) adhering to the LaTeX llncs
style must be submitted by 2 February 2015. There is no official page limit,
but authors should strive for brevity. The web-based system EasyChair will be
used for submission (https://easychair.org/conferences/?conf=mpc2015).

Papers must report previously unpublished work, and must not be submitted
concurrently to a journal or to another conference with refereed proceedings.
Accepted papers must be presented at the conference by one of the authors.
Please feel free to write to mpc2015@easychair.org with any questions about
academic matters.

The proceedings of MPC 2015 will be published in Springer-Verlag's Lecture
Notes in Computer Science series, as have all the previous editions. Authors
of accepted papers will be expected to transfer copyright to Springer for
this purpose. After the conference, authors of the best papers will be
invited to submit revised versions to a special issue of the Elsevier journal
Science of Computer Programming.


PROGRAMME COMMITTEE

Ralf Hinze                University of Oxford, UK (chair)

Eerke Boiten              University of Kent, UK
Jules Desharnais          Université Laval, Canada
Lindsay Groves            Victoria University of Wellington, New Zealand
Zhenjiang Hu              National Institute of Informatics, Japan
Graham Hutton             University of Nottingham, UK
Johan Jeuring             Utrecht University and Open University, The Netherlands
Jay McCarthy              Vassar College, US
Bernhard Möller           Universität Augsburg, Germany
Shin-Cheng Mu             Academia Sinica, Taiwan
Dave Naumann              Stevens Institute of Technology, US
Pablo Nogueira            Universidad Politécnica de Madrid, Spain
Ulf Norell                University of Gothenburg, Sweden
Bruno C. d. S. Oliveira   The University of Hong Kong, Hong Kong
José Nuno Oliveira        Universidade do Minho, Portugal
Alberto Pardo             Universidad de la República, Uruguay
Christine Paulin-Mohring  INRIA-Université Paris-Sud, France
Tom Schrijvers            KU Leuven, Belgium
Emil Sekerinski           McMaster University, Canada
Tim Sheard                Portland State University, US
Anya Tafliovich           University of Toronto Scarborough, Canada
Tarmo Uustalu             Institute of Cybernetics, Estonia
Janis Voigtländer         Universität Bonn, Germany


VENUE

The conference will take place in Königswinter, Maritim Hotel, where
accommodation has been reserved. Königswinter is situated on the right bank
of the river Rhine, opposite Germany's former capital Bonn, at the foot of
the Siebengebirge.


LOCAL ORGANIZERS

Ralf Hinze                      University of Oxford, UK (co-chair)
Janis Voigtländer               Universität Bonn, Germany (co-chair)
José Pedro Magalhães            University of Oxford, UK
Nicolas Wu                      University of Oxford, UK

For queries about local matters, please write to jv@informatik.uni-bonn.de.
Categories: Offsite Blogs

Dependencies missing when building ghc.

glasgow-user - Mon, 10/13/2014 - 2:03am
Hi, I am with my new Ubuntu Trusty box. I have installed ghc by apt-get. Then I wanted to build ghc from git to upgrade to 7.8.3. I did following commands. I tried 'make clean', or reget the source. No luck yet. $ git clone --recursive git://git.haskell.org/ghc.git $ ./sync-all -r git://git.haskell.org remote set-url origin $ git checkout ghc-7.8.3-release $ ./sync-all get $ rm -r libraries/time # as prompted by sync-all $ ./sync-all get $ ./boot $ ./configure $ make ===--- building phase 0 make -r --no-print-directory -f ghc.mk phase=0 phase_0_builds make[1]: Nothing to be done for `phase_0_builds'. ===--- building phase 1 make -r --no-print-directory -f ghc.mk phase=1 phase_1_builds "inplace/bin/ghc-cabal" check libraries/haskell98 "inplace/bin/ghc-cabal" configure libraries/haskell98 dist-install "" --with-ghc="/home/local/ANT/shida/src/git/ghc/inplace/bin/ghc-stage1" --with-ghc-pkg="/home/local/ANT/shida/src/git/ghc/inplace/bin/ghc-pkg" --disable-library-for-ghci --enable-library-vanilla --enable
Categories: Offsite Discussion