# News aggregator

### In " returnIO x = IO $ \ s -> (# s,x #)" what are the # symbols?

### [LPNMR 2015] REGISTRATION OPEN - Call for Participation (student support grants available)

### Brent Yorgey: The Species of Bracelets

*Summary*: The species package now has support for *bracelets*, *i.e.* equivalence classes of lists up to rotation and reversal. I show some examples of their use and then explain the (very interesting!) mathematics behind their implementation.

I recently released a new version of my species package which adds support for the species of *bracelets*. A bracelet is a (nonempty) sequence of items which is considered equivalent up to rotation and reversal. For example, the two structures illustrated below are considered equivalent as bracelets, since you can transform one into the other by a rotation and a flip:

In other words, a bracelet has the same symmetry as a regular polygon—that is, its symmetry group is the dihedral group . (Actually, this is only true for —I’ll say more about this later.)

Bracelets came up for me recently in relation to a fun side project (more on that soon), and I am told they also show up in applications in biology and chemistry (for example, bracelet symmetry shows up in molecules with cycles, which are common in organic chemistry). There was no way to derive the species of bracelets from what was already in the library, so I added them as a new primitive.

Let’s see some examples (later I discuss how they work). First, we set some options and imports.

ghci> :set -XNoImplicitPrelude ghci> :m +NumericPrelude ghci> :m +Math.Combinatorics.SpeciesUnlabelled bracelets, by themselves, are completely uninteresting: there is only a single unlabelled bracelet shape of any positive size. (Unlabelled species *built using* bracelets can be interesting, however; we’ll see an example in just a bit). We can ask the library to tell us how many distinct size- unlabelled bracelets there are for :

Labelled bracelets are a bit more interesting. For there are labelled bracelets of size : there are cycles of size (there are lists, which counts each cycle times, once for each rotation), and counting cycles exactly double counts bracelets, since each bracelet can be flipped in one of two ways. For example, there are labelled bracelets of size .

ghci> take 10 $ labelled bracelets [0,1,1,1,3,12,60,360,2520,20160]In addition to counting these, we can exhaustively generate them (this is a bit annoying with the current API; I hope to improve it):

ghci> enumerate bracelets [0,1] :: [Bracelet Int] [<<0,1>>] ghci> enumerate bracelets [0..2] :: [Bracelet Int] [<<0,1,2>>] ghci> enumerate bracelets [0..3] :: [Bracelet Int] [<<0,1,2,3>>,<<0,1,3,2>>,<<0,2,1,3>>]And here are all of the size- bracelets, where I’ve used a different color to represent each label (see here for the code used to generate them):

As a final example, consider the species , the Cartesian product of bracelets with ordered pairs of sets. That is, given a set of labels, we *simultaneously* give the labels a bracelet structure and *also* partition them into two (distinguishable) sets. Considering *unlabelled* structures of this species—that is, equivalence classes of labelled structures under relabelling—means that we can’t tell the labels apart, other than the fact that we can still tell which are in the first set and which are in the second. So, if we call the first set “purple” and the second “green”, we are counting the number of bracelets made from (otherwise indistinguishable) purple and green beads. Let’s call these *binary bracelets*. Here’s how many there are of sizes through :

Let’s use the OEIS to check that we’re on the right track:

ghci> :m +Math.OEIS ghci> let res = lookupSequence (drop 1 . take 10 $ unlabelled biBracelets) ghci> fmap description res Just "Number of necklaces with n beads of 2 colors, allowing turning over."Unfortunately the species library can’t currently enumerate unlabelled structures of species involving Cartesian product, though I hope to fix that. But for now we can draw these purple-green bracelets with some custom enumeration code. You can see the numbers show up here, and it’s not too hard to convince yourself that each row contains all possible binary bracelets of a given size.

If you’re just interested in *what you can do with* bracelets, you can stop reading now. If you’re interested in the mathematical and algorithmic details of how they are implemented, read on!

The *exponential generating function* (egf) associated to a combinatorial species is defined by

That is, the egf is an (infinite) formal power series where the coefficient of is the number of distinct labelled -structures on labels. We saw above that for there are labelled bracelets of size , and there is one bracelet each of sizes and . The egf for bracelets is thus:

