July 2017 - Haskell-Cafe

representations of probability distributions
by Olaf Klinke 04 Jul '17

04 Jul '17

Dear cafe, following up the announcement of bali-phy and the discussion that ensued, I'd like ask the cafe for an overview of representations of probability distributions as data types. It seems that all packages mentioned to far use some flavour of Markov chain. Why? What else is there? Can someone recommend a survey publication/book/talk? Explicitly I am interested in: - the data type, as in Haskell's type system - how an element of the data type relates to the distribution it describes - how the monad instance works (if there is one) - how to compute conditionals (if computable) - how to compute integrals (if computable) - what base types are supported (finite types, reals, products ...) Below is an incomplete, and possibly oversimplified (or even wrong), list of my own. Additions and corrections welcome. -- Olaf 1. Markov chains - uses a random number generator - type is something like Markov a = a -> IO a - repeated execution produces an infinite trace xs :: [a] where for each predicate p :: a -> Bool, the limit of (length (filter p (take n xs))) % n as n tends to infinity approaches the probability of p under the distribution modeled. - monad instance? - conditionals? - integrals? - supported base types a in Markov a? 2. Riesz functionals: possibly the most functional representation - representation as linear functionals Riesz a = (a -> R) -> R for a suitable real number type R - embed predicates in the type (a -> R) via characteristic functions characteristic p = \a -> if p a then 1 else 0 Then for a functional phi :: Riesz a and p :: a -> Bool, phi (characteristic p) is the probability of p. - Monad instance is the same as for the continuation monad - conditionals? - integration is trivial: evaluation - arbitrary base types - but how would you even declare a uniform distribution in this type? 3. Density functions - represent a distribution on the reals as density function w.r.t. the Lebesgue measure - limited to reals (and products thereof) - data type possibly holds only parameters of parametric families (gaussian, beta, gamma, ...) - computing conditionals only for matching pairs of prior and sampling function (conjugate priors), analytically - integration analytically - no monad instance because no arbitrary base type 4. Finite distributions - type Dist a = [(a,R)] for suitable real number type R - optimizations use search trees instead of flat lists - basically composition of list and writer monads, where R is regarded as monoid under multiplication - represents a distribution of finite support. If phi :: Dist a, then probability p = sum $ map snd $ filter (p.fst) phi - conditioning possible if base type is of Eq class and R supports division - gets unwieldy without Ord instance of base type to keep the list small 5. Valuations - type Val a = (a -> Bool) -> R for suitable real number type R - models mathematical definition closely - monad bind is integration: requires exact reals R due to limit process - conditioning possible if R supports division

2 1

Haskell Implementors' Workshop Call for Talks
by Richard Eisenberg 04 Jul '17

04 Jul '17

Call for Contributions ACM SIGPLAN Haskell Implementors' Workshop http://icfp17.sigplan.org/track/hiw-2017 Oxford, UK, 9 September, 2017 Co-located with ICFP 2017 http://www.icfpconference.org/icfp2017/ Important dates --------------- Proposal Deadline: Thursday, 6 July, 2017 Notification: Thursday, 20 July, 2017 Workshop: Saturday, 9 September, 2017 The 9th Haskell Implementors' Workshop is to be held alongside ICFP 2017 this year in Oxford. It is a forum for people involved in the design and development of Haskell implementations, tools, libraries, and supporting infrastructure, to share their work and discuss future directions and collaborations with others. Talks and/or demos are proposed by submitting an abstract, and selected by a small program committee. There will be no published proceedings. The workshop will be informal and interactive, with open spaces in the timetable and room for ad-hoc discussion, demos, and impromptu short talks. Scope and target audience ------------------------- It is important to distinguish the Haskell Implementors' Workshop from the Haskell Symposium which is also co-located with ICFP 2017. The Haskell Symposium is for the publication of Haskell-related research. In contrast, the Haskell Implementors' Workshop will have no proceedings -- although we will aim to make talk videos, slides and presented data available with the consent of the speakers. The Implementors' Workshop is an ideal place to describe a Haskell extension, describe works-in-progress, demo a new Haskell-related tool, or even propose future lines of Haskell development. Members of the wider Haskell community encouraged to attend the workshop -- we need your feedback to keep the Haskell ecosystem thriving. Students working with Haskell are specially encouraged to share their work. The scope covers any of the following topics. There may be some topics that people feel we've missed, so by all means submit a proposal even if it doesn't fit exactly into one of these buckets: * Compilation techniques * Language features and extensions * Type system implementation * Concurrency and parallelism: language design and implementation * Performance, optimisation and benchmarking * Virtual machines and run-time systems * Libraries and tools for development or deployment Talks ----- We invite proposals from potential speakers for talks and demonstrations. We are aiming for 20-minute talks with 5 minutes for questions and changeovers. We want to hear from people writing compilers, tools, or libraries, people with cool ideas for directions in which we should take the platform, proposals for new features to be implemented, and half-baked crazy ideas. Please submit a talk title and abstract of no more than 300 words. Submissions should be made via HotCRP. The website is: https://icfp-hiw17.hotcrp.com/ We will also have a lightning talks session which will be organised on the day. These talks will be 5-10 minutes, depending on available time. Suggested topics for lightning talks are to present a single idea, a work-in-progress project, a problem to intrigue and perplex Haskell implementors, or simply to ask for feedback and collaborators. Program Committee ----------------- * Richard A. Eisenberg -- chair (Bryn Mawr College) * Adam Gundry (Well-Typed) * Bartosz Nitka (Facebook) * Wren Romano (X, formerly Google[x]) * Alejandro Serrano Mena (Utrecht University) * Jan Stolarek (University of Edinburgh) Contact ------- * Richard A. Eisenberg <rae(a)cs.brynmawr.edu>

