- Haskell-Cafe - Haskell.org

lost the ability to provide haddocks for hackage
by Olaf Klinke 17 Jul '21

17 Jul '21

Dear Cafe, it seems I lost the ability to provide documentation for my hackage packages. While it is known that hackage sometimes fails to build documentation, the upload page [1] provides a guide to build and upload documentation. Stack does not have this ability yet [2] but it has the convenient option --no-haddock-deps that I can use as last resort when a dependency fails to build its Haddocks. I'd rather present documentation with broken links than no documentation at all. Cabal does not seem to provide such an option, while adding --keep-going and/or --enable-per-component to the suggested cabal command in [1] still aborts when one dependency fails to build. Is there something I've missed? If there is a way to build hackage-documentation in presence of haddock errors in dependencies, please someone update [1] and [3]. Can [4] be used to circumvent my problem? Perhaps add a guide to tweak the links generated by stack haddock to be hackage-compatible, as suggested in [2]? Strangely, the dependency package my cabal v2-haddock command fails on does have documentation on hackage. Would it be possible to pull these docs from hackage and use as a drop-in replacement? Thanks, Olaf [1] https://hackage.haskell.org/upload [2] https://github.com/commercialhaskell/stack/issues/737 [3] https://cabal.readthedocs.io/en/3.4/cabal-commands.html#cabal-v2-haddock [4] http://neilmitchell.blogspot.co.uk/2014/10/fixing-haddock-docs-on-hackage.h…

2 1

Compiled program running (extremely) slower than interpreted equivalent (no results produced)
by CASANOVA Juan 16 Jul '21

16 Jul '21

Hello, I have a (fairly complicated) Haskell program. The main aspect I believe is relevant about it is that it produces an infinite output (something like an infinite list evaluated lazily, except I use my own data structures with better properties). What I want is to see how fast the elements in the "list" are produced and check that they are correct, without reaching any particular point. Producing even just a couple elements of this list takes A LOT of computations. I normally run everything interpreted, and this works fine. However, it is a tad too slow and I wanted to profile it, for which I need to compile it. Here is my typical way to run it interpreted: * stack ghci +RTS -M500m -RTS * :load CESQResolverEval.hs * main This produces 4-5 outputs within a few seconds. When I try to compile it: * stack ghc --rts-options "-M500m" CESQResolverEval.hs * stack exec ./CESQResolverEval This dies. Moreover, if I run without the RTS options and/or let it run for a while, it completely kills my computer and I have to restart it. I initially thought it may be a thing with output flushing but: * I added a stdout flush after each individual element of the "list", and it changes nothing. * I even tried changing what main does so that it stops after the first result. This works when interpreted (takes less than a second), but still the program produces nothing and kills my CPU when compiled. Maybe relevant is that loading my program into GHCi takes about 30 seconds. The only thing I've been able to find online is this: https://www.reddit.com/r/haskell/comments/3hu3sd/how_is_it_possible_that_co… But that seems to be about complicated flags and their implications. As you can see, my flags are fairly simple. Anyone has any idea what this could be about, or how to avoid it? My purpose is to profile the program to see where most of the time is being spent, but I cannot do that without compiling it, and if the compiled code is running much slower than the interpreted code, then it seems absurd to even try to profile this (it must not be doing the same that the interpreted code is doing?). Thanks in advance, Juan. The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th' ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.

3 3

Lazy Probabilistic Programming System in Haskell
by Benjamin Redelings 16 Jul '21

16 Jul '21

Hi, My program BAli-Phy implements probabilistic programming with models written as Haskell programs. http://www.bali-phy.org/models.php Unlike [1], models are *lazy* in the sense that you can generate an infinite list of random variables, as long as you only access a finite number. I am also using MCMC for inference, not particle filters. BAli-Phy implements a Haskell interpreter in C++ that records execution traces of Haskell programs. When a random variable is modified (during MCMC), the parts of the execution trace that depend on the changed variables are invalidated and recomputed. This saves work by not recomputing the probability of the new state from scratch. Here's a example of a model written in Haskell: https://github.com/bredelings/BAli-Phy/blob/master/tests/prob_prog/regressi… WARNING: There are lots sharp edges. First and foremost, no type system! (yet) -BenRI [1] Practical probabilistic programming with monads, https://dl.acm.org/doi/10.1145/2804302.2804317

1 0

Haskell books index with RSS
by Travis Cardwell 14 Jul '21

14 Jul '21

