News aggregator

Extending Compiler With Authorized Types

haskell-cafe - Thu, 04/07/2016 - 10:17pm
Dear friends, we are thinking about implementing the paper Authenticated Data Structures, Generically[1], but we did not have any prior experience with extending Haskell. We are informed about compiler plugins[2] and hope that writing a compiler plugin will be enough to provide machinery required by the paper, but we are not sure about it. If anyone has an opinion on bringing Authenticated Data Structures to Haskell, please share. If there is some interest in our work, we will keep you up to date in this thread. - - - References: [1]: http://f.nn.lv/o5/a7/yk/GPADS-A_Miller-Authenticated_Data_Structures_Generically.pdf [2]: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/compiler-plugins.html — Kindest regards, Jonn Mostovoy (IOHK / Serokell) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Douglas M. Auclair (geophf): March 2016 1HaskellADay 1Liners

Planet Haskell - Thu, 04/07/2016 - 10:09pm
One-liners
  • March 29th, 2016: You have a list, Show a => [a], of known-length n, n > 100 Show the first three and the last three elements of that list
  • March 28th, 2016: You have f :: c -> d and g :: a -> b -> c
    define (<<-) such that f <<- g is f (g a b)
    Does it exist already (in the Prelude, maybe)?
  • March 26th, 2016: insert1 :: Ord k => k -> a -> Map k [a] -> Map k [a] define, points-free, efficiently. (hint: it's not insertWith)
  • March 26th, 2016: sqDist :: Fractional ä => [ä] -> [ä] -> ä sqDist v1 v2 = sum (zipWith (\a b -> (a - b) ^2) v1 v2) Point-free-itize sqDist (and λ)
  • March 17th, 2016: for f :: (a -> b) -> (a, a) -> (b, b) define f
    • obadz @obadzz f = join bimap
  • March 17th, 2016: removeAll :: Eq a => a -> [a] -> [a]; define
    e.g.: removeAll '"' "(\"S312\", \"S204\")" ~> "(S312, S204)"
    • obadz @obadzz removeAll = filter . (/=)
    • Gautier DI FOLCO @gautier_difolco ... same
  • March 17th, 2016:
    f, g :: (String, String) -> String
    let ab = ("a", "b")
    f ab ~> "(\"a\", b)"
    g ab ~> "(a, \"b\")"
    define h that generalizes f and g
    • Gautier DI FOLCO @gautier_difolco
      cp x y (a,b) = concat ["(", x a, ",", y b, ")"]
      f,g :: (String, String) -> String
      g = cp id show
      f = cp show id
Categories: Offsite Blogs

Building shared library to be called from C

haskell-cafe - Thu, 04/07/2016 - 5:52pm
Hi, I'm attempting to build a shared library that can be called from C. My end goal is to build a PAM module, but for now I'm working with toy programs so that I can get a feel for building how to build the library. The Haskell part looks like this (in a file called hfact.hs) module Hfact where import Foreign import Foreign.C.Types foreign export ccall fact_hs :: CInt -> CInt fact :: Int -> Int fact x = product [1..x] fact_hs :: CInt -> CInt fact_hs = fromIntegral . fact . fromIntegral I can compile this into a so (I think successfully) with "ghc --make -shared -dynamic -fPIC -o libhfact.so hfact.hs". Now I would like to be able to call this from C. I have a C program (in a file called main.c) as follows: #include <stdio.h> #include "HsFFI.h" #include "hfact_stub.h" int main(int argc, char *argv[]) { int user, answer; scanf("%d", &user); hs_init(&argc, &argv); answer = fact_hs(user); hs_exit(); printf("Result: %d\n", answer);
Categories: Offsite Discussion

Simple Interpreter with State Monad

haskell-cafe - Thu, 04/07/2016 - 3:29pm
I'm currently in a graphics class where, in order to provide a standard interface to all of our graphics libraries, we have to process small scripts that look like this: line 0 0 0 1 1 1 circle 0 0 10 scale 0 0 3 save pic.png I successfully wrote a parser with attoparsec that parses the file into a list of Commands. Now I'm trying to process that list to produce an IO action, and I thought the State monad would be useful to keep track of the persistent state of the shapes to draw and the transformations on them. I'm confused about how exactly to do this though. What should the type of my State be? Right now I have an execute function that is execute :: Command -> State ParseState (IO ()) where ParseState is a tuple of stuff. ParseState also includes an IO () because I wanted to be able to create multiple pictures one after another, and I couldn't figure out how to access the previous result value from State to add on to it in the next one. So can anyone offer advice on my specific situation, or maybe a s
Categories: Offsite Discussion

18th International Symposium on Principles and Practiceof Declarative Programming PPDP 2016 - 2nd call for papers

General haskell list - Thu, 04/07/2016 - 8:19am
====================================================================== Second call for papers 18th International Symposium on Principles and Practice of Declarative Programming PPDP 2016 Special Issue of Science of Computer Programming (SCP) Edinburgh, UK, September 5-7, 2016 (co-located with LOPSTR and SAS) http://ppdp16.webs.upv.es/ ====================================================================== SUBMISSION DEADLINE: 9 MAY (abstracts) / 16 MAY (papers) ---------------------------------------------------------------------- INVITED SPEAKERS Elvira Albert, Complutense University of Madrid, Spain ---------------------------------------------------------------------- PPDP 2016 is a forum that brings together researchers from the declarative programming communities, including those working in the logic, constraint and functional programming paradigms, but also embracing languages, database languages, and knowledge rep
Categories: Incoming News

wren gayle romano: Dissertating, ahoy!

Planet Haskell - Thu, 04/07/2016 - 1:09am

Usually whenever we think about gradschool we think about the switch from "doing classwork, quals, etc" to "dissertating" is a single-step process, which we call "becoming a PhD candidate" (as opposed to being a PhD student). In practice there are over half a dozen steps. Filing the paperwork declaring your completion of classwork, quals, etc is just the first few. (Okay, easy enough) Then there's the prospectus, for the graduate school. (The what for the who now?) Then the forming of your research committee. (Right, okay) Then the proposal. (Wait, how is this different from the other thing?) Then the proposal defense. (Um, okay, but not every department requires this?) Plus a few other steps I'm surely forgetting.

As of yesterday, I am officially finally totally completely absolutely done with all the paperwork, and can finally get back to actually working on the thesis itself!



comments
Categories: Offsite Blogs

Magnus Therning: Qt5+D-Bus+CMake, a complete example

Planet Haskell - Wed, 04/06/2016 - 6:00pm

Yesterday I started digging into Qt5 and D-Bus. I never found a complete example, so I put one together myself: https://gist.github.com/magthe/2cf7220655bd8bf431259cc7dee99f64.

Categories: Offsite Blogs

Neil Mitchell: Github Offline Issues with IssueSync

Planet Haskell - Wed, 04/06/2016 - 2:33pm

For a while I've been looking for something to download the GitHub issues for a project. I do a lot of development work on a train with no internet, so referring to the tickets offline is very useful. I've tried lot of tools, in a very wide variety of languages (Ruby, Python, Perl, Javascript, PHP) - but most of them don't seem to work - and the only one I did manage to get working only gave a curses UI.

Finally, I've found one that works - IssueSync. Installing it worked as described. Running it worked as described. I raised tickets for the author and they fixed them. I even sent a pull request and the author discussed and merged it. It downloads all your issues to Markdown files in an issues directory. I then "list" my issues using:

head -n1 -q issues/*.md | grep -v CLOSED

It's simple and works nicely.

Categories: Offsite Blogs

accessing the RTS -M flag value from GHC.RTS.Flags

haskell-cafe - Tue, 04/05/2016 - 9:46pm
Given, import GHC.RTS.Flags main = do gcf <- getRTSFlags print (maxHeapSize (gcFlags gcf)) And running on x86-64 in GHC 7.10.3, $ ./ghcflags 0 $ ./ghcflags +RTS -M1M 256 $ ./ghcflags +RTS -M1024K 256 $ ./ghcflags +RTS -M4096K 1024 Is there anyway I can get access to the value stored in the -M flag and depend on that value being correct? I was not able find it in the user's guide or anywhere else for that matter. Thanks, Adam
Categories: Offsite Discussion

Text.Regex.matchRegex: Success is empty?

haskell-cafe - Tue, 04/05/2016 - 9:16pm
Esteemed Haskellers, It is working for me, but I am puzzled by the matchRegex function: > import Text.Regex > :i matchRegex matchRegex :: Regex -> String -> Maybe [String] -- Defined in ‘Text.Regex’ Searches that fail return Nothing: > matchRegex (mkRegex "z") "abracadabra" Nothing which makes sense. But why do searches that succeed return an empty list of Strings? > matchRegex (mkRegex "a") "abracadabra" Just [] >
Categories: Offsite Discussion

Documenting extensions

haskell-cafe - Tue, 04/05/2016 - 9:12pm
I'd like to believe the Haskell report is a bible. I learned H98 using the Prelude as a source of examples and Hugs as a testbed. That was a comfortable and rewarding combination. Later I discovered that by default GHC rejected almost all my report-conforming (H98 and H2010) code. Ironically, its website at the time asserted, "Haskell is a standard language." In fact, far from reflecting biblical authority, the de facto Haskell discussed in this cafe comes in some 2^99 flavors -- enough to use a different language for every run of the compiler for the life of the universe. Witness: ghc --supported-languages | grep -v '^No[A-Z]' | wc -l (99 is the answer for GHC 7.8.4. In fact not all combinations of -X options are legal, but you get the point.) Unfortunately there is no coherent discussion of all those Haskells. The extensions section of the GHC User Guide gives no formal syntax, often teaches semantics only by example, and is replete with sales pitches, partial analogies, inconsistent terminology, an
Categories: Offsite Discussion

Brent Yorgey: The network reliability problem and star semirings

Planet Haskell - Tue, 04/05/2016 - 7:28pm

In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in a network. The problem is then to compute the probability that a message will successfully traverse the network from a given source node to a given target node.

Several commenters pointed out the connection to Bayesian networks. I think they are right, and the network reliability problem is a very special case of Bayesian inference. However, so far this hasn’t seemed to help very much, since the things I can find about algorithms for Bayesian inference are either too general (e.g. allowing arbitrary functions at nodes) or too specific (e.g. only working for certain kinds of trees). So I’m going to put aside Bayesian inference for now; perhaps later I can come back to it.

In any case, Derek Elkins also made a comment which pointed to exactly what I wanted to talk about next.

Star semirings and path independence

Consider the related problem of computing the reliability of the single most reliable path from to in a network. This is really just a disguised version of the shortest path problem, so one can solve it using Dijkstra’s algorithm. But I want to discuss a more general way to think about solving it, using the theory of star semirings. Recall that a semiring is a set with two associative binary operations, “addition” and “multiplication”, which is a commutative monoid under addition, a monoid under multiplication, and where multiplication distributes over addition and . A star semiring is a semiring with an additional operation satisfying . Intuitively, (though can still be well-defined even when this infinite sum is not; we can at least say that if the infinite sum is defined, they must be equal). If is a star semiring, then the semiring of matrices over is also a star semiring; for details see Dolan (2013), O’Connor (2011), Penaloza (2005), and Lehmann (1977). In particular, there is a very nice functional algorithm for computing , with time complexity (Dolan 2013). (Of course, this is slower than Dijkstra’s algorithm, but unlike Dijkstra’s algorithm it also works for finding shortest paths in the presence of negative edge weights—in which case it is essentially the Floyd-Warshall algorithm.)

Now, given a graph and labelling , define the adjacency matrix to be the matrix of edge probabilities, that is, . Let be the star semiring of probabilities under maximum and multiplication (where , since ). Then we can solve the single most reliable path problem by computing over this semiring, and finding the largest entry. If we want to find the actual most reliable path, and not just its reliability, we can instead work over the semiring , i.e. probabilities paired with paths. You might enjoy working out what the addition, multiplication, and star operations should be, or see O’Connor (2011).

In fact, as shown by O’Connor and Dolan, there are many algorithms that can be recast as computing the star of a matrix, for an appropriate choice of semiring: for example, (reflexive-)transitive closure; all-pairs shortest paths; Gaussian elimination; dataflow analysis; and solving certain knapsack problems. One might hope that there is similarly an appropriate semiring for the network reliability problem. But I have spent some time thinking about this and I do not know of one.

Consider again the simple example given at the start of the previous post:

For this example, we computed the reliability of the network to be , by computing the probability of the upper path, , and the lower path, , and then combining them as , the probability of success on either path less the double-counted probability of simultaneous success on both.

Inspired by this example, one thing we might try would be to define operations and . But when we go to check the semiring laws, we run into a problem: distributivity does not hold! , but . The problem is that the addition operation implicitly assumes that the events with probabilities and are independent: otherwise the probability that they both happen is not actually equal to . The events with probabilities and , however, are not independent. In graph terms, they represent two paths with a shared subpath. In fact, our example computation at the beginning of the post was only correct since the two paths from to were completely independent.

Graph reduction

We can at least compute the reliability of series-parallel graphs whose terminals correspond with and :

  • If consists of a single edge, return that edge’s probability.
  • Otherwise, is a composition of two subgraphs, whose reliabilities we recursively compute. Then:
    • If is a sequential composition of graphs, return the product of their reliabilities.
    • If is a parallel composition of two graphs with reliabilities and , return .

In the second case, having a parallel composition of graphs ensures that there are no shared edges between them, so and are indeed independent.

Of course, many interesting graphs are not series-parallel. The simplest graph for which the above does not work looks like this:

Suppose all the edges have probability . Can you find the reliability of this network?

More in a future post!

References

Dolan, Stephen. 2013. “Fun with Semirings: A Functional Pearl on the Abuse of Linear Algebra.” In ACM SIGPLAN Notices, 48:101–10. 9. ACM.

Lehmann, Daniel J. 1977. “Algebraic Structures for Transitive Closure.” Theoretical Computer Science 4 (1). Elsevier: 59–76.

O’Connor, Russell. 2011. “A Very General Method for Computing Shortest Paths.” http://r6.ca/blog/20110808T035622Z.html.

Penaloza, Rafael. 2005. “Algebraic Structures for Transitive Closure.” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650.


Categories: Offsite Blogs

Journal of Functional Programming - Call for PhDAbstracts

haskell-cafe - Tue, 04/05/2016 - 9:34am
If you or one of your students recently completed a PhD in the area of functional programming, please submit the dissertation abstract for publication in JFP: simple process, no refereeing, deadline 30th April 2016. Best wishes, Graham ============================================================ CALL FOR PHD ABSTRACTS Journal of Functional Programming Deadline: 30th April 2016 http://tinyurl.com/jfp-phd-abstracts ============================================================ PREAMBLE: Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year. The abstracts are made freely available on the JFP website, i.e. not behind any paywall. They do not require any transfer of copyright, merely a license from the author. A dissertation is eligible for inclusion if parts of it have or could have appeared in JFP, that is, if it is in the general area of f
Categories: Offsite Discussion

Journal of Functional Programming - Call for PhD Abstracts

General haskell list - Tue, 04/05/2016 - 9:34am
If you or one of your students recently completed a PhD in the area of functional programming, please submit the dissertation abstract for publication in JFP: simple process, no refereeing, deadline 30th April 2016. Best wishes, Graham ============================================================ CALL FOR PHD ABSTRACTS Journal of Functional Programming Deadline: 30th April 2016 http://tinyurl.com/jfp-phd-abstracts ============================================================ PREAMBLE: Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year. The abstracts are made freely available on the JFP website, i.e. not behind any paywall. They do not require any transfer of copyright, merely a license from the author. A dissertation is eligible for inclusion if parts of it have or could have appeared in JFP, that is, if it is in the general area of f
Categories: Incoming News

Call for papers for David Turner's Festschrift issue ofJUCS

General haskell list - Tue, 04/05/2016 - 9:07am
Friends David Turner was one of the two people who changed my life by introducing me to functional programming (*). David designed and implemented a succession of functional languages, Sasl, KRC, and Miranda, that made lazy functional programming into a tool you could use to get work done. They all used SK-combinator reduction in their implementations, a technique of irresistibly simple beauty, invented by Curry and Feys, but refined and popularised by David. For David’s 70th birthday, the Journal of Universal Computer Science is running a special Festschrift issue on “Functional programming: past, present, and future” in David’s honour. The Call for Papers is attached. Here’s the timetable. · 1 July 2016: Paper submissions. · 1 September 2016: Author notification. · 1 October, 2016: Revised version due. · 15 October 2016: Final notification. · 30 October 2016: Camera Ready Copy. Do consider submitting a paper. Simon (*) Arthur Norman w
Categories: Incoming News

Philip Wadler: Steven Pinker's The Sense of Style

Planet Haskell - Tue, 04/05/2016 - 2:35am

I recently read Pinker's The Sense of Style, and urge you to read it too. It is chock full of practical advice on how to make your writing better. Chapter One shows you how to appreciate good writing; I never knew an obituary could be so zippy. Chapter Two explains the approach to writing called 'the classical style', which I have used my whole life without realising it. Chapter Three describes how to keep knowing what you are talking about from getting in the way of communicating clearly. Pinker is an expert on modern grammar, and Chapter Four clarifies how to parse your sentences to avoid ambiguity and employ referents correctly. Chapter Five details the mechanics of how to make a passage cohere. Chapter Six catalogues, from Pinker's position on the usage panel for the American Heritage dictionary, contentious points of diction, with his advice on how to resolve them and what points to consider when resolving them for yourself.
I recommend it highly, and doubly so if you are ever likely to write something that I will have to read.

Categories: Offsite Blogs

Darcs+Pijul Hacking Sprint #11 (May 6th-8th,Helsinki)

haskell-cafe - Mon, 04/04/2016 - 10:36pm
Dear Hackers, The 11th Darcs Sprint, organised by and jointly with the Pijul team, will be in Helsinki, on Friday May 6th-Sunday May 8th, at Aalto University's startup sauna in the Otaniemi Campus. Please check the details at http://pijul.org/2016/04/02/sprint.html Many thanks to Pierre-Étienne Meunier for organising it. The Darcs planning page is at: http://darcs.net/Sprints/2016-05 Here are three things to know: 1. Everybody is welcome to join us. We'd love to have you, whatever your hacking experience with Pijul or Darcs. Also, if you've got a wacky idea for the future of version control, or a cool use for the Darcs or Pijul libraries, you should join us too. 2. If you're attending please add your name to http://wiki.darcs.net/Sprints/2016-05 3. We may be able to reimburse travel costs (within reason!). Let us know if you'd like a reimbursement, and save your receipts. Many thanks to everybody who participated in our fundraising drives or who gave money on the side. Tha
Categories: Offsite Discussion

[ANN] bond-haskell: yet another data serializationlibrary

haskell-cafe - Mon, 04/04/2016 - 8:48pm
bond-haskell and bond-haskell-compiler is a pair of packages adding Haskell support to bond serialization framework. Bond is an open source, cross-platform framework for working with schematized data. It supports cross-language serialization/deserialization and powerful generic mechanisms for efficiently manipulating data. It is broadly used at Microsoft in high scale services. For a discussion how Bond compares to similar frameworks (most notably protobufs) see https://microsoft.github.io/bond/why_bond.html Microsoft's bond package or other foreign code is not needed for building or using bond-haskell, all dependencies are published to hackage. For those interested, Microsoft's code is published at https://github.com/Microsoft/bond/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

[ANN] protobuf-simple: Protocol Buffers library

haskell-cafe - Mon, 04/04/2016 - 8:32pm
Hello, I've just released protobuf-simple, an Haskell implementation of Google's Protocol Buffers with an emphasis on simplicity. This implementation consists of a library for the encoding and decoding of data and an executable for generating Haskell types from proto files. The code can be found at https://github.com/sru-systems/protobuf-simple Kind regards, Martijn Rijkeboer
Categories: Offsite Discussion

CFP SBLP 2016: 20th Brazilian Symposium on Programming Languages *** Deadline for Abstracts Approaching***

General haskell list - Mon, 04/04/2016 - 8:24pm
[Apologies if you receive multiple copies of this CFP] *** Deadline for Abstracts Approaching*** ======================================================= The Brazilian Symposium on Programming Languages is a well-established symposium which provides a venue for researchers and practitioners interested in the fundamental principles and innovations in the design and implementation of programming languages and systems. SBLP 2016 will be held in Maringá, in the Southern region of Brazil, and will be the 20th edition of the symposium. SBLP is part of the 7th edition of CBSoft, the Brazilian Congress on Software: Theory and Practice. More information is available at http://cbsoft.org/sblp2016/xx-brazilian-symposium-on-programming-languages. IMPORTANT DATES Abstract submission: April 8th 2016 Paper submission: April 15th 2016 Author notification: May 27th 2016 Camera ready deadline: June 10th 2016 Symposium dates: September 22nd and 23rd Authors are invited to submit original research on any relevant top
Categories: Incoming News