# News aggregator

### language-puppet: 7 Startups - part 3 - An interpreter for the rules

### Convincing GHC that some constraint always holds on closed type families? [StackOverflow]

### Mikael Vejdemo Johansson (Syzygy-): Classifying spaces and Haskell

I’ve been talking with some topologists lately, and seen interesting constructions. I think these may potentially have some use in understanding Haskell or monads.

**Simplicial objects**

A simplicial object in a category is a collection of objects $C_n$ together with n maps $d_j:C_n\to C_{n-1}$ and n maps $s_j:C_n\to C_{n+1}$ subject to a particular collection of axioms.

The axioms are modeled on the prototypical simplicial structure: if $C_n$ is taken to be a (weakly) increasing list of integers, $d_j$ skips the $j$th entry, and $s_j$ repeats the $j$th entry. For the exact relations, I refer you to Wikipedia.

**Classifying spaces**

Take a category C. We can build a simplicial object $C_*$ from C by the following construction:

$C_n$ is all sequences $c_0\xrightarrow{f_0}c_1\xrightarrow{f_1}\dots\xrightarrow{f_{n-1}}c_n$ of composable morphisms in $C$.

$d_j$ composes the $j$th and $j+1$st morphisms. $d_0$ drops the first morphism and $d_n$ drops the last morphism.

$s_j$ inserts the identity map at the $j$th spot.

We can build a topological space from a simplicial object: dimension by dimension, we glue the product $\Delta^{n-1}\times C_n$ of an $n-1$-dimensional simplex and the object $C_n$ to the lower dimensional construction — with the face maps dictating the gluing step.

**Classifying space of Hask**

Consider the category of Haskell types and functions. The classifying space here will have an $n$-dimensional simplex for any sequence of $n+1$ composable functions; glued to the lower-dimensional simplices by composing adjacent functions.

I honestly am not entirely sure what structure, if any, can be found here: this might model $\beta$-reductions; or it might model something utterly trivial — I wonder what, if anything, can be found here, but I currently have no answers.

**Classifying space of a Monad**

We can do the same thing in the category of endofunctors. Recall that a Monad is an endofunctor $T$ with natural transformations $b:T^2\to T$ and $u:1\to T$. Just like any monoid, there is a category structure that fits in this framework. The simplicial object here is $T_*$ with $T_n=T^(n+1)$. The face maps $d_j$ compose two adjacent applications of $T$ using $b$. Degeneracy maps $s_j$ introduce a new $T$ by applying $u$.

For an example, let’s consider the Writer monad, for a monoid w:

newtype Writer w a = Writer { runWriter :: (a, w) }

return a = (a, mone)

bind ((a, w0), w1) = (a, w0 `mappend` w1)

The endofunctor here is Writer w :: * -> *. Iterating this endofunctor gets us (Writer w)^n a = (((...(a,w),w),w),w)...,w). A typical value would be something like

(((...(a,w0),w1),w2),...,wn) :: (Writer w)^n a

We get a simplicial structure here by letting the $j$th face map apply mappend to wj and w(j+1). The $j$th degeneracy map creates an instance of mone at the $j$th spot.

Let’s get more concrete. Consider Writer Any Bool. Recall that w0 `mappend` w1 = w0 `or` w1. For any value of of type x::a, there are $2^n$ values in (Writer w)^n a: one for each possible sequence of input to the Writer monad. Each of these produces an $n-1$-dimensional simplex, that glues to the lower dimensional simplices by fusing neighboring points.

In (Writer Any Bool)^0 there are two vertices: (x,False) and (x,True).

In (Writer Any Bool)^1 there are four edges: (x,True, True), (x,True, False), (x,False, True) and (x,False, False).

These connect to the vertices like this:

In (Writer Any Bool)^2 there are eight triangles. They glue as follows — each triangle gets its three edges in order:

FFF to FF, FF, FF

FFT to FT, FT, FT

FTF to TF, TF, FT

FTT to TT, TT, FT

TFF to FF, TF, TF

TFT to FT, TT, TT

TTF to TF, TF, TT

TTT to TT, TT, TT