(Challenge: show this is also equivalent to .) This egf is directly encoded in the species library, and this is what is being used to evaluate labelled bracelets in the example above.

Incidentally, the reason only works for is in some sense due to the fact that the dihedral groups and are a bit weird: every dihedral group is a subgroup of the symmetric group except for and . The problem is that for , “flips” actually have no effect, as you can see below:

So, for example, has elements, corresponding to the identity, a 180 degree rotation, a flip, and a rotation + flip; but the symmetric group only has two elements, in this case corresponding to the identity and a 180 degree rotation. The reason doesn’t work, then, is that the division by two is superfluous: for , counting cycles doesn’t actually overcount bracelets, because every cycle is already a flipped version of itself. So it would also be correct (if rather baroque) to say that for there are actually bracelets.

I find this fascinating; it’s almost as if for bigger the dihedral symmetry has “enough room to breathe” whereas for small it doesn’t have enough space and gets crushed and folded in on itself, causing weird things to happen. It makes me wonder whether there are other sorts of symmetry with a transition from irregularity to regularity at even bigger . Probably this is an easy question for a group theorist to answer but I’ve never thought about it before.

Ordinary generating functionsThe *ordinary generating function* (ogf) associated to a species is defined by

where is the equivalence relation on -structures induced by permuting the labels. That is, the coefficient of is the number of *equivalence classes* of -structures on labels up to relabelling. There is only one unlabelled bracelet of any size , that is, any bracelet of size can be transformed into any other just by switching labels around. The unique unlabelled bracelet of a given size can be visualized as a bracelet of uniform beads:

though it’s occasionally important to keep in mind the more formal definition as an equivalence class of labelled bracelets. Since there’s just one unlabelled bracelet of each size, the ogf for bracelets is rather boring:

.

This is encoded in the species library too, and was used to compute unlabelled bracelets above.

egfs, ogfs, and homomorphismsegfs are quite natural (in fact, species can be seen as a categorification of egfs), and the mapping from species to their associated egf is a homomorphism that preserves many operations such as sum, product, Cartesian product, composition, and derivative. ogfs, however, are not as nice. The mapping from species to ogfs preserves sum and product but does not, in general, preserve other operations like Cartesian product, composition or derivative. In some sense ogfs throw away too much information. Here’s a simple example to illustrate this: although the ogfs for bracelets and cycles are the same, namely, (there is only one unlabelled bracelet or cycle of each size), the ogfs for binary bracelets and binary cycles are different:

ghci> -- recall biBracelets = bracelet >< (set * set) ghci> let biCycles = cycles >< (set * set) ghci> take 15 $ unlabelled biBracelets [0,2,3,4,6,8,13,18,30,46,78,126,224,380,687] ghci> take 15 $ unlabelled biCycles [0,2,3,4,6,8,14,20,36,60,108,188,352,632,1182](Puzzle: why are these the same up through ? Find the unique pair of distinct binary -cycles which are equivalent as bracelets.)

Clearly, there is no way to take equal ogfs, apply the same operation to both, and get different results out. So the species library cannot be working directly with ogfs in the example above—something else must be going on. That something else is *cycle index series*, which generalize both egfs and ogfs, and retain enough information that they once again preserve many of the operations we care about.

Let denote the symmetric group of order , that is, the group of permutations on under composition. It is well-known that every permutation can be uniquely decomposed as a product of disjoint cycles. The *cycle type* of is the sequence of natural numbers where is the number of -cycles in the cycle decomposition of . For example, the permutation has cycle type since it has one -cycle, two -cycles, and one -cycle.

For a species and a permutation , let denote the number of -structures that are fixed by the action of , that is,

The *cycle index series* of a combinatorial species is a formal power series in an infinite set of variables defined by

We also sometimes write as an abbreviation for . As a simple example, consider the species of lists, *i.e.* linear orderings. For each , the identity permutation (with cycle type ) fixes all lists of length , whereas all other permutations do not fix any lists. Therefore

(This is not really that great of an example, though—since lists are regular species, that is, they have no nontrivial symmetry, their cycle index series, egf, and ogf are all essentially the same.)

Cycle index series are linked to both egfs and ogfs by the identities

