# News aggregator

### generating object file for ARM

### ANN: servant-swagger and swagger2

### Douglas M. Auclair (geophf): Graphing with Goats

*comme ça!*Links at the end. Presentation posted on youtube of the meetup.

1

2

3 (I am known for teh kittehs)

4 (graphs-я-borin' is another talk I gave at SanFran GraphConnect 2015)

5. The Beach (not Plastic)

6

7

8. ACID

*means*

*something*very important to DBMSes(eses)(eses)

9. neo4j Graph of Amino Acids (data table, Haskell code)

10. links: linkurio.us, d3js.org, grapheneDB.com(geddit? links to

*link*urio.us? geddit?)

11. "sed-butt, sed-butt, sed-butt" my daughters chant around the house all day

Now: Graph-applications:

12. Social Media

13. The Markets

14. The Markets (again) / Managing Complexity

15. Search / (Fraud) Detectione.g.: Regressive Imagery Dictionary

16. Scoping / (Requirements) Analysis

17. Clustering

18.

*Errybody*say: "YAAAAAAYYYYYY!"

19. Links, en-text-ified:

- What is a Graph? from neo4j.com
- Regressive Imagery Dictionary-as-Graph (yours truly)
- Goats (because reasons)
- grapheneDB.com (DaaS)
- linkurio.us / d3js.org
- @1HaskellADay
- Daily Haskell problem; sometimes Graph (Theory)-related
- Yeah, links to themselves. Yeah.
- Amino Acid CODON table
- data: http://lpaste.net/raw/3763369603112108032
- problem statement: http://lpaste.net/6606149825735950336

20. Buh-bay!

### Combining Pipes with Callbacks

### How to handle recoverable errors in multi-stepcomputation?

### New type of ($) operator in GHC 8.0 is problematic

### Foldable/Traversable and Applicative/Monoid?

### Month in haskell-ide-engine January 2016

### Christopher Allen: Haskell is not trivial, but it's not unfair like Dark Souls either

Alternate title: Another brutal fisking for which I’ll forever be remembered as a monster

Don’t be a dick and don’t harass the original author please. They were just sharing their experience.It took me five years to stop struggling with Haskell, I know a lot of the UX stuff sucks. I think there’s a lot of value in using Haskell for everyday work so it’s disappointing when things fall apart for a learner for unnecessary reasons.

I’ve since talked to the author of the original post and they’re cool with this post. Also they agree with me that wreq should get more airplay. On with the show.

Getting the ball rolling on talking to HTTP APIsI want to collect some statistics from the GitHub API. Watch as I retrace my steps attempting the Tomb of the Dread HTTPS GET Request.

Okay, is there a reason we’re not going to use the Haskell Github client for that? Anyway, we’ll follow along with what the author’s doing for now.

Now I need to query the GitHub API. Not my first time to the rodeo, I generate a personal access token from GitHub and copy it to a local file. What query should I run first? How about the count for all ASM tetris repositories? Poking around the docs comes up with:

GET https://api.github.com/search/repositories?q=tetris+language:assembly&sort=stars&order=desc User-Agent: victim Authorization: token PUT_TOKEN_HERECool so far. Think the author figured out Github’s docs more easily than I did.

Easy life. Now how do you GET a resource in Haskell? Ah, Network.HTTP! I copy the front page sample into src/Lib.hs

Okay first mistake. I know it sucks, but you want to be careful about using Hackage to find libraries for things unless you’re good at sniff-testing APIs. It’s generally better to ask what a good library to use is. The library named “HTTP” is a bit creaky and there are nicer, more up to date ways of doing HTTP in Haskell. Entirely not the author’s fault, but it’s pretty hard to get Hackage to do anything useful anyway. I know this is sucky implicit crap nobody should have to care about, but Haskell just doesn’t have the culture of design-focused self-promotion that other communities have. Not a value judgment, in the end it’s probably better for end-users if they can use design as a signal of how up to date or nice a library is, but that’s just how it is right now. It would probably help if there were more Haskellers that didn’t sneer at web devs.

Anyhoodle,

-- the article's version module Lib ( someFunc ) where x = simpleHTTP (getRequest "https://www.github.com/") >>= fmap (take 100) . getResponseBody someFunc :: IO () someFunc = print xWell. Yes that sucks. It’s also a weird way to write it. It’s like the code people write the first time they figure out how do syntax desugars into >>=, then they just start using >>= and point-free all over the place for the fuck of it. We’ll re-do it in wreq:

-- first.hs -- this is my version module FirstExample ( someFunc ) where -- Don't give me any shit about lens. -- You don't need to understand lens -- to know the ^. is for accessing a -- record field. The wreq tutorial -- lays out the common use-cases. import Control.Lens import qualified Data.ByteString.Lazy as BL import Network.Wreq -- Brand X -- simpleHTTP (getRequest "https://www.github.com/") >>= fmap (take 100) . getResponseBody -- someFunc :: IO () -- someFunc = -- print x -- our version someFunc :: IO () someFunc = do response <- get "https://www.github.com/" print $ BL.take 100 (response ^. responseBody)To load this beast up:

-- yes this'll take a moment, but then you won't -- have to do it again because it's Stack. $ stack build lens wreq $ stack ghci Prelude> :l first.hs [1 of 1] Compiling FirstExample ( first.hs, interpreted ) Ok, modules loaded: FirstExample. Prelude> someFunc "<!DOCTYPE html>\n<html lang=\"en\" class=\"\">\n <head prefix=\"og: http://ogp.me/ns# fb: http://ogp.me/ns"Right-o, moving along.

Doesn’t compile. Durp, hackage is a package library, I need to add this to my cabal.

If you want to and you wanted a package for this, sure. I’ll typically use a stack template for new projects, but for initial exploration I’ll build the libraries as above I want and use them in stack ghci.

…author struggles with HTTP only supporting HTTP…

wreq and http-client-tls support HTTPS out of the box. YMMV. There’s a reason I don’t really recommend older Haskell libraries even if they’re maintained. The foundation of many libraries is http-client and it’s a pretty popular library to use. It’s used in http-conduit and pipes-http as well. The latter of which is a single 130 line module that has required almost zero maintenance in the past two years to add pipes streaming support to http-client. Things that use http-client are generally nice but you’ll often want to use something higher level than http-client itself, such as wreq.

Author moves on to use http-conduit, which uses http-client-tls under the hood

query :: IO String query = do initReq <- parseUrl "https://api.github.com/search/repositories" let r = initReq { method = "GET" , requestHeaders = [(hUserAgent, "victim") , (hAuthorization, "token PUT_TOKEN_HERE")]} let request = setQueryString [("q", Just "tetris+language:assembly") ,("order", Just "desc") ,("sort", Just "stars")] r manager <- newManager tlsManagerSettings res <- httpLbs request manager return . show . responseBody $ res someFunc :: IO () someFunc = do query >>= putStrLnThey’re not using the streaming, might as well use wreq. Normally you’d have, such as in a web framework, an HTTP client pool which gets initialized with the web app once and then shared with the handlers. So the initial setup code would happen once. I do think the API staging out the parseUrl part is a bit pointless for the common-case but w/e. For the record, I wouldn’t consider this code to be bad.

As it happens, wreq has an example of how to talk to Github’s API *in the tutorial* here if you ctrl-f “most popular implementations of Tetris” you’ll find it.

As it happens, we can just skip past the explicit params thing and just do this:

Prelude> response <- get "https://api.github.com/search/repositories?q=tetris+language:assembly&sort=stars&order=desc" Prelude> response ^. responseBodyBut uh, we’ll get back to what they’re trying to do.

Time to parse this mega JSON string. Aeson seems to be the biggest contender. To use Aeson and get the total_count value from the return, I needed the following additions:

{-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE DeriveGeneric #-} import GHC.Generics import Data.Aeson data ResultCount = ResultCount { total_count :: Int } deriving (Generic, Show) instance ToJSON ResultCount instance FromJSON ResultCountHuh? No you don’t! Int already has a FromJSON instance.

Just to make the point, I’ll do it in GHCi again with no module.

$ stack build aeson lens-aeson $ stack ghci Prelude> import Network.Wreq Prelude> import Control.Lens Prelude> import Data.Aeson Prelude> import Data.Aeson.Lens Prelude> :set -XOverloadedStrings Prelude> response <- get "https://api.github.com/search/repositories?q=tetris+language:assembly&sort=stars&order=desc" Prelude> response ^? responseBody . key "total_count" Just (Number 354.0) Prelude> response ^? responseBody . key "total_count" . _Number Just 354.0Don’t make it harder than it has to be. *Ask for help!*

I know this site is a bit of a disaster zone, but if you like my writing or think you could learn something useful from me, please take a look at the book I've been writing with my coauthor Julie. There's a free sample available too!

Posted on February 6, 2016

### servant: Announcing servant-swagger and swagger2

Servant is not the first project to provide a unified way of documenting APIs. There is API Blueprint, RAML, Apiary, and finally swagger. While these Web API description languages are not also web frameworks , they are generally very mature, and have some amazing tooling. For example, take a look at what swagger-ui, a client-side HTML, CSS, and JS bundle, does with your swagger API description here.

As you can see, it’s a very convenient and approachable way of exploring your API. In addition to an easily-navigable structure, you can build up requests and send them to your server, and see its responses.

But it doesn’t end there. If you have a swagger specification of your API, you can also take advantage of the large variety of languages for which you can generate a client library automatically. You don’t even need to build the Java code - you can just use the “Generate Client” button in the beautiful swagger editor.

There are a wide array of other tools that support swagger. Obviously, having access to them would be a great boon. The problem so far has been that writing and maintaining a swagger specification, that you can be sure matches your service, is hard work.

</section> <section class="level2" id="swagger2-and-servant-swagger"> swagger2 and servant-swaggerThankfully David Johnson and Nickolay Kudasov have written two Haskell libraries, swagger2 and servant-swagger, that automate nearly all of that process for servant APIs. They use the mechanism that guides most of the servant ecosystem — interpreters for the type-level DSL for APIs that is servant — to generate a swagger spec for that API.

Let’s see how it is used; as an example, we’re going to take the Gists part of the GitHub API v3. For the purpose of this post we will ignore authentication and consider only GET requests which do not require one. Furthermore, we’ll use simplified representation for the responses (i.e. we are also ignoring some fields of the response objects).

First the imports and pragmas (this is a literate haskell file):

{-# LANGUAGE DataKinds #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE TypeOperators #-} module Gists where import Control.Lens import Data.Aeson import Data.Aeson.Types (camelTo2) import qualified Data.Aeson.Types as JSON import qualified Data.ByteString.Lazy.Char8 as BL8 import Data.HashMap.Strict (HashMap) import Data.Proxy import Data.Swagger import Data.Text (Text) import Data.Time (UTCTime) import GHC.Generics (Generic) import Servant import Servant.SwaggerThe API:

type GitHubGistAPI = "users" :> Capture "username" Username :> "gists" :> QueryParam "since" UTCTime :> Get '[JSON] [Gist] :<|> "gists" :> GistsAPI type GistsAPI = "public" :> QueryParam "since" UTCTime :> Get '[JSON] [Gist] :<|> "starred" :> QueryParam "since" UTCTime :> Get '[JSON] [Gist] :<|> Capture "id" GistId :> GistAPI type GistAPI = Get '[JSON] Gist :<|> Capture "sha" Revision :> Get '[JSON] Gist api :: Proxy GitHubGistAPI api = ProxyData types:

newtype Username = Username Text deriving (Generic, ToText, FromJSON) newtype GistId = GistId Text deriving (Generic, ToText, FromJSON) newtype SHA = SHA Text deriving (Generic, ToText) type Revision = SHA data Gist = Gist { gistId :: GistId , gistDescription :: Text , gistOwner :: Owner , gistFiles :: HashMap FilePath GistFile , gistTruncated :: Bool , gistComments :: Integer , gistCreatedAt :: UTCTime , gistUpdatedAt :: UTCTime } deriving (Generic) data OwnerType = User | Organization deriving (Generic) data Owner = Owner { ownerLogin :: Username , ownerType :: OwnerType , ownerSiteAdmin :: Bool } deriving (Generic) data GistFile = GistFile { gistfileSize :: Integer , gistfileLanguage :: Text , gistfileRawUrl :: Text } deriving (Generic)FromJSON instances:

modifier :: String -> String modifier = drop 1 . dropWhile (/= '_') . camelTo2 '_' prefixOptions :: JSON.Options prefixOptions = JSON.defaultOptions { JSON.fieldLabelModifier = modifier } instance FromJSON OwnerType instance FromJSON Owner where parseJSON = genericParseJSON prefixOptions instance FromJSON GistFile where parseJSON = genericParseJSON prefixOptions instance FromJSON Gist where parseJSON = genericParseJSON prefixOptionsSo far this is what you would usually have when working with servant. Now to generate Swagger specification we need to define schemas for our types. This is done with ToParamSchema and ToSchema instances:

prefixSchemaOptions :: SchemaOptions prefixSchemaOptions = defaultSchemaOptions { fieldLabelModifier = modifier } instance ToParamSchema SHA instance ToParamSchema Username instance ToParamSchema GistId instance ToSchema Username instance ToSchema GistId instance ToSchema OwnerType instance ToSchema Owner where declareNamedSchema = genericDeclareNamedSchema prefixSchemaOptions instance ToSchema GistFile where declareNamedSchema = genericDeclareNamedSchema prefixSchemaOptions instance ToSchema Gist where declareNamedSchema = genericDeclareNamedSchema prefixSchemaOptionsThese will give us a generically-derived Swagger schema (which is sort of a deterministic version of JSON Schema).

Part of the swagger2 package, Schema and ParamSchema can be quite useful in their own right if you want to e.g. respond with a schema in case of bad request bodies, or OPTIONS requests.

The next step will traverse the GitHubGistAPI, gathering information about it and swagger2 schemas to generate a Swagger value:

swaggerDoc1 :: Swagger swaggerDoc1 = toSwagger apiNow we can generate the swagger documentation:

genSwaggerDoc1 :: IO () genSwaggerDoc1 = BL8.putStr $ encode swaggerDoc1You can attach more information to your Swagger doc quite easily, using the lenses provided by swagger2:

swaggerDoc2 :: Swagger swaggerDoc2 = swaggerDoc1 & host ?~ "api.github.com" & info.title .~ "GitHub Gists API" & info.version .~ "v3" main :: IO () main = BL8.putStr $ encode swaggerDoc2Which results in this.

There’s a lot more you can do with both servant-swagger and swagger2 — write manual ToSchema instances for more detailed information, conveniently add tags or change responses of parts of your API, use convenient lenses to modify any part of your schema, generate automatic tests, etc.

Check out the servant-swagger and swagger2 docs for more.

These two new packages vastly expand the landscape of tools within easy reach of application developers using servant. Time to explore that landscape!

On a related note, Masahiro Yamauchi has recently added Servant codegen for Swagger. So not only can you generate a swagger description for your servant server, but you can also generate the servant description from a swagger one too!

</section> Posted on February 6, 2016 by David Johnson, Nickolay Kudasov, Julian Arni### Douglas M. Auclair (geophf): January 2016 1HaskellADay Problems and Solutions

- January 29th, 2016: Yesterday we monaded, for today's #haskell problem, we COMonad! ... with STREAMS! Oh, yeah! http://lpaste.net/2853437990695337984 onesies and twosies, duplicate to our solutionseis! http://lpaste.net/2531970919929217024
- January 28th, 2016: Today: Monads. Tomorrow? COMonads! But today's #haskell problem: monads. http://lpaste.net/3895602141393321984 Todayed we Monaded! Oh, yeah! http://lpaste.net/8618821627204861952
- January 27th, 2016: Today's #haskell problem: A Date-client! http://lpaste.net/3557542263343022080 Not what you're thinking, naughty children! *scold-scold*
- January 26th, 2016: For today's #haskell problem we create a DayOfWeek web service! Woot! http://lpaste.net/5212178701889830912
- January 25th, 2016: Per @SirElrik idea, this week we'll do #Haskell #µservices Today's problem is to JSONify a Day -> DayOfWeek function http://lpaste.net/150850 Date, JSONified http://lpaste.net/7633349000409645056
- January 20th, 2016: Yesterday's problem showed us MLK-day was not a trading day, but WHAT WEEK DAY WAS IT? Today's #haskell problem: http://lpaste.net/3912063664412164096 The solutioneth giveth us the dayth of the weeketh! http://lpaste.net/703919211096834048
- January 19th, 2016: Today's #haskell problem asks: Was yesterday a #trading day? http://lpaste.net/1968281888535609344 And a #haskell solution to the trading calendar? Monoids, of course! http://lpaste.net/1299918534133940224
- January 18th, 2016: Today's #haskell problem is a mathematical conundrum concerning poetry ... yes, poetry http://lpaste.net/4733337870415167488 Langston Hughes and Rob't Frost give us the solution: http://lpaste.net/8014739098407272448
- January 15th, 2016: Yesterday was the Repeatinator2000, for today's #haskell problem we have the GAPINATOR3004!! YES! http://lpaste.net/1481736263689043968 Well, we see HALF the stocks are only mentioned once. But minGaps are NOT telling! Hm. http://lpaste.net/5017845158461308928
- January 14th, 2016: In the sea of data we look for some repeaters for today's #haskell problem http://lpaste.net/781423227393015808 AN (H)istogram? A HISTogram? eh, whatevs. #haskell soln shows LOTS of low frequency mentions http://lpaste.net/8518180312847482880
- January 13th, 2016: One chart to rule them all, one chart to find them, one chart to bring them all, and in the darkness bind them http://lpaste.net/161563874967945216 Big Up Chart ... in #haskell, ya! http://lpaste.net/2722111763528024064
- January 12th, 2016: Printing out buy/sell Orders for further analysis http://lpaste.net/2893303782647529472 The charts, ... with the #haskell program that generated them: http://lpaste.net/333157576608841728
- January 11th, 2016: Prolog. Lists. *drops mic http://lpaste.net/8013339712162889728 For the solution we represent PrologList as a difference list http://lpaste.net/3349987882864476160
- January 8th, 2016: '$NFLX and Chili?' is today's #haskell problem http://lpaste.net/3944517274819362816 What is this fascination with eating chili whilst watching movies? Case study: $NFLX a solution with several buy/sell scenarios and some open questions remaining http://lpaste.net/6187369537755676672
- January 5th, 2016: We are Y2K16-compliance officers for today's #haskell problem http://lpaste.net/4805789218464858112
- January 4th, 2016: Happy New Year! Today's #haskell problem looks at the World of WarCr–... Oops, I mean the World of Work-flow! http://lpaste.net/5383485916327182336

### Is there a way to generate instances from the GHCiREPL?

### Temporal Higher Order Contracts

Temporal Higher Order Contracts

Tim Disney, Cormac Flanagan, Jay McCarthy

2011

Behavioral contracts are embraced by software engineers because they document module interfaces, detect interface violations, and help identify faulty modules (packages, classes, functions, etc). This paper extends prior higher-order contract systems to also express and enforce temporal properties, which are common in software systems with imperative state, but which are mostly left implicit or are at best informally specified. The paper presents both a programmatic contract API as well as a temporal contract language, and reports on experience and performance results from implementing these contracts in Racket.

Our development formalizes module behavior as a trace of events such as function calls and returns. Our contract system provides both non-interference (where contracts cannot influence correct executions) and also a notion of completeness (where contracts can enforce any decidable, prefix-closed predicate on event traces).

This paper appears to be about a way to define (and enforce through dynamic monitoring) correctness properties of APIs by enforcing or ruling out certain orderings of function calls, such as calling a "read" method on a file descriptor after having called "close". I am personally not convinced that this specification language is a good way to solve these problems. However, the bulk of the paper is actually about giving a denotational semantics to contracts, as specifying a set of traces that the external interface of a component may expose (in a way strongly reminding of game semantics), and this feels like an important technique to reason about contracts. The exposition of this contribution is practical (based on a simple abstract machine) and accessible.

### Haskell game to translate

### Gabriel Gonzalez: From mathematics to map-reduce

There's more mathematics to programming than meets the eye. This post will highlight one such connection that explains the link between map-reduce and category theory. I will then conclude with some wild speculation about what this might imply for future programming paradigms.

This post assumes that you already know Haskell and explains the mathematics behind the map-reduce using Haskell concepts and terminology. This means that this post will oversimplify some of the category theory concepts in order to embed them in Haskell, but the overall gist will still be correct.

Background (Isomorphism)In Haskell, we like to say that two types, s and t, are "isomorphic" if and only if there are two functions, fw and bw, of types

fw :: s -> tbw :: t -> s

... that are inverse of each other:

fw . bw = idbw . fw = id

We will use the symbol ≅ to denote that two types are isomorphic. So, for example, we would summarize all of the above by just writing:

s ≅ tThe fully general definition of isomorphism from category theory is actually much broader than this, but this definition will do for now.

Background (Adjoint functors)Given two functors, f and g, f is left-adjoint to g if and only if:

f a -> b ≅ a -> g bIn other words, for them to be adjoint there must be two functions, fw and bw of types:

fw :: (f a -> b) -> (a -> g b)bw :: (a -> g b) -> (f a -> b)

... such that:

fw . bw = idbw . fw = id

These "functors" are not necessarily the same as Haskell's Functor class. The category theory definition of "functor" is more general than Haskell's Functor class and we'll be taking advantage of that extra generality in the next section.

Free functorsImagine a functor named g that acted more like a type-level function that transforms one type into another type. In this case, g will be a function that erases a constraint named C. For example:

-- `g` is a *type-level* function, and `t` is a *type*g (C t => t) = t

In other words, g "forgets" the C constraint on type t. We call g a "forgetful functor".

If some other functor, f is left-adjoint to g then we say that f is the "free C" (where C is the constraint that g "forgets").

In other words, a "free C" is a functor that is left-adjoint to another functor that forgets the constraint C.

Free monoidThe list type constructor, [], is the "free Monoid"

The "free Monoid" is, by definition, a functor [] that is left-adjoint to some other functor g that deletes Monoid constraints.

When we say that g deletes Monoid constraints we mean that:

g (Monoid m => m) = m... and when we say that [] is left-adjoint to g that means that:

[] a -> b ≅ a -> g b... and the type [a] is syntactic sugar for [] a, so we can also write:

[a] -> b ≅ a -> g bNow substitute b with some type with a Monoid constraint, like this one:

b = Monoid m => mThat gives us:

[a] -> (Monoid m => m) ≅ a -> g (Monoid m => m)... and since g deletes Monoid constraints, that leaves us with:

[a] -> (Monoid m => m) ≅ a -> mThe above isomorphism in turn implies that there must be two functions, fw and bw, of types:

fw :: ([a] -> (Monoid m => m)) -> (a -> m)bw :: (a -> m) -> ([a] -> (Monoid m => m))

... and these two functions must be inverses of each other:

fw . bw = idbw . fw = id

We can pull out the Monoid constraint to the left for both of those types to give us these more idiomatic types:

fw :: Monoid m => ([a] -> m) -> ( a -> m)bw :: Monoid m => ( a -> m) -> ([a] -> m)

Both of these types have "obvious" implementations:

fw :: Monoid m => ([a] -> m) -> (a -> m)fw k x = k [x]

bw :: Monoid m => (a -> m) -> ([a] -> m)

bw k xs = mconcat (map k xs)

Now we need to prove that the fw and bw functions are inverse of each other. Here are the proofs:

-- Proof #1fw . bw

-- eta-expand

= \k -> fw (bw k)

-- eta-expand

= \k x -> fw (bw k) x

-- Definition of `fw`

= \k x -> bw k [x]

-- Definition of `bw`

= \k x -> mconcat (map k [x])

-- Definition of `map`

= \k x -> mconcat [k x]

-- Definition of `mconcat`

= \k x -> k x

-- eta-reduce

= \k -> k

-- Definition of `id`

= id

-- Proof #2

bw . fw

-- eta-expand

= \k -> bw (fw k)

-- eta-expand

= \k xs -> bw (fw k) xs

-- Definition of `bw`

= \k xs -> mconcat (map (fw k) xs)

-- eta-expand

= \k xs -> mconcat (map (\x -> fw k x) xs)

-- Definition of `fw`

= \k xs -> mconcat (map (\x -> k [x]) xs)

-- map (f . g) = map f . map g

= \k xs -> mconcat (map k (map (\x -> [x]) xs))

-- ... and then a miracle occurs ...

--

-- In all seriousness this step uses a "free theorem" which says

-- that:

--

-- forall (k :: Monoid m => a -> m) . mconcat . map k = k . mconcat

--

-- We haven't covered free theorems, but you can read more about them

-- here: http://ttic.uchicago.edu/~dreyer/course/papers/wadler.pdf

= \k xs -> k (mconcat (map (\x -> [x]) xs)

-- This next step is a proof by induction, which I've omitted

= \k xs -> k xs

-- eta-reduce

= \k -> k

-- Definition of `id`

= idMap reduce

Let's revisit the type and implementation of our bw function:

bw :: Monoid m => (a -> m) -> ([a] -> m)bw k xs = mconcat (map k xs)

That bw function is significant because it is a simplified form of map-reduce:

- First you "map" a function named k over the list of xs
- Then you "reduce" the list using mconcat

In other words, bw is a pure "map-reduce" function and actually already exists in Haskell's standard library as the foldMap function.

The theory of free objects predict that all other functions of interest over a free object (like the free Monoid) can be reduced to the above fundamental function. In other words, the theory indicates that we can implement all other functions over lists in terms of this very general map-reduce function. We could have predicted the importance of "map-reduce purely from the theory of "free Monoids"!

However, there are other free objects besides free Monoids. For example, there are "free Monads" and "free Categorys" and "free Applicatives" and each of them is equipped with a similarly fundamental function that we can use to express all other functions of interest. I believe that each one of these fundamental functions is a programming paradigm waiting to be discovered just like the map-reduce paradigm.

### Month in Haskell Mode January 2016

### Programmatic and Direct Manipulation, Together at Last

A technical report by Ravi Chugh et al. Abstract:

We present the SKETCH-N-SKETCH editor for Scalable Vector Graphics (SVG) that integrates programmatic and direct manipulation, two modes of interaction with complementary strengths. In SKETCH-N-SKETCH, the user writes a program to generate an output SVG canvas. Then the user may directly manipulate the canvas while the system infers realtime updates to the program in order to match the changes to the output. To achieve this, we propose (i) a technique called trace-based program synthesis that takes program execution history into account in order to constrain the search space and (ii) heuristics for dealing with ambiguities. Based on our experience writing more than 40 examples and from the results of a study with 25 participants, we conclude that SKETCH-N-SKETCH provides a novel and effective work- flow between the boundaries of existing programmatic and direct manipulation systems.

This was demoed at PLDI to a lot of fanfare. Also see some videos. And a demo that you can actually play with, sweet!

### Building / cross compile GHC for OpenBSD/macppc.

### Problems with cabal and stackage

### Roman Cheplyaka: Reducing boilerplate in finally tagless style

Typed Tagless, a.k.a tagless-final or finally tagless, is an approach to embedding DSLs and modeling data in general, advocated by Oleg Kiselyov. Instead of defining a set of algebraic data types to describe data or terms, thus focusing on how data is *constructed*, the approach focuses on data *consumption*, defining a canonical eliminator for every constructor that we would otherwise define.

For instance, instead of defining lists as

data List a = Nil | Cons a (List a)we would define a class

class List rep a where nil :: rep cons :: a -> rep -> repwhich of course corresponds to the Böhm-Berarducci (or Church) encoding of the above algebraic type.

Oleg has written extensively on the merits of this approach. In this article, I want to discuss a certain aspect of writing transformations in the finally tagless style.

The use case: language-integrated queryOleg, together with Kenichi Suzuki and Yukiyoshi Kameyama, have published a paper Finally, Safely-Extensible and Efficient Language-Integrated Query. In this paper, they employ the finally tagless approach to embed, optimize, and interpret SQL queries in OCaml.

Here are some excerpts from their OCaml code:

(* Base Symantics *) module type Symantics_base = sig ... (* lambda abstract *) val lam : ('a repr -> 'b repr) -> ('a -> 'b) repr (* application *) val app : ('a -> 'b) repr -> 'a repr -> 'b repr ... end (* Symantics with list operations *) module type SymanticsL = sig include Symantics (* comprehension *) val foreach : (unit -> 'a list repr) -> ('a repr -> 'b list repr) -> 'b list repr (* condition *) val where : bool repr -> (unit -> 'a list repr) -> 'a list repr (* yield singleton list *) val yield : 'a repr -> 'a list repr (* empty list *) val nil : unit -> 'a list repr (* not empty *) val exists : 'a list repr -> bool repr (* union list *) val (@%) : 'a list repr -> 'a list repr -> 'a list repr (* the table constructor which take a table name and table contents *) val table : (string * 'a list) -> 'a list repr end(‘Symantics’ is not a typo; it’s a portmanteau of ‘syntax’ and ‘semantics’.)

TransformationsA SQL trasnformation (such as transforming a subquery to a join) is represented by an ML functor, i.e. a function mapping one SymanticsL to another, which interprets the term slightly differently than the original one. I say *slightly*, because normally a transformation touches only a few relevant methods. The others are transformed mechanically following the Reflection-Reification pattern (RR). Informally speaking, we leave the irrelevant methods unchanged, applying the minimal transformation that makes them typecheck.

The question is, **how to avoid mentioning irrelevant methods when defining a transformation**?

This question is not idle. The language-integrated query code contains about 40 methods and 13 transformations. Pause for a second and imagine the amount of boilerplate that would have to be written if we needed to define every single method for every transformation. As we will see below, ML modules make this a non-issue. In Haskell, however, it is an issue, exhibited in Oleg’s own Haskell example (although easy to miss for a class that only contains 3 methods).

In OCaml, the RR is defined as a transformation of the whole module:

module OL(X:Trans) (F:SymanticsL with type 'a repr = 'a X.from) = struct include O(X)(F) open X let foreach src body = fwd (F.foreach (fun () -> bwd (src ())) (fun x -> bwd (body (fwd x)))) let where test body = fwd (F.where (bwd test) (fun () -> bwd (body ()))) let yield e = fmap F.yield e let nil () = fwd (F.nil ()) let exists e = fmap F.exists e let (@%) e1 e2 = fmap2 F.(@%) e1 e2 let table (name,data) = fwd @@ F.table (name, data) endWhen they define a transformation, they first transform the module in this mechanical fashion, and then override the few relevant methods:

module AbsBeta_pass(F:SymanticsL) = struct module X0 = struct type 'a from = 'a F.repr type 'a term = Unknown : 'a from -> 'a term | Lam : ('a term -> 'b term) -> ('a -> 'b) term let fwd x = Unknown x (* generic reflection *) let rec bwd : type a. a term -> a from = function (* reification *) | Unknown e -> e | Lam f -> F.lam (fun x -> bwd (f (fwd x))) end open X0 module X = Trans_def(X0) open X (* optimization *) module IDelta = struct let lam f = Lam f let app e1 e2 = match e1 with | Lam f -> f e2 | _ -> fmap2 F.app e1 e2 end end (* Combine the concrete optimization with the default optimizer *) module AbsBeta(F:SymanticsL) = struct module M = AbsBeta_pass(F) include OL(M.X)(F) (* the default optimizer *) include M.IDelta (* overriding `lam` and `app` *) endHow can we do this in Haskell?

Explicit dictionariesAn explicit dictionariy (a data type containing methods as its fields) seems like a great fit for Symantics. The RR transformation would be a simple function mapping one record to another. To define a transformation, we would override the relevant methods via record update.

However, explicit dictionaries are not that well suited for the finally tagless style. In OCaml, you can include one module into another (notice include Symantics in the OCaml code above). This “unpacks” the contents of one module into another, so that when you open the second module, the contents of the first module is available, too.

This is important for the finally tagless style. One of its strength is extensibility, which is achieved through such inclusion. Consequently, deep inclusion chains are common. With Haskell’s data types, unpacking such chains manually at every use site will quickly become unwieldy.

Type classesType classes are better suited for inclusion. If we declare

class Symantics1 rep => Symantics2 rep where { ... }and impose a Symantics2 rep constraint on a function definition, the methods of Symantics1 become available without any additional effort.

But then we don’t have good support for RR. Type class instances are not first class citizens; we can’t declare a function that transforms one instance into another. Nor can we create one instance from another by overriding a few methods… Or can we?

We can achieve our goal by using default method signatures.

We define the RR transformation simultaneously with the class itself:

class Symantics rep where lam :: (rep a -> rep b) -> rep (a -> b) default lam :: RR t rep => (t rep a -> t rep b) -> t rep (a -> b) lam f = fwd $ lam $ bwd . f . fwd app :: rep (a -> b) -> rep a -> rep b default app :: RR t rep => t rep (a -> b) -> t rep a -> t rep b app f x = fwd $ bwd f `app` bwd x foreach :: rep [a] -> (rep a -> rep [b]) -> rep [b] default foreach :: RR t rep => t rep [a] -> (t rep a -> t rep [b]) -> t rep [b] foreach a b = fwd $ foreach (bwd a) (bwd . b . fwd) ...The implementation of RR is straightforward:

class RR t rep where fwd :: rep a -> t rep a bwd :: t rep a -> rep aNow let’s define the AbsBeta pass in Haskell.

data AbsBeta rep a where Unknown :: rep a -> AbsBeta rep a Lam :: (AbsBeta rep a -> AbsBeta rep b) -> AbsBeta rep (a -> b) instance Symantics rep => RR AbsBeta rep where fwd = Unknown bwd = \case Unknown t -> t Lam f -> lam (bwd . f . fwd) instance Symantics rep => Symantics (AbsBeta rep) where lam = Lam app f x = case f of Unknown f' -> fwd $ app f' (bwd x) Lam b -> b xAll the methods not mentioned in the last instance get their default implementations based on RR, which is exactly what we wanted.

Associated typesApart from methods, ML/OCaml modules can also define types. This is used in the Language-integrated query paper and code in the following way:

(* Base Symantics *) module type Symantics_base = sig type 'a repr (* representation type *) val observe : (unit -> 'a repr) -> 'a obs ...In Haskell, we can replicate that with an associated type:

class SymanticsObs rep where type Obs rep :: * -> * observe :: rep a -> Obs rep a default observe :: RR t rep => t rep a -> Obs rep a observe = observe . bwdThe default definition for observe saves us from redefining it for derived representations, but what about Obs itself? We would like to write, in the spirit of default method signatures,

class SymanticsObs rep where type Obs rep :: * -> * type Obs (t rep) = repHowever, GHC would not let us to. Since recently, GHC does support default type declarations, but they need to be of the general form type Obs rep = ....

Nevertheless, we can create a type family that will extract the rep from t rep for us:

type family Peel (rep :: * -> *) :: (* -> *) where Peel (t rep) = rep class SymanticsObs rep where type Obs rep :: * -> * type Obs rep = Obs (Peel rep) observe :: rep a -> Obs rep a default observe :: RR t rep => t rep a -> Obs rep a observe = observe . bwdNow we can say

instance (Symantics rep, SymanticsObs rep) => SymanticsObs (AbsBeta rep)without having to define either type Obs or observe explicitly.

ConclusionExtensions such as default method signatures, default associated types, and type families can significantly reduce the boilerplate when defining transformations in the finally tagless style.

*Update.* Although I missed it on the first reading of the paper, /u/rpglover64 on reddit points out that the authors themselves acknowledge the boilerplate problem which this article addresses:

Haskell typeclasses made the encoding lightweight compared to OCaml modules. On the other hand, in OCaml we relied on the include mechanism to program optimizations by reusing the code for the identity transformation and overriding a couple of definitions. Haskell does not support that sort of code reuse among type classes. Therefore, programming tagless-final transformation in Haskell has quite a bit of boilerplate.