News aggregator

Foldable/Traversable and Applicative/Monoid?

haskell-cafe - 0 sec ago
Hi all, I don't understand why Foldable is a necessary super-class of Traversable, and I suspect that the Applicative/Monoid duality, which I've just begun discovering in the literature, has something to do with why that is so. Can anyone give me a hint, without giving me the answer? Thanks! -db _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Month in haskell-ide-engine January 2016

haskell-cafe - 0 sec ago
Welcome Haskell IDE Engine users, Haskell IDE Engine progress report for January 2016 [1] What is Haskell IDE Engine? Not an IDE. It is a common point for people in the Haskell community to pool their efforts with respect to tooling. For tool writers, provide tools as a HIE plugin, so it can be available on supported IDEs For IDE developers, integrate to HIE, and all the Haskell tools supported as plugins become available For users, it means the overall Haskell experience should improve. Important developments A new ghc-dump-tree plugin based on https://github.com/edsko/ghc-dump-tree Current project focus The current focus is to get the initial version working well enough for an alpha release. To this end, there are some hardy developers using it in their daily work in emacs. Issues closed in January Querying a graph database instead of using GHC-API? #10 Decide how haskell-ide project is run #13 Rework the Console #20 Use an error handler in the dispatcher #50 Protocol definition #66 (emacs) "S
Categories: Offsite Discussion

something went wrong

del.icio.us/haskell - 58 min 57 sec ago
Categories: Offsite Blogs

Douglas M. Auclair (geophf): Graphing with Goats

Planet Haskell - 11 hours 17 min ago
Slides, presented comme ça! Links at the end



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 linkurio.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:
20. Buh-bay!
Categories: Offsite Blogs

Douglas M. Auclair (geophf): January 2016 1HaskellADay Problems and Solutions

Planet Haskell - 11 hours 27 min ago
  • 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
Categories: Offsite Blogs

Is there a way to generate instances from the GHCiREPL?

haskell-cafe - Thu, 02/04/2016 - 4:56pm
Good evening, Is there a way with TH to generate instances for a class in GHCi? I want to generate instances for a serialization class. I tried to write some TH to do it, but $(foo) in GHCi’s REPL says that it can only be Q Exp, not Q [Dec]. Sadness. I found qAddTopDecls. I tried to add the class declarations via $(foo >>= qAddTopDecls; stringE "OK!") and it says “Only function, value, and foreign import declarations may be added with addTopDecl". Woe. I could create a file and then load in that file, but loading modules loses all GHCi's state, which would defeat the purpose of using a REPL in the first place. Any hope? Ciao! ​ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Temporal Higher Order Contracts

Lambda the Ultimate - Thu, 02/04/2016 - 2:33pm

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 "closed". 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.

Categories: Offsite Discussion

Haskell game to translate

haskell-cafe - Thu, 02/04/2016 - 10:28am
Hi, Cafe. My friend wants to improve her collaboration skills in the area of game development. She is a Translator and the plan is to learn Git by contributing some Russian/English/French (and maybe simple Korean) translations to a GitHub project. Could you recommend me (and my friend) some game project wich needs translation? Note, that It should support multylang features in some form, understandable for non-programmer. I'll help with required workplace setup. Haskell, Linux, etc. is OK. Regards, Sergey
Categories: Offsite Discussion

Gabriel Gonzalez: From mathematics to map-reduce

Planet Haskell - Thu, 02/04/2016 - 12:32am

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 -> t
bw :: t -> s

... that are inverse of each other:

fw . bw = id
bw . 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 ≅ t

The 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 b

In 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 = id
bw . 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 functors

Imagine 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 monoid

The 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 b

Now substitute b with some type with a Monoid constraint, like this one:

b = Monoid m => m

That 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 -> m

The 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 = id
bw . 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 #1
fw . 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.

Categories: Offsite Blogs

Month in Haskell Mode January 2016

haskell-cafe - Wed, 02/03/2016 - 11:02pm
Welcome Haskell Mode users, Haskell Mode progress report for January 2016. For previous issue see December 2015 <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-December-2015>. Reddit discussion <https://www.reddit.com/r/haskell/comments/441ukg/month_in_haskell_mode_january_2016/> . <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-January-2016#what-is-haskell-mode>What is Haskell Mode? Haskell Mode is an umbrella project for multiple Emacs tools for efficient Haskell development. Haskell Mode is an open source project developed by a group of volunteers constantly looking for contributions. For more information how to help see https://github.com/haskell/haskell-mode. <https://github.com/haskell/haskell-mode/wiki/Month-in-Haskell-Mode-January-2016#important-developments>Important developments Haskell Mode 2015 retrospective <https://github.com/haskell/haskell-mode/wiki/Haskell-Mode-2015-retrospective> was published. Emacs 23 support was dropped. Last stable haskell-mod
Categories: Offsite Discussion

Building / cross compile GHC for OpenBSD/macppc.