Dear Café, I have often wished that I could subscribe to RSS feeds that notify me when new books are published about a certain topic or by a certain author. I recently implemented the idea in the article system of my personal website and created an index of Haskell books. https://www.extrema.is/articles/haskell-books The index provides a simple UI for browsing by tag, and each book page has basic information and links. By subscribing to the following RSS feed, you get a notification when a new book is added to the index. https://www.extrema.is/articles/tag/index:haskell-books.rss This is a humble first implementation, but I am posting here in case others find it useful. Regards, Travis

3 4

Re: [Haskell-cafe] Check a lack of a constraint?
by Olaf Klinke 14 Jul '21

14 Jul '21

> > Hello cafe, > > Is it possible in Haskell to check a lack of a certain constraint? > > For example, > > ``` > foo :: C => a > foo = undefined > > ``` > > Here `foo` can only be compiled if called with C satisfied. How do I write the > opposite, so that `foo` is only possible to use when C is not satisfied? > > With best regards. Indeed I found myself wanting this, too. Such a feature might reduce the amount of overlapping instances, but of course it bears the danger that others pointed out. For example, suppose you have a type T :: (* -> *) and the library author of T already defined an instance instance C a => C (T a). Now suppose you have a concrete type A which you know can never have a (lawful) C A instance, but you can define an instance C (T A). The latter would be formally overlapping with the former, even if you know that the former will never be implemented. Thus, instead of local non-satisfiability, a token for the proof that an instance can not exist might be more useful (and more safe). This would correspond to case 2 in Sylvain Henry's GHC proposal. I have no idea, however, how such a proof can be presented [*] in a way that can not be circumvented by a third author and lead to unsoundness. As a concrete example, I defined an instance MonadParsec (StateT String Maybe) which makes a wonderfully fast parser that you can swap in for a Megaparsec parser, but it is overlapping because of MonadParsec Maybe => MonadParsec (StateT s Maybe) although it is absurd to try to make Maybe an instance of MonadParsec. Another example: Think about why the mtl library has an instance MonadFoo m => MonadFoo (BarT m) for every pair (Foo,Bar) of transformers. (And there are quadratically many of these!) It is precisely because a catch-all instance like (MonadTrans t, MonadFoo m) => MonadFoo (t m) will be overlapping as long as we can't rule out MonadFoo (t m) by other means. Olaf [*] The logically natural way would be to have a Void constraint, so that we can say: MonadParsec Maybe => Void

1 0

Check a lack of a constraint?
by Lana Black 13 Jul '21

13 Jul '21

Hello cafe, Is it possible in Haskell to check a lack of a certain constraint? For example, ``` foo :: C => a foo = undefined ``` Here `foo` can only be compiled if called with C satisfied. How do I write the opposite, so that `foo` is only possible to use when C is not satisfied? With best regards.

5 9

What can I use for a weighted graph? I thought Data.Graph would work but I see no provision for edge weights?
by Casey Hawthorne 12 Jul '21

12 Jul '21

Hi What can I use for a weighted graph? I thought Data.Graph would work but I see no provision for edge weights?

2 3

Re: [Haskell-cafe] How to do reversible parsing?
by Johannes Waldmann 11 Jul '21

11 Jul '21

Rendell and Ostermann, Invertible syntax descriptions, Haskell Symposium '10 https://doi.org/10.1145/1863523.1863525 https://hackage.haskell.org/package/invertible-syntax For the general background, see, e.g., Grohne and Voigtländer 2017 Formalizing semantic bidirectionalization ... https://doi.org/10.1016/j.jlamp.2016.04.002 And there's a workshop series on Bidirectional Transformations (from 2012 onwards) - J.

3 9

Invitation: Virtual Haskell Cohack, July 10 (Saturday)
by Chris Smith 10 Jul '21

10 Jul '21

Hello everyone, I'd like to formally invite you to the Virtual Haskell Cohack, which will be running monthly beginning Saturday, July 10. Please review times and RSVP at https://www.meetup.com/NY-Haskell/events/279067287/ so that I know how many people are coming. I would need to upgrade my Zoom account if we exceed 100 people, but that would be amazing. Please make that happen! This is an event for the Haskell community to get together and work on collaborative projects. This could mean: - Teaching or learning Haskell - Writing code or docs on your favorite project and introducing it to others - Learning about other people's projects and getting some mentorship to contribute. - Pair programming on programming challenges like Advent of Code or Project Euler. - Just hanging out and geeking out talking category theory or GHC profiling techniques or whatever. The full agenda is listed at the link above, but it also includes lightning talks, which you can propose when you RSVP or just wait and volunteer to give one at the event. If you want to be sure you make it on the list, mention that you'd like to give a talk in your RSVP and you'll get priority on the signup list. Haskell-adjacent technologies are also welcome, so if you'd like to come hack in Elm, Idris, Agda, Coq, Ocaml, or whatever, you are welcome. The only rule we have is to be kind and welcoming to others. Thanks, and hope to see you there.