To show the first, note that setting all to other than means that the only terms that survive are terms with only raised to some power. These correspond to permutations with only -cycles, that is, identity permutations. Identity permutations fix *all* -structures of a given size, so we have

To prove the link to ogfs, note first that for any permutation with cycle type we have . Thus:

where the final step is an application of Burnside’s Lemma.

The important point is that the mapping from species to cycle index series is again a homomorphism for many of the operations we care about, including Cartesian product and composition. So in order to compute an ogf for some species defined in terms of operations that are not compatible with ogfs, one can start out computing with cycle index series and then project down to an ogf at the end.

Cycle index series for braceletsLet’s now see how to work out the cycle index series for the species of bracelets. For , the single bracelet is fixed by the only element of , giving a term of . For , the single bracelet is fixed by both elements of , one of which has cycle type and the other . Bracelets of size , as discussed previously, have the dihedral group as their symmetry group. That is, every one of the size- bracelets is fixed by the action of each element of , and no bracelets are fixed by the action of any other permutation. Putting this all together, we obtain

Our remaining task is thus to compute , that is, to compute the cycle types of elements of for . I don’t know whether there’s a nice closed form for , but for our purposes it doesn’t matter: it suffices to come up with a finite algorithm to generate all its terms with their coefficients. A closed form might be important if we want to compute with symbolically, but if we just want to generate coefficients, an algorithm is good enough.

In general, has elements corresponding to rotations (including the identity element, which we think of as a rotation by degrees) and elements corresponding to reflections across some axis. Below I’ve drawn illustrations showing the symmetries of bracelets of size and ; each symmetry corresponds to an element of .

The lines indicate reflections. You can see that in general there are lines of reflection. The curved arrows indicate clockwise rotations; taking any number of consecutive arrows from to gives a distinct rotational symmetry. Let’s label the rotations (for ), where indicates a rotation by of a turn (so is the identity element). We won’t bother labelling the reflections since it’s not clear how we would choose canonical names for them, and in any case (as we’ll see) we don’t have as much of a need to give them names as we do for the rotations. The only thing we will note is that for even there are two distinct types of reflections, as illustrated by the dark and light blue lines on the right: the dark blue lines pass through two vertices, and the light blue ones pass through two edges. In the odd case, on the other hand, every line of reflection passes through one vertex and one edge. If you haven’t studied dihedral groups before, you might want to take a minute to convince yourself that this covers all the possible symmetries. It’s clear that a rotation followed by a rotation is again a rotation; what may be less intuitively clear is that a reflection followed by a reflection is a rotation, and that a rotation followed by a reflection is a reflection.

So the name of the game is to consider each group element as a permutation of the labels, and compute the cycle type of the permutation. Let’s tackle the reflections first; we have to separately consider the cases when is odd and even. We saw above that when is odd, each line of reflection passes through exactly one vertex. As a permutation, that means the reflection will fix the label at the vertex it passes through, and swap the labels on other vertices in pairs, as shown in the leftmost diagram below:

So the permutation has cycle type . There is one -cycle, and the remaining elements are paired off in -cycles. There are of these reflections in total, yielding a term of (where ).

When is even, half of the reflections (the light blue ones) have no fixed points, as in the middle diagram above; they put everything in -cycles. The other half of the even reflections fix two vertices, with the rest in -cycles, as in the rightmost diagram above. In all, this yields terms .

Now let’s tackle the rotations. One could be forgiven for initially assuming that each rotation will just yield one big -cycle… a rotation is just cycling the vertices, right? But it is a bit more subtle than that. Let’s look at some examples. In each example below, the green curved arrow indicates a rotation applied to the bracelet. As you can check, the other arrows show the resulting permutation on the labels, that is, each arrow points from one node to the node where it ends up under the action of the rotation.

Do you see the pattern? In the case when (the first example above), or more generally when and are relatively prime (the second example above, with and ), indeed generates a single -cycle. But when and are not relatively prime, it generates multiple cycles. By symmetry the cycles must all be the same size; in general, the rotation generates cycles of size (where denotes the greatest common divisor of and ). So, for example, cycles are generated when and or (the next two examples above). The last example shows and ; we can see that three -cycles are generated. Note this even works when : we have , so we get cycles of size , *i.e.* the identity permutation.

