News aggregator

Constant time pattern matching and jump tables?

Haskell on Reddit - Wed, 08/05/2015 - 8:36pm

I have been reading quite a lot about pattern matching, and a little bit about jump tables as well. I still have a hard time understanding how does GHC enable us to do pattern matching in O(1).

I would be grateful if someone could enlighten me on this, or direct me to a comprehensive resource on the subject.

submitted by kalimeo
[link] [11 comments]
Categories: Incoming News

Performance problems, implementing an ASP solver in Haskell

Haskell on Reddit - Wed, 08/05/2015 - 2:15pm

Hi, I'm relatively new to Haskell. Comming from a logic programming background, I like it mostly because of its declarativeness. As a side project I'm developing an answer set solver in Haskell. Basically a SAT-solver for logic programs. Although I like the current design, it is unfortunately a terribly slow implementation. After profiling my program I found that most of the time is spend in the following functions.

COST CENTRE MODULE %time %alloc get_ng NGS 23.0 0.0 can_choose NGS 17.1 0.0 new_watch2i Types 15.3 39.7 new_watch1i Types 12.7 31.5 get_ng :: NoGoodStore -> Clause get_ng (NoGoodStore png lng _ _ counter) = if counter < length png then png!!counter else if counter < (length png) + (length lng) then lng!!(counter-length png) else error "NoGoodStore out of bounds" new_watch1i :: Clause -> Assignment -> Int -> Maybe Int new_watch1i (c,w,v) a i = if i < Vector.length c then if c!i == 0 then new_watch1i (c,w,v) a (i+1) else if i == v then new_watch1i (c,w,v) a (i+1) else if (a!i > 0 && c!i > 0) || (a!i < 0 && c!i < 0) then new_watch1i (c,w,v) a (i+1) else Just i else Nothing new_watch2i :: Clause -> Assignment -> Int -> Maybe Int new_watch2i (c,w,v) a i = if i < Vector.length c then if c!i == 0 then new_watch2i (c,w,v) a (i+1) else if i == w then new_watch2i (c,w,v) a (i+1) else if (a!i > 0 && c!i > 0) || (a!i < 0 && c!i < 0) then new_watch2i (c,w,v) a (i+1) else Just i else Nothing

You can find the complete code here Maybe you can have a look at the code and give me some tips on how to improve it.

submitted by robauke
[link] [17 comments]
Categories: Incoming News

Waiting for async exception (and nothing else)

haskell-cafe - Wed, 08/05/2015 - 11:43am
Hi, Is there an elegant way to have a thread wait for an async exception but nothing else? I tend to do something like forever $ threadDelay 1000000000 but this seems like a bit of a hack. Waiting on an otherwise-unused MVar or doing 'atomically retry' don't work because GHC kills them off straight away. The context is when using an API that only has a 'withMyThingy' wrapper and no explicit openMyThingy and closeMyThingy alternatives. Perhaps that's an API problem and the only way to work around this is with something a bit hacky? Cheers, _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

Syntax extension - adding import support tolet/where bindings

haskell-cafe - Wed, 08/05/2015 - 11:28am
Hi all, I'm sure this has come up before, but a quick bit of Googling didn't reveal any prior discussions (if you known any, let me know), so I'm kicking off a new discussion. I find myself wanting to be able to say something like: foo = ... where import Something.Specific The result would be to import the contents of Something.Specific into the scope of foo and its other where bindings, but not import into the rest of the module that foo is defined in. As a motivating example, I'm currently working on building some HTML in Haskell, and the amount of symbols that come into scope is huge, when you have a DSL for both CSS and HTML - the real pain point being that you get symbols that often conflict. Here's an example of something that doesn't type-check currently image = img [ width 50, style [ width (px 50) ] ] width here is both a symbol in the HTML DSL and the CSS DSL, but to get this to type check I need to write something like image = img [ HTML.width 50, style [ CSS.width (CSS.px 50) ] ] T
Categories: Offsite Discussion

Updating elements by key in hierarchical structure?

Haskell on Reddit - Wed, 08/05/2015 - 10:35am

Let's say you have something like

data Thing = Thing { key :: Key, ... , children :: [Thing] }

And you want to implement

modify :: (Thing -> Thing) -> Key -> Thing -> Thing

We can assume that keys are unique.

I'm somewhat interested in efficiency, though not extremely so. Mostly just looking for a somewhat elegant solution with decent performance characteristics.

I think I could figure out how to do it with the Plated stuff from lens... That would probably be good enough, coding-wise, even if it will do a depth-first search.

Since Thing is an abstract data type, I also have some thoughts about maintaining some kind of "index" of all keys, but I don't know what kind of thing the index would keep track of. A map of keys to lenses, perhaps?