1 2

[ANN] parser-unbiased-choice-monad-embedding - the best parsing library; it is based on arrows (was: Pearl! I just proved theorem about impossibility of monad transformer for parsing with (1) unbiased choice and (2) ambiguity checking before running embedded monadic action (also, I THREAT I will create another parsing lib))
by Askar Safin 10 Jul '21

10 Jul '21

Hi. I announce my parsing library https://hackage.haskell.org/package/parser-unbiased-choice-monad-embedding . I think it is best parsing library, and you should always use it instead of other solutions. I will tell you why. You may check comparison table: https://paste.debian.net/1203863/ (if you don't understand the table, don't worry; come back to the table after reading this mail). My library is solution to problem described in this e-mail thread, so read it for motivation: https://mail.haskell.org/pipermail/haskell-cafe/2021-June/134094.html . Now let me describe my solution in detail. I will distinguish parser errors (i. e. "no parse" or "ambiguous parse") and semantic errors (i. e. "division by zero", "undefined identifier", "type mismatch", etc). So, now I will show you parser with unbiased choice, which allows monad embedding. As a very good introduction to arrows I recommend this: https://ocharles.org.uk/guest-posts/2014-12-21-arrows.html . We start from classic parser with this type: newtype ParserClassic t a = ParserClassic ([t] -> [(a, [t])]) You can make it be instance of Functor, Applicative, Monad and Alternative. This type is similar to ReadS from base ( https://hackage.haskell.org/package/base-4.15.0.0/docs/Text-ParserCombinato… ) and to "type Parser = StateT String []" from example here: https://hackage.haskell.org/package/transformers-0.5.5.0/docs/Control-Monad… . I will not give more information, feel free to find it in internet. Now let's replace "a" with Kleisli arrow "b -> m c". We will get this: newtype Parser1 t m b c = Parser1 ([t] -> [(b -> m c, [t])]) Here is resulting parsing library and example: https://godbolt.org/z/qsrdKefjT (backup: https://paste.debian.net/1203861/ ). We can use this parser in Applicative style. And when we need to lift something to embedded monad, we resort to Arrow style. I didn't test this code much. Parser1 cannot be Monad (I proved this in previous letters). At this point someone may ask: why we need arrows? Can we achieve same effect using Applicative only? Yes, we can. Here is result: https://godbolt.org/z/ocY3csWjs (backup: https://paste.debian.net/1203862/ ), I will call such method "anti-arrow". But we have two problems here: first, I think this method makes parser code uglier. Second, this method is limited, and I will show you why later. Okey, now back to arrows. Still, we have this problems (I'm about our arrow code): - Handling left-recursive grammars is tricky (it is possible, but not as simple as right-recursive ones) - Parsing errors (as opposed to semantic error messages) are not great. I. e. if there is no valid parses, we don't get any additional information, i. e. we don't know which token caused error - We don't track locations, so semantic errors are not great, too (i. e. we want to have location info to embed it into semantic error messages) - I suspect this parsing library will have very bad speed, possibly O(exp(input size)) So, let's combine our ideas with package Earley ( https://hackage.haskell.org/package/Earley ). Earley has type "Prod r e t a". Let's replace "a" with Kleisli arrow "b -> m c". Also let's wrap this Kleisli arrow to "L" from srcloc ( https://hackage.haskell.org/package/srcloc ) to get location info. Also, we wrap "t" to "L", too. Thus we get this type: newtype ArrowProd r e t m b c = ArrowProd (Prod r e (L t) (L (b -> m c))) Here is resulting library with example: https://hackage.haskell.org/package/parser-unbiased-choice-monad-embedding . (I didn't test much.) (I recommend to read docs to Earley first.) (My library is designed to be used with some external lexer, lexer-applicative is recommended.) The example also uses lexer-applicative, because lexer-applicative automatically wraps tokens into "L". So, what we got? We solved original goals, i. e.: - We have combinator parser with unbiased choice. Unfortunately, it is not monadic, but it is Applicative and Arrow - We can embed monad, for example, to handle semantic errors - We can test parsing errors before executing embedded monadic action Additionally we solved 4 remaining problems mentioned above, i. e.: - Handling left-recursive grammars is as simple as right-recursive ones (thanks to Earley's RecursiveDo) - Parsing errors are ok - We track locations and we can embed them into semantic errors - We have relatively good speed thanks to Earley What else? We can test grammar for ambiguity using https://hackage.haskell.org/package/Earley-0.13.0.1/docs/Text-Earley.html#v… (I didn't wrap this function, but this can easily be done). Personally I think that my parsing library is simply best. :) And that one should always use it instead of all others. Why I think this? Because: - We all know that CFG is better than PEG, i. e. unbiased choice is better that biased - I don't want to merely produce AST, I want to process information while I parse, and this processing will uncover some semantic errors - So I want unbiased choice with handling semantic errors - The only existing solution, which can do this is my library (and also "happy") - But "happy" doesn't automatically track locations (as well as I know it tracks lines, but not columns) - So the best parsing solution is my library :) My library has another advantage over happy: by extensive use of Alternative's "many" (and arrow banana brackets) you can write things, which are impossible to write in happy. Consider this artificial example (subset of Pascal): --- var a: integer; b: integer; begin a := b + c; end. --- This is its parser, which uses my library (completely untested): --- arrowRule (proc () -> do { sym TVar -< (); declated <- many (ident <* sym TColon <* sym TInteger <* sym TSemicolon) -< (); sym TBegin -< (); -- Banana brackets (|many (do { x <- ident -< (); lift -< when (x `notElem` declated) $ Left "Undeclated identifier"; sym TAssign -< (); -- My library doesn't have "sepBy", but it can be easily created (|sepBy (do { y <- ident -< (); lift -< when (y `notElem` declated) $ Left "Undeclated identifier"; returnA -< (); })|) [TPlus]; sym TSemicolon -< (); returnA -< (); |); sym TEnd -< (); sym TDot -< (); returnA -< (); }) --- This is impossible to write similar code using "happy" with similar ergonomics, because in happy we would not have access to "declared" inside production for sum. The only way we can access "declared" is using state monad (for example, StateT) and put this "declared" into this state monad. But in my library you don't have to use any StateT! Now let me say why mentioned "anti-arrow" style is not enough. Let's try to rewrite this Pascal example using anti-arrow style: --- antiArrowLift $ do { -- ApplicativeDo sym TVar; declated <- many (ident <* sym TColon <* sym TInteger <* sym TSemicolon); sym TBegin; many $ antiArrowLift $ do { x <- ident; sym TAssign; -- My library doesn't have "sepBy", but it can be easily created sepBy [TPlus] $ antiArrowLift $ do { y <- ident; pure $ when (y `notElem` declated) $ Left "Undeclated identifier"; -- Oops }; sym TSemicolon; pure $ when (x `notElem` declated) $ Left "Undeclated identifier"; -- Oops }; sym TEnd; sym TDot; pure (); } --- Looks good. But there is a huge problem here: look at lines marked as "Oops". They refer to "declared", but they cannot refer to it, because outer "do" is ApplicativeDo. So, yes, merely Applicative is not enough. Does my library have disadvantages? Of course, it has! - It is not monadic - It cannot statically check that grammar is element of LR(1) set (as well as I understand, happy can do this) - My library has relatively good speed asymptotic (same as Earley), but it is still not fastest - My library will freeze on infinitely ambiguous grammars. Attempting to check such grammar for ambiguity using Earley's "upTo" will cause freezing, too. See also: https://github.com/ollef/Earley/issues/54 - My library is based on unbiased choice and CFG (as opposed to biased choice and PEG). I consider this as advantage, but my library will not go if you want to parse language defined by some PEG My library is unfinished. The following things are needed: - We need combinator similar to Alternative's "many", but every item should have access to already parsed part of list. Such combinator should be made to be used by banana brackets - We need combinators similar to parsec's chainl and chainr (my library already supports left and right recursion thanks to Earley, but still such combinators would be useful) - Already mentioned "sepBy" - I didn't wrap all Earley functionality, for example, <?> is left unwrapped I don't have motivation for fix this things, because I decided to switch to Rust as my main language. Final notes - It is quite possible that I actually need attribute grammars or syntax-directed translation. I didn't explore this - I suspect that my parser is arrow transformer (whatever this means) Side note: I really want some pastebin for reproducible shell scripts (possibly dockerfiles), do you know such? Answer me if you have any questions. == Askar Safin http://safinaskar.com https://sr.ht/~safinaskar https://github.com/safinaskar

2 3