So contributes a term . However, we can say something a bit more concise than this. Note, for example, when , as the contribution of all the we get

but we can collect like terms to get

For a given divisor , the coefficient of is the number of nonnegative integers less than whose with is equal to . For example, the coefficient of is , since there are two values of for which and hence generate a six-cycle, namely, and . So as the contribution of the we could write something like

but there is a better way. Note that

since multiplying and dividing by establishes a bijection between the two sets. For example, we saw that and are the two numbers whose with is ; this corresponds to the fact that and are relatively prime to .

But counting relatively prime numbers is precisely what Euler’s totient function (usually written ) does. So we can rewrite the coefficient of as

.

Finally, since we are adding up these terms for all divisors , we can swap and (divisors of always come in pairs whose product is ), and rewrite this as

.

To sum up, then, we have for each :

- When is odd, .
- When is even, .
- For each , we have .

The only overlap is between (2) and (3): when both generate terms. Using Iverson brackets (the notation is equal to if the predicate is true, and if it is false), we can thus write the sum of the above for a particular as

.

Substituting this for yields a full definition of . You can see the result encoded in the species library here. Here’s the beginning of the full expanded series:

ghci> :m +Math.Combinatorics.Species.Types ghci> take 107 $ show (bracelets :: CycleIndex) "CI x1 + 1 % 2 x2 + 1 % 2 x1^2 + 1 % 3 x3 + 1 % 2 x1 x2 + 1 % 6 x1^3 + 1 % 4 x4 + 3 % 8 x2^2 + 1 % 4 x1^2 x2"This, then, is how unlabelled biBracelets (for example) is calculated, where biBracelets = bracelet >< (set * set). The cycle index series for bracelet and set are combined according to the operations on cycle index series corresponding to * and ><, and then the resulting cycle index series is mapped down to an ogf by substituting for each .

Bracelet generationThe final thing to mention is how bracelet *generation* works. Of course we can’t really generate actual bracelets, but only lists. Since bracelets can be thought of as equivalence classes of lists (under rotation and reversal), the idea is to pick a canonical representative element of each equivalence class, and generate those. A natural candidate is the *lexicographically smallest* among all rotations and reversals (assuming the labels have an ordering; if they don’t we can pick an ordering arbitrarily). One easy solution would be to generate all possible lists and throw out the redundant ones, but that would be rather inefficient. It is surprisingly tricky to do this efficiently. Fortunately, there is a series of papers by Joe Sawada (Generating bracelets with fixed content; A fast algorithm to generate necklaces with fixed content; Generating bracelets in constant amortized time) describing (and proving correct) some efficient algorithms for generating things like cycles and bracelets. In fact, they are as efficient as possible, theoretically speaking: they do only work per cycle or bracelet generated. One problem is that the algorithms are very imperative, so they cannot be directly transcribed into Haskell. But I played around with benchmarking various formulations in Haskell and got it as fast as I could. (Interestingly, using STUArray was a lot slower in practice than a simple functional implementation, even though the imperative solution is asymptotically faster in theory—my functional implementation is at least per bracelet, and quite possibly , though since is typically quite small it doesn’t really matter very much. Of course it’s also quite possible that there are tricks to make the array version go faster that I don’t know about.) The result is released in the multiset-comb package; you can see the bracelet generation code here.

### Best way to return Bool based on a successfulpattern match?

### Help with catching exceptions

I have been playing around with Haskell for some time now but have not made a lot of progress beyond writing simple applications that follow the same pattern. For example, with Yesod, I just focused on my Get and Post handlers and simple DB logic using Persistent. Every time I want to do something complex and interact with a third party library I end up getting lost in all the type errors that stem from deep inside the library or while trying to use them.

One example is my recent foray in handling exceptions. I posted my question on Stack Overflow and did not get any responses yet so I thought I will ask here instead. I probably should have not even bothered with SO as I am also interested in learning about how people debug Haskell programs and not just a simple answer so this would have the right place to begin with.