It continues like this as we add higher and higher dimensional faces. Any history of $n$ writes to the monad produces an $n-1$-dimensional object, that connects to lower dimensions by looking at how the history could have been contracted by the monoid action at various points.

For the monad Writer All Bool, the same vertices, edges, triangles, et.c. show up, but they connect differently:

FF to F, F

FT to T, F

TF to F, F

TT to T, T

FFF to FF, FF, FF

FFT to FT, FT, FF

FTF to TF, FF, FF

FTT to TT, FT, FT

TFF to FF, FF, TF

TFT to FT, FT, TF

TTF to TF, TF, TF

TTT to TT, TT, TT

**What can we use this for?**

And here, at last, is my reason for writing all this. This construction gets us a topological space, where cells in the space (possibly even points in the space) correspond to possible values of the iterated monad datatype, and where connectivity in the space is driven by the monad. This gives us a geometric, a topological, handle on the programming language structure.

Is this good for anything?

Are there any sort of questions we might be able to approach with this sort of perspective?

I’ll be thinking about it, but if anyone out there has any sort of idea I’d love to hear from you.

### Tidal is great fun - experience report

### case, GADTs, Arrows

### [GCM 2014] Last CFP : Graph Computation Models

### I have a day to learn haskell.

I did a bit of it a few months ago for a college course but I have basically forgotten everything.

Does anybody have any links to some tutorials that will get me up to speed in the next 24 hours?

submitted by mormon-[link] [10 comments]

### Get "cabal repl" to dump ghc options?

### Any library for writing and composing tree transducers, with examples?

The only related library I found was CompData, but the focus is not particularly on the tree transducers and it is lacking any examples.

submitted by SrPeixinho[link] [11 comments]

### vector and GeneralizedNewtypeDeriving

### Once more into the teach, dear friends

### Bryan O'Sullivan: Once more into the teach, dear friends

Since the beginning of April, David Mazières and I have been back in the saddle teaching CS240H at Stanford again.

If you’re tuning in recently, David and I both love systems programming, and we particularly get a kick out of doing it in Haskell. Let me state this more plainly: Haskell is an *excellent* systems programming language.

Our aim with this class is to teach both enough advanced Haskell that students really get a feel for how different it is from other programming languages, and to apply this leverage to the kinds of problems that people typically think of as “systemsy”: How do I write solid concurrent software? How do I design it cleanly? What do I do to make it fast? How do I talk to other stuff, like databases and web servers?

As before, we’re making our lecture notes freely available. In my case, the notes are complete rewrites compared to the 2011 notes.

I had a few reasons for rewriting everything. I have changed the way I teach: every class has at least some amount of interactivity, including in-class assignments to give students a chance to absorb what I’m throwing at them. Compared to the first time around, I’ve dialed back the sheer volume of information in each lecture, to make the pace less overwhelming. Everything is simply fresher in my mind if I write the material right before I deliver it.

And finally, sometimes I can throw away plans at the last minute. On the syllabus for today, I was supposed to rehash an old talk about folds and parallel programming, but I found myself unable to get motivated by either subject at 8pm last night, once I’d gotten the kids to bed and settled down to start on the lecture notes. So I hemmed and hawed for a few minutes, decided that talking about lenses was *way* more important, and went with that.

Some of my favourite parts of the teaching experience are the most humbling. I hold office hours every week; this always feels like a place where I have to bring my “A” game, because there’s no longer a script. Some student will wander in with a problem where I have no idea what the answer is, but I vaguely remember reading a paper four years ago that covered it, so when I’m lucky I get to play glorified librarian and point people at really fun research.

I do get asked why we don’t do this as a MOOC.

It is frankly a pleasure to actually engage with a room full of bright, motivated people, and to try to find ways to help them and encourage them. I don’t know quite how I’d replicate that visceral feedback with an anonymous audience, but it qualitatively matters to me.

And to be honest, I’ve been skeptical of the MOOC phenomenon, because while the hype around them was huge, it’s always been clear that almost nobody knew what they were doing, or what it would even mean for that model to be successful. If the MOOC world converges on a few models that make some sense and don’t take a vast effort to do well, I’m sure we’ll revisit the possibility.

Until then, enjoy the slides, and happy hacking!