News aggregator

Shake's Internal State

Haskell on Reddit - Tue, 10/14/2014 - 1:04am
Categories: Incoming News

Haskell Introduction - YouTube - 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 ( 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 Software Engineer / Developer at Clutch Analytics/ Windhaven Insurance Cheers, Sean Murphy
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 ( 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 >> 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 >
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]

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: :? 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 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?


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