1 1

speed of hashing
by Dennis Raddle 04 Jul '17

04 Jul '17

Hello, I have an application which could benefit from caching certain computations. For instance, I might have a function: listToWord :: [Int] -> Word16 which takes an integer X in the input as referring to bit X in the output word, and sets the bits. I have to run this computation many times within the inner loop. So I thought I could cache it. The only trouble is that it may not be any less expensive to convert the [Int] into a hash value, or use it as a key to look up a binary Map. What do you think? Does Haskell hashing use some kind of optimized computation that's faster than me writing a loop by hand? D

2 2

Re: [Haskell-cafe] type (++) = (<>)
by Doug McIlroy 03 Jul '17

03 Jul '17

> What do you think of making (++) the same as (<>) Before Haskell 98, ++ was an overloadable operator associated with class MonadPlus. Why was that arrangement abolished? Doug

1 0

Re: [Haskell-cafe] Master programme with Haskell prospects
by Olaf Klinke 02 Jul '17

02 Jul '17

Please follow Abhiroop's advice. The English midlands is a great region for functional minds. There is not only Nottingham: There is Leeds, Birmingham, Leicester and Swansea nearby, all of which have CS departments with very experienced scientists in that area. The midlands have the midlands graduate school [1]! I did my degree at the University of Birmingham, whose CS department is, as I dare say, run by a bunch of mathematicians. You can find any level of abstractness there, ranging from compiling ML to hardware up to topos theory. It was there I decided to learn Haskell. Recently they had a graduate whose entire dissertation [2] has an Agda version [3] so you can not only read it, but also execute. Olaf [1] http://www.cs.nott.ac.uk/MGS/ [2] http://etheses.bham.ac.uk/5967/ [3] http://www.cs.bham.ac.uk/~mhe/continuity-false/

1 0

Re: [Haskell-cafe] Fast JSON validation - reducing allocations
by Ben Gamari 01 Jul '17

01 Jul '17

David Turner <dave.c.turner(a)gmail.com> writes: > On 11 May 2017 at 19:40, Ben Gamari <ben(a)smart-cactus.org> wrote: > >> Ccing Luke Maurer under the assumption that he will appreciate seeing >> the fruits of his labor. >> >> >> David Turner <dct25-561bs(a)mythic-beasts.com> writes: >> >> > Dear Café, >> > >> (snip) >> > >> > There's a copy of the relevant code for option 4 at >> > https://github.com/DaveCTurner/json-validator. I've hacked around with >> it a >> > bit since producing the numbers above, so it's now apparently a bit >> slower >> > than Aeson but allocates less too (~65kB). >> > >> > Could anyone help, e.g. by pointing me at the bit in the Core that is >> > allocating within the main loop? >> > >> While turning this over in my head I realized that this is the sort of >> program which may be helped significantly by GHC 8.2's improved join >> point handling. Indeed the timings seem to support this hypothesis: >> >> GHC 8.0.2 >> >> benchmarking json-validator/Automaton/testEvent >> time 22.84 μs (22.76 μs .. 22.94 μs) >> 1.000 R² (1.000 R² .. 1.000 R²) >> mean 22.84 μs (22.76 μs .. 22.94 μs) >> std dev 297.4 ns (221.8 ns .. 378.8 ns) >> >> Alloc rate 4,015,256,078,038 bytes per MUT second >> >> GHC 8.2 >> >> benchmarking json-validator/Automaton/testEvent >> time 9.221 μs (9.141 μs .. 9.318 μs) >> 0.998 R² (0.996 R² .. 1.000 R²) >> mean 9.163 μs (9.084 μs .. 9.356 μs) >> std dev 399.8 ns (193.0 ns .. 745.4 ns) >> variance introduced by outliers: 54% (severely inflated) >> >> Alloc rate 123,141,635 bytes per MUT second >> >> >> Wow! I suspect your allocations have now vanished. >> > > > Ooo, that's more like it. > > Could you run again using the following to get Criterion's estimate of the > allocations-per-call? > > json-validator-exe --regress allocated:iters +RTS -T >benchmarking json-validator/Automaton/testEvent Here it is, GHC 8.0.2 benchmarking json-validator/Automaton/testEvent time 34.81 μs (33.48 μs .. 36.10 μs) 0.991 R² (0.988 R² .. 0.994 R²) mean 34.04 μs (33.28 μs .. 34.99 μs) std dev 2.828 μs (2.423 μs .. 3.247 μs) allocated: 1.000 R² (1.000 R² .. 1.000 R²) iters 65924.651 (65895.364 .. 65951.510) y -4175.284 (-46736.295 .. 39814.235) variance introduced by outliers: 78% (severely inflated) GHC 8.2 benchmarking json-validator/Automaton/testEvent time 9.021 μs (8.923 μs .. 9.162 μs) 0.998 R² (0.994 R² .. 1.000 R²) mean 8.970 μs (8.905 μs .. 9.232 μs) std dev 341.4 ns (94.90 ns .. 711.7 ns) allocated: 0.973 R² (0.956 R² .. 0.984 R²) iters 343.033 (332.692 .. 354.606) y -7326.339 (-57269.638 .. 47222.231) variance introduced by outliers: 47% (moderately inflated) Cheers, - Ben