I am using Persistent to run a serious DB statements inside MaybeT so if one of them fails, it will short-circuit and get a Nothing at the end. /u/snoyberg mentioned I need to throw an exception inside MaybeT if I want to rollback the transaction when a failure occurs, which I managed to do but cannot figure out how to handle this transaction cleanly. So I tried this using try (from Control.Exception.Lifted)

import Control.Exception.Lifted (throwIO, Exception, try) import Control.Monad.Reader as Imports (ReaderT, runReaderT, asks, lift, liftIO) eauth <- liftIO ( try( runDb $ do ma <- runMaybeT $ do valid <- ... -- DB statement 1 uid <- ... -- DB statement 2 auth <- createAuth uid return auth case ma of Just a -> return a Nothing -> liftIO $ throwIO MyException ) :: IO (Either MyException Auth) ) case eauth of Right auth -> return auth Left _ -> lift $ left err400 { errBody = "Could not create user"}My runDb looks like:

runDb query = do pool <- asks getPool liftIO $ runSqlPool query poolI get this error:

No instance for (Control.Monad.Reader.Class.MonadReader Config IO) arising from a use of ‘runDb’ In the expression: runDb In the first argument of ‘try’, namely ‘(runDb $ do { ma <- runMaybeT ...I am running inside servant handler and my return type is AppM Auth where

type AppM = ReaderT Config (EitherT ServantErr IO)This from /u/ephiron's sample code for using servant with persistent.

I felt adding exception handling should be an easy change but the errors messages indecipherable to me. Any help / pointers are very much appreciated.

Initially I thought this was a servant issue and thanks to /u/jkarni for helping me troubleshoot patiently.

submitted by ecognium[link] [12 comments]

### reflex-dom-contrib: A playground for experimenting with infrastructure and common code for reflex applications

### /r/haskell gets a makeover

Hey all, /u/evanrelf did a wonderful job overhauling our CSS, he modified the "Naut" theme, and you can find the source here.

Everyone give him a big round of applause -- it looks great!

https://github.com/evanrelf/r-haskell-theme

submitted by jfredett[link] [58 comments]

### From Lenses to Yoneda Embedding

### To all users of FGL

### We want to start a new small social network written in Haskell, who wants to join?

So, the concept is all about "countdowns", and it is (more or less) based on twitter: A countdown is just a small piece of information stating "at this time and this place, something will happen". As an example, the ESA could have a countdowns-account. If the ESA now plans to launch a rocket, it publishes a countdown, for example, for the 14th of July in Guiana. Other people could browse the countdowns network and then see "Oh, I like what the ESA does, I will follow it!" and then they will see rocket launches of the ESA on their dashboard. Or maybe they just say "Oh, I like the rocket launch of this Ariane, and I want to watch it!" and then they mark this countdown as a favourite. In the moment, maxptr and I would like to start this project - maxptr because he wants to learn real world haskell and me because I like the idea. As the title says, does anybody want to join us?

TL;DR: We want to build a network like twitter but use countdowns instead of short messages, help would be appreciated.

EDIT: Yes, I have a framework in mind: Yesod. And because functional programming is awesome, PureScript would be nice to program with (from the client side). Furthermore, of course this project will be open source :)

EDIT2: I created a repo on GitHub. However wants to join the team, send me a PM and I'll add you to the contributor list - I just have to know your GitHub names!

submitted by sammecs[link] [15 comments]

### Dominic Steinitz: Conditional Expectation under Change of Measure

Let and be measures on with , a sub -algebra and an integrable random variable () then

Proof

Thus

Hence

We note that

is -measurable (it is the result of a projection) and that

Hence

as required.

### Advice on migrating live applications to Haskell

I have built a chrome extension that uses a back-end powered by a Python server with Flask. It receives a fairly modest but steady amount of traffic daily, and this traffic is growing (slowly). I'm very comfortable in Python so there's nothing inherently wrong with the current set up, but I love Haskell and have an interest in switching the server over. I want to do this because:

- Haskell is awesome and I want to get better at it. At my current skill level, I'm far less productive in Haskell than in other languages - most of my time is spent trying to understand new libraries, and wrapping my head around how to use them. I really want to see if Haskell can be as productive for me as the veterans in this community claim it is for them.
- Type safety.

I have these concerns that have been holding me back from making the switch:

- This is currently deployed on Heroku. I've never successfully deployed a Haskell app to production, and haven't even yet attempted getting it to work well with Heroku. Halcyon looks really cool, but historically things in the building and deploying area end up being much harder and more time consuming for me in practice than I think it should be. Python seems to be much easier to use in this area (at least for me, please share your opinion if you disagree).
- I currently use a Python library to hash and check passwords (passlib). Switching to a new library without making everyone reset their passwords seems like a potential pain point.
- I'm worried the time required to completely rewrite the server will outweigh the benefit of the switch. The current implementation is ~1500 lines of Python.
- Swapping out a live server for a new one just seems plain tricky. That one is not a Haskell related fear.

Are there pros or cons of such a change I'm not considering? Does anyone here have experience rewriting a production application in Haskell and have some stories to share on what you learned from it? Would you do it again? Any thoughts on this situation would be appreciated!

submitted by aviaviaviavi[link] [10 comments]

### Please rename 'stack' to 'haystack'

'Stack' is too generic and widely used to mean different things in programming.

Searching for 'haskell stack' (https://duckduckgo.com/?q=haskell+stack) currently has this as the top result - http://www.haskell.org/haskellwiki/Stack_overflow. I'm sure that will change, but it does show how 'stack' conflicts unnecessarily with other usages of the term. Not to mention haskell specific terms like 'monad transformer stack' etc.

Can we please rename it to something more distinct and a little easier to search for online?

I suggest 'haystack', which can be shortened to 'hastack' or 'hstack' (but still pronounced haystack). Almost *anything* less generic than 'stack' would be fine though.

**Edit:** To clarify to people who think that Google gets it right, or that searchability of stack is not a concern - it's not just about being able to search for stack. It's about having a collision that doesn't need to exist. As 'kqr' points out below - One problem lies in searching for "haskell stack <something>" where the "<something> stack" is a relevant thing on its own, such as "transformer stack" or "web dev stack". And once the name is solidified, we will have to pay the cost of not being able to search correctly for things year after year.

**Edit 2:** Haystack is only a suggestion. Hastack is a good amalgam of Haskell and stack. Hstack also works. Other things people suggested (in no particular order) - "sheaf", "costack", "hake", "needle", and perhaps a little less seriously also things like "dude", "bro", "plz". Also suggested - reusing the name "stackage"/"stk" as those tools are effectively defunct now.

**Edit 3.** Chris Done has said this will not happen (https://www.reddit.com/r/haskell/comments/3d3e95/please_rename_stack_to_haystack/ct1itcd). However, this post has reached 100 upvotes, indicating that it has atleast some popular support. Chris / someone else from FPComplete, please let us know if this has no chance ** at all** of happening so we can stop the bikeshedding :)

**Final Edit:** The powers that be have spoken (https://www.reddit.com/r/haskell/comments/3d9z57/about_the_name_stack/) and this is not going to happen. I believe that it was a mistake not picking the name stkg (https://www.reddit.com/r/haskell/comments/3d9z57/about_the_name_stack/ct3d6rv) but it's a closed chapter for now.

[link] [77 comments]

### Leksah 0.15.1.0 (Haskell IDE) faster, better errors, nicer HLint, retina, sorted files & functions and lots of bug fixes!

### Announcing libravatar < at > hackage

### On Windows after I install the new cabal-install then when I do a cabal update it says there is a new ...

### Translating Haskell to C++ templates

### AI4FM 2015: Final call for short contributions

### mp4v2 bindings for Haskell?

Another relative newcomer to haskell, I'm rewriting a media management system for my home video library that I originally wrote in Python as a way to work through concepts in LYAH and RWH. It's taken me a few weeks to get the basic concepts solid, and work through some differences between the code in RWH and what works in the current platform.

At this point, I need some functions that will read tags from .mp4/.m4v videos. I tried TagLib that I found on hackage,but that doesn't seem to work with videos (and only mentions audio in the docs). Does anyone know of any haskell bindings for the mp4v2 library, or of any library that will read mp4 video tags in haskell?

My other choice is to start to rewrite something like Python's mutagen in haskell, but I'm not quite sure I'm ready for that.

submitted by rogue203[link] [5 comments]