It seems like a general enough problem that somebody ought to have come up with something clever.

submitted by mioloko
[link] [3 comments]
Categories: Incoming News

FP Complete: How stack can use Docker under the hood

Planet Haskell - Wed, 08/05/2015 - 10:00am
How stack can use Docker under the hood

TL;DR: if you just want to get started use stack's Docker support, see the Docker page on the stack wiki. The rest of this post gives background on the benefits, implementation, and reasons for our choices.

A brief history

Using LXC for containerization is an integral component of the FP Complete Haskell Center and School of Haskell, so lightweight virtualization was not new to us. We started tentative experiments using Docker for command-line development about a year ago and it quickly became an indispensable part of our development tool chain. We soon wrote a wrapper script that did user ID mapping and volume mounting so that developers could just prefix their usual cabal or build script commands with the wrapper and have them automagically run in a container without developers needing to adjust their usual workflow for Docker. The wrapper's functionality was integrated into an internal build tool and formed the core of its sandboxing approach. Then that internal build tool became stack which got its own non-Docker based sandboxing approach. But the basic core of that original wrapper script is still available, and there are significant benefits to using stack's Docker integration for teams.


The primary pain point we are solving with our use of Docker is ensuring that all developers are using a consistent environment for building and testing code.

Before Docker, our approach involved having developers all run the same Linux distribution version, install the same additional OS packages, and use hsenv sandboxes (and, as they stabilized, Cabal sandboxes) for Haskell package sandboxing. However, this proved deficient in several ways:

  • Some people develop on their primary workstation, so have additional software or different versions installed. Not everyone has a spare extra machine around or wants the overhead of developing in a "heavyweight" virtual machine (e.g. using Vagrant and/or VirtualBox) that requires dedicated RAM and virtual disks.
  • Different projects may have different requirements. Again, the overhead of multiple heavyweight VMs is undesirable.
  • Keeping automated build environments in sync for multiple projects and versions with different requirements was error-prone.

In the process of solving the main problems, there were some additional goals:

  • Avoid changing the developer's workflow. stack commands should work as close to normally as possible when Docker is enabled.
  • Shield developers from having to know the details of how containerization is implemented. Developers shouldn't need to learn all about Docker in order to build their code.
  • Be able to easily update all developers to new and consistent versions system tools, libraries, and packages.
  • Give developers a way to test their code in an environment that is very similar to the environment that it will run in production.
  • Require as few changes as possible for our existing automated build processes. We use Jenkins and Bamboo for automated builds. All that should be needed is having Docker available on the build slave.

When Docker is enabled in stack.yaml, every invocation of stack (with the exception of certain sub-commands) transparently re-invokes itself in an ephemeral Docker container which has the project root directory and the stack home (~/.stack) bind-mounted. The container exists only to provide the environment in which the build runs, nothing is actually written to the container's file-system (any writes happen in the bind-mounted directories) and it the container is destroyed immediately after stack exits (using docker run --rm). This means upgrading to a new image is easy, since it's just a matter of creating ephemeral containers from the new image. The directories are bind-mounted to the same file-system location in the container, which makes it possible to switch between using docker and not and still have everything work.

Docker runs processes in containers as root by default, which would result in files all over our project and stack home being owned by root when they should be owned by the host OS user. There is the docker run --user option to specify a different user ID to run the process as, but it works best if that user already exists in the Docker image. In this case, we don't know the user ID of the developer at image creation. We work around that by using docker run --env to pass in the host user's UID and GID, and adding an ENTRYPOINT which, inside the container, creates the user and then uses sudo -u to run the build command as that user.