haskell-cafe - Wed, 02/03/2016 - 3:31pm
Hello ! I am new here - sorry, if I ask something what was asked before. OpenBSD provides for amd64 and other platforms GHC and, also the haskell-platform which works very good. I try to get one of the old PowerMac's with a G5 CPU and saw, that there is no GHC (yes, there is a very old version - something like 3.x) for OpenBSD/macppc. I got some informations about to cross compile and saw also the wiki at https://ghc.haskell.org/trac/ghc/wiki/Building/CrossCompiling now my main question is, are there more informations about it ? Available for cross compile is GHC and haskell-platform 7.10.3, gcc 4.2.1 20070719, llvm 3.5.20140228 all on amd64. The planned target platforms are Mac's / PowerMac's with G3, G4 and G5 CPU's. All versions of OpenBSD/macppc are 32 bit only (including the G5). A cross compile from Mac OS X is no option because the OpenBSD project should be able to cross build on their machines (security reasons). Thanks for informations and tips. Regards, Christoph
Categories: Offsite Discussion

Problems with cabal and stackage

haskell-cafe - Wed, 02/03/2016 - 2:13pm
Hi, Overnight there seems to have been a change to stackage where it's now issuing redirects from http to https URLs: ~$ cabal update Downloading the latest package list from stackage-lts-2.22 Warning: http error: Unable to handle redirect, unsupported scheme: https://www.stackage.org/snapshot/lts-2.22/00-index.tar.gz cabal: Failed to download http://www.stackage.org/snapshot/lts-2.22/00-index.tar.gz : ErrorMisc "Error HTTP code: 301" My cabal doesn't seem to like https and I think it's a recentish version: $ cabal --version cabal-install version 1.22.0.0 using version 1.22.0.0 of the Cabal library I'm probably using a bit of an old workflow (and I know that LTS-2 is pretty old too) but is there any simple way of getting this working again? Cheers, _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Roman Cheplyaka: Reducing boilerplate in finally tagless style

Planet Haskell - Wed, 02/03/2016 - 2:00pm
Introduction

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 -> rep

which 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 query

Oleg, 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’.)

Transformations

A 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) end