3 3

ANN: hledger 1.3
by Simon Michael 01 Jul '17

01 Jul '17

I'm pleased to announce hledger 1.3, released yesterday. Thank you release contributors: Mykola Orliuk, Christian G. Warden, Dmitry Astapov, Justin Le, Joe Horsnell, Nicolas Wavrant, afarrow, Carel Fellinger, flip111, David Reaver, Felix Yan, Nissar Chababy, and Jan Zerebecki. Notable user-visible changes in this release: terminology/UI improvements for the status field, selection/scrolling/movement improvements in hledger-ui, negative amounts shown in red, bugfixes. Full release notes are at http://hledger.org/release-notes#hledger-1.3 The next major release is scheduled for September 30. hledger (http://hledger.org) is a dependable, precise, cross-platform program for tracking money, time, or any other commodity, using double-entry accounting and a simple plain text file format. It is a haskell reimplementation of Ledger, provides command-line, curses and web interfaces, and aims to be a robust, practical tool for daily use. To get started, install the stack tool, eg by downloading from http://haskell-lang.org/get-started. Then install hledger (and optionally the alternate UIs): $ stack install hledger-lib-1.3 hledger-1.3 [hledger-ui-1.3] [hledger-web-1.3] [hledger-api-1.3] (cabal experts can use that instead. See http://hledger.org/download for more install options.) Ensure $HOME/.local/bin is in your $PATH, and try some commands: $ hledger # list commands $ hledger -h # quick help $ hledger --man # man page for the hledger CLI tool $ hledger info journal # info manual for the journal format etc. Our IRC channel is #hledger on Freenode, and you can find out more at http://hledger.org. If you have benefitted from hledger, please give back and make it stronger! Donate using one of the funding links on the home page, give feedback, report bugs, send pull requests, write about it, or help in some other way. Thanks for your support; I hope you enjoy hledger and that it helps you achieve your goals. -Simon

1 0

install haddock only with cabal?
by Evan Laforge 01 Jul '17

01 Jul '17

It's pretty common to wind up with a package installed, but not its haddock. Pretty much any time you install the traditional way via runhaskell Setup.hs you can forget to run haddock, since it doesn't use ~/.cabal/config. And even if you do, it doesn't update the haddock html index. But it seems like cabal install wants to install all targets in the cabal file, which means it wants to reinstall, which is no good for e.g. 'stm'. In fact I can't tell any way to address individual targets (e.g. if I just want to install the executable), and haddock doesn't seem to be a proper target at all, and I can't find any documentation about it. I can run 'haddock' and manually copy dist/doc/html to ~/.cabal/share/doc/$arch/$package/, but shouldn't cabal be able to do that? Also, it looks like regenerateHaddockIndex is hardcoded into the postInstallActions, and there's no way to run it independently, so it seems if you missed documentation on some package, you have to reinstall everything from scratch to fix it. Is there a way to install just haddock without going through all that? And shouldn't cabal-install/bootstrap.sh make the haddock index? Otherwise, you're guaranteed to be missing links for a bunch of fundamental packages. Or maybe it could default to using its (undocumented?) --sandbox flag to install just the binary, and not the various libraries (which are also likely to be missing desired flags, like --enable-profiling, since ~/.cabal/config is not available yet).

1 0

Nice clean code example?
by Han Joosten 01 Jul '17

01 Jul '17

I'd like to showoff some nice Haskell code to a CTO with no experience with FP. I promised to send him a small piece of Haskell so he could get an idea. The code should be easy to read, without obscure looking operators (so sorry, no lens, arrows stuff like that), optionally even do something interesting. Who has the nicest example laying around? (and yes, I need it by yesterday ;-) ) Thanks!

6 6