In addition, stack and the entrypoint:

  • Uses the stack.yaml resolver setting to construct the Docker image tag (which can be overridden).

  • Copies the Stackage LTS snapshot's build plan and the Hackage index from the image into ~/.stack, if they are newer. This way, they do not need to be downloaded which enables Internet-connectionless operation once you have the Docker image.

  • Determines whether the stdin/stdout/stderr file handles are connected to a terminal device and, if so, runs in interactive container (using docker run --interactive --tty). Unfortunately there doesn't seem to be a way to get a Dockerized process to behave just like a normal process when it comes to stdin/stdout/stderr on the host, but this is close enough that it behaves as expected most of the time.

  • Volume-mounts special project-and-image-specific ~/.cabal and ~/.ghc directories into the image, which means that if you use cabal install directly it will end up with an automatic "sandbox" (before stack added its own, this was the sandboxing approach of our internal build tool, but it is no longer necessary since stack doesn't touch ~/.cabal or ~/.ghc anymore).

  • Checks that the version of Docker installed on the host is recent enough.

  • Provides options to adjust Docker behaviour for common development use cases, plus the ability to pass arbitrary arguments to docker run for the less common cases.


For each GHC version + Stackage LTS snapshot combination, we tag several images (which layer on top of each other):

  • run: Starts with phusion/baseimage, which itself is built on top of Ubuntu 14.04, and adds basic runtime libraries (e.g. libgmp, zlib) and tools (e.g. curl). The idea is that any binary built using one of the higher-level images would run in the base image without any missing shared libs or tools. It does not contain anything to support building Haskell code. Includes the ENTRYPOINT and other support for stack described in the previous section.
  • build: Adds GHC and a complete set of Haskell build tools (cabal-install, alex, happy, cpphs, shake and others, all built from the Stackage LTS snapshot). It does not include Stackage packages or any packages that are not included with GHC itself.
  • full: Adds a complete build of the Stackage LTS snapshot! Includes Haddocks for all packages and a Hoogle database. Adds some extra tools that are handy while developing.

Most of a developer's work is done using a build or full image, and they can test using a run image. The actual production environment for a server can be built on run.

In addition, there are variants of these images that include GHCJS (ghcjs-build and ghcjs-full), plus additional private variants for internal and clients' use that include proprietary extensions.

We create and push these images using a Shake script on the host, and Propellor in the container to control what is in the image. This provides far more flexibility than basic Dockerfiles, and is why we can easily mix-and-match and patch images. Our image build process also allows us to provide custom images for clients. These might include additional tools or proprietary libraries specific to a customer's requirements. We intend to open the image build tool, but it currently contains proprietary information and needs to be refactored before we can extract that and open the rest.


Nothing is perfect, and we have run into some challenges with Docker:

  • It is Linux-only. While Docker does have some support for other host operating systems using boot2docker this has not been reliable enough in practice. In particular, since it uses VirtualBox under the surface, it relies on VirtualBox's extremely slow "shared folders" for bind-mounting directories from the host into the container, which makes it nearly unusable for Haskell builds.

  • The V1 private Docker registry is not very reliable, so we use a variant of this approach to run a static registry hosted directly from S3. We're pleased with this static S3 registry since it means we don't need to set up high availability for our various registries, so we haven't tried the new V2 registry yet.

  • Some corporate customers have extremely restrictive firewalls, which pose difficulties for downloading Docker images from the registry. The static registry helps with this as well.

  • Docker images, especially when they include a complete set of pre-built packages from Stackage, use a lot of disk space. To help with this, stack keeps track of which images it uses and makes it easy to clean up old images.

  • Since the images are large, we have hit limitations in the default device-mapper storage driver configuration which require some tuning. In particular, we've hit default maximum container file system size with the device-mapper driver and and must use the --storage-opt dm.basesize=20G option to increase it. When using btrfs, it is not uncommon to get No space left on device errors even though there is plenty of disk space. This is a well known issue with btrfs due to it running our of space for metadata, which requires a re-balance. We have found the aufs and overlay drivers to work out-of-the-box.

Alternative approaches

There are many other ways to use Docker, but we didn't find that the "obvious" ones met our goals.

The Official Haskell image (which didn't exist when we started using Docker) approach of iteratively developing using docker build and Dockerfile has some disadvantages:

  • It's very different from the way developers are accustomed to working and requires them to understand Docker.
  • While it uses Docker's intermediate step caching to avoid rebuilding dependencies, it has to rebuild the entire project every time. For anything more than a toy project this would make for slow edit-compile-test cycle.
  • It also has to upload the "context" (the project directory) to the Docker daemon for every build. With a large project, this will be time consuming.
  • Since each successful build is saved to an image, we end up with many images that need to be cleaned up.

The Vagrant-style approach of having a persistent container with the project directory bind-mounted into it, while much better, has other disadvantages:

  • Developers need to be congnizant of managing multiple running containers, one for each project.
  • Upgrading to a new image can be more difficult, because this approach encourages making custom changes in the persistent container which then have to be re-done when upgrading.
  • Is more oriented toward heavyweight virtual machines, which have high startup costs.

There are plenty of directions to take Docker support in stack as the container ecosystem evolves. There is work-in-progress to have stack create new Docker images containing executables automatically, and this works even if you perform the builds without Docker. Moving toward more general support is another direction we are considering. A better solution to using containers on non-Linux operating system is desirable. As stack's support for editor integration via ide-backend improves, this will apply equally well to Docker use.

Categories: Offsite Blogs

Rigorous reasoning about space complexity in Haskell?

Haskell on Reddit - Wed, 08/05/2015 - 9:06am

I've been thinking about the folklore belief that you can't sum up a list of integers in O(1) additional space without using strictness, because both foldl and foldr end up using O(n) space (reference). Then suddenly I realized that I don't know if it's actually true. Is there a proof of that claim, using some mathematical model of space complexity in lazy languages? And does that model actually hold true for Haskell, given the existence of optimizations like fusion?

EDIT: the answer is that there's no proof, because the claim is false! It's possible to use pattern matching to have the same effect as strictness, as shown by /u/cgibbard and /u/kamatsu. Thanks!

submitted by want_to_want
[link] [21 comments]
Categories: Incoming News

New theme broken in Google Chrome when the window is narrow (half screen)

Haskell on Reddit - Wed, 08/05/2015 - 8:03am

Not sure to whose attention should I bring this but when I resize the window to half of the screen (Retina Macbook Pro 13"), the comment section becomes broken.

There is a huge amount of empty space (more than a full page; I was surprised to see no comments when the main page there are some) and the comments only appear when sidebar on the right-hand side ends.

If you narrow the window a bit more there are few more UI elements that end up in the wrong place. For instance, the search bar overlaps with the content of the page (on top of the content) while the buttons below the search bar disappear behind the content.

submitted by lostman_
[link] [5 comments]
Categories: Incoming News

[noob] notReverse

Haskell on Reddit - Wed, 08/05/2015 - 6:37am

I'm trying to do the following exercise from NICTA/course:

-- | Do anything other than reverse a list. -- Is it even possible? -- -- >>> notReverse Nil -- [] -- -- prop> let types = x :: List Int in notReverse x ++ notReverse y == notReverse (y ++ x) -- -- prop> let types = x :: Int in notReverse (x :. Nil) == x :. Nil notReverse :: List a -> List a notReverse = error "todo: Is it even possible?"

I'd say it's impossible. I may pass the tests because they're not exhaustive (not all lists are tested), but that would be cheating.

Here's my little proof

  • notReverse Nil = Nil = reverse Nil
  • notReverse (x :. Nil) = x :. Nil = reverse (x :. Nil)

Now let's assume notReverse xs = reverse xs for all lists xs of length n. Then, for all y :. ys of length n+1:

  • notReverse (y :. ys) =
  • notReverse ((y :. Nil) ++ ys) =
  • notReverse ys ++ notReverse (y :. Nil) =H=
  • reverse ys ++ reverse (y :. Nil) =
  • reverse ((y :. Nil) ++ ys) =
  • reverse (y :. ys)

Do you agree?

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

Opaleye or relational-record?

Haskell on Reddit - Wed, 08/05/2015 - 2:23am

I am starting a new project using PostgreSQL as a backend, and the choice of database abstraction seems to be between Opaleye and relational-record.

Although both are relatively young, are there any users in production of either of these prepared to share their experiences?

submitted by alan_zimm
[link] [61 comments]
Categories: Incoming News

The Haskell User Experience

Haskell on Reddit - Tue, 08/04/2015 - 8:29pm
Categories: Incoming News

Proposal: Allow arr ∧ (first ∨ (***)) as minimal definition of Arrow instance

libraries list - Mon, 08/03/2015 - 7:47am
Add default definitions of first, second in terms of (***) to let one define an Arrow instance in terms of (***) rather than first, which is sometimes more elegant or convenient. To my knowledge this can not break any code. GHC ticket: 10216
Categories: Offsite Discussion

simultaneous ghc versions

glasgow-user - Fri, 07/31/2015 - 7:10pm
The recent release of ghc 7.10.2 reminded me of something I meant to ask about a long time ago. Most of the binaries ghc installs are versioned (x linked to x-7.10.2), with some exceptions (hpc and hsc2hs). Shouldn't they all be versioned? Also, 'haddock' is inconsistent with all the rest, in that it's haddock linked to haddock-ghc-7.10.2. I've long used a few shell scripts (recently upgraded to python) to manage ghc installs. A 'set' which creates symlinks to make a particular version current, and an 'rm' to remove all traces of a version. But due to the inconsistency, I have to remember to run "fix" first, which moves the unversioned binaries to versioned names. As an aside, I have three scripts I use all the time: set version, remove version, and remove library. Come to think of it, shouldn't ghc include this, instead of everyone creating their own shell scripts by hand?
Categories: Offsite Discussion

broken source link

glasgow-user - Fri, 07/24/2015 - 8:59am
Hi, when trying to look up the original definition for Data.List.transpose in I found that the source link does not work. Could this be fixed? Or should I look elsewhere for the sources? Cheers Christian P.S. my looking up transpose was inspired by
Categories: Offsite Discussion

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!


Categories: Incoming News