When 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` *) end

How can we do this in Haskell?

Explicit dictionaries

An 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 classes

Type 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 a

Now 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 x

All the methods not mentioned in the last instance get their default implementations based on RR, which is exactly what we wanted.

Associated types

Apart 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 . bwd

The 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) = rep

However, 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 . bwd

Now we can say

instance (Symantics rep, SymanticsObs rep) => SymanticsObs (AbsBeta rep)

without having to define either type Obs or observe explicitly.

Conclusion

Extensions 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.

Categories: Offsite Blogs

Functional Jobs: OCaml server-side developer at Ahrefs Research (Full-time)

Planet Haskell - Wed, 02/03/2016 - 1:36pm
Who we are

Ahrefs Research is a San Francisco branch of Ahrefs Pte Ltd (Singapore), which runs an internet-scale bot that crawls whole Web 24/7, storing huge volumes of information to be indexed and structured in timely fashion. On top of that Ahrefs is building analytical services for end-users.

Ahrefs Research develops a custom petabyte-scale distributed storage to accommodate all that data coming in at high speed, focusing on performance, robustness and ease of use. Performance-critical low-level part is implemented in C++ on top of a distributed filesystem, while all the coordination logic and communication layer, along with API library exposed to the developer is in OCaml.

We are a small team and strongly believe in better technology leading to better solutions for real-world problems. We worship functional languages and static typing, extensively employ code generation and meta-programming, value code clarity and predictability, constantly seek out to automate repetitive tasks and eliminate boilerplate, guided by DRY and following KISS. If there is any new technology that will make our life easier - no doubt, we'll give it a try. We rely heavily on opensource code (as the only viable way to build maintainable system) and contribute back, see e.g. https://github.com/ahrefs . It goes without saying that our team is all passionate and experienced OCaml programmers, ready to lend a hand or explain that intricate ocamlbuild rule.

Our motto is "first do it, then do it right, then do it better".

What we need

Ahrefs Research is looking for backend developer with deep understanding of operating systems, networks and taste for simple and efficient architectural designs. Our backend is implemented mostly in OCaml and some C++, as such proficiency in OCaml is very much appreciated, otherwise a strong inclination to intensively learn OCaml in a short term will be required. Understanding of functional programming in general and/or experience with other FP languages (F#,Haskell,Scala,Scheme,etc) will help a lot. Knowledge of C++ and/or Rust is a plus.

The candidate will have to deal with the following technologies on the daily basis:

  • networks & distributed systems
  • 4+ petabyte of live data
  • OCaml
  • linux
  • git

The ideal candidate is expected to:

  • Independently deal with and investigate bugs, schedule tasks and dig code
  • Make argumented technical choice and take responsibility for it
  • Understand the whole technology stack at all levels : from network and userspace code to OS internals and hardware
  • Handle full development cycle of a single component, i.e. formalize task, write code and tests, setup and support production (devops)
  • Approach problems with practical mindset and suppress perfectionism when time is a priority

These requirements stem naturally from our approach to development with fast feedback cycle, highly-focused personal areas of responsibility and strong tendency to vertical component splitting.

What you get

We provide:

  • Competitive salary
  • Modern office in San Francisco SOMA (Embarcadero)
  • Informal and thriving atmosphere
  • First-class workplace equipment (hardware, tools)
  • No dress code

Get information on how to apply for this position.

Categories: Offsite Blogs

Accessing and Inspecting StgBindings in Ghci

haskell-cafe - Wed, 02/03/2016 - 8:30am
Hi all, I'm currently trying to understand how STG works, and my goal right now is to be able to inspect StgBinding values. I've written a short program, based on the wiki article GHC/As a library <https://wiki.haskell.org/GHC/As_a_library>, like below:
Categories: Offsite Discussion

Tom Schrijvers: New Postdoc Vacancy in Functional/Constraint/Logic Programming

Planet Haskell - Wed, 02/03/2016 - 5:54am

I have a new postdoc vacancy in my group. For more details, please read the official vacancy announcement or get in touch.
Categories: Offsite Blogs

Can we improve Show instance for non-ascii charcters?

haskell-cafe - Wed, 02/03/2016 - 3:37am
Show instance for non-ascii characters prints their character codes. This is sad for Haskell users that speaks language other than English. 'A' '\196' '\28450' ["Simon's dad","John's dad","Simon's mom","John's mom"] ["\30000\20013\12398\29238","\23665\30000\12398\29238","\30000\20013\12398\27597","\23665\30000\12398\27597"] The function that needs improvement is showLitChar in GHC.Show, which currently prints any character larger than ASCII code 127 by its character code: http://haddock.stackage.org/lts-5.1/base-4.8.2.0/src/GHC-Show.html showLitChar :: Char -> ShowS showLitChar c s | c > '\DEL' = showChar '\\' (protectEsc isDec (shows (ord c)) s) On the other hand, there is GHC.Unicode.isPrint, the predicate for printable Unicode characters, that is calling on a foreign function u_iswprint for the knowledge. https://hackage.haskell.org/package/base-4.8.2.0/docs/src/GHC.Unicode.html#isPrint I think one of the solution is to import and call u_iswprint from GHC.Show, too, but I don't kno
Categories: Offsite Discussion

wren gayle romano: It's official, I'm off to Google

Planet Haskell - Wed, 02/03/2016 - 12:43am

It's official, I'm heading to Google at the end of July to work with Mark Larson on the Chrome OS security team (of all things!). Seems an unlikely match, but Mark was pretty keen on my background (including the gender stuff!) and wasn't put off by my fusion of linguistics, type-theory, constructive logic/maths, et al. I guess the security team is more concerned with semantic models and constructive correctness than the other teams I talked with. Makes sense, I suppose, but it's sad that these are still thought of as "security" concerns rather than "everything in programming" concerns.

I'm totally looking forward to it, but I am still thinking of it as a bit of an experiment. I'm an academic at heart, so I could see myself heading back to academia in a few years. (Wanting to be a professor is, afterall, what motivated me to start gradschool in the first place.) Then again, I've never really thought of industry as being interested in the sorts of theory I work on. In any case, I'll still be around at the various conferences I've been frequenting; I won't just disappear into industry.

I know a bunch of y'all are in the bay area. I'd love to hear any pointers you have on apartment hunting or on what neighborhoods (nearish Mt View) are nice— i.e., places an artistic disabled radical queer woman might like. Feel free to comment below or get in touch by email, twitter, etc.



comments
Categories: Offsite Blogs

PROHA 2016 (< at > CGO'16): Early Registration Deadline (Feb 3)

General haskell list - Wed, 02/03/2016 - 12:23am
****************************************************************************** PROHA 2016 -- CALL FOR PARTICIPATION First Workshop on Program Transformation for Programmability in Heterogeneous Architectures Website: http://goo.gl/RzGbzY Barcelona, 12th March 2016 In conjunction with the CGO'16 Conference ==== Early Bird Registration: February 3rd, 2016 ==== For registration information, please see http://cgo.org/cgo2016/registration/ ****************************************************************************** The PROHA workshop focuses on techniques and foundations to make it possible to perform source code transformations that preserve the intended semantics of the original code and improve efficiency, portability or maintainability. The topics of interest for the workshop include, non-exclusively: program annotations to capture algorithmic properties and intended code semantics; programming paradigms able to express underlying (mat
Categories: Incoming News

Is there a type class for boring types?

haskell-cafe - Tue, 02/02/2016 - 7:41pm
Or, alternatively, some common class that lets me express that a type is boring (i.e., inhabited by precisely one fully-defined value)? lens has Settable, whose law ensures the type involved has a boring representation (in the sense of representable functor), but is there a more fundamental way? class Boring x where inhabitant :: x instance Boring () where inhabitant = () instance Boring (Proxy a) where inhabitant = Proxy instance Boring y => Boring (x -> y) where inhabitant = const inhabitant instance (Boring x, Boring y) => Boring (x, y) where inhabitant = (inhabitant, inhabitant) instance Boring x => Boring (Const x y) where inhabitant = Const inhabitant instance Boring x => Boring (Identity x) where inhabitant = Identity inhabitant ... _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion