- Haskell-Cafe - Haskell.org

Basic list exercise
by Todd Wilson 27 Mar '23

27 Mar '23

Dear Cafe, Here's a basic exercise in list processing: define a function runs :: Ord a => [a] -> [[a]] that breaks up its input list into a list of increasing "runs"; e.g., runs [3,4,5,6,2,3,4,1,2,1] ---> [[3,4,5,6],[2,3,4],[1,2],[1]] A natural solution is the following: runs [] = [] runs (x:xs) = let (ys, zs) = run x xs in (x:ys) : runs zs where run x [] = ([], []) run x (y:ys) = if x <= y then let (us, vs) = run y ys in (y:us, vs) else ([], y:ys) My question: can we do better than this? It seems that this solution is constantly building and breaking apart pairs. (Or is it, when optimized?) Todd Wilson

6 12

Re: [Haskell-cafe] Basic list exercise
by Johannes Waldmann 26 Mar '23

26 Mar '23

Dear Anthony, and Cafe, > ... get sidetracked into all sorts of places you didn't ask about that's the semantics of "-cafe"? I think we agree. In that spirit, allow me to continue with some more tangential remarks. > Haskell community is so off-putting to learners ... I think a language (or other tool) is best for learning if it shows the concepts (that are the subject of the study) most clearly, instead of ignoring, hiding, or sugarcoating them. > So now they have to find out about `Ordering` > and generic compare functions. Yes - that's algebraic data types, higher order functions, generic polymorphism. You don't get Haskell without that. (By definition: functional, strongly typed) Now we might argue whether that's really the concepts that are needed to answer the original question of this thread. In a way, yes - it is about runs in a list, and a run is defined with respect to an order, so it feels natural that the order is an input of the problem. In another way, no (I think that is your point) - it was about efficient implementation, and that could as well be discussed with a monomorphic type and some fixed order. I found the original question interesting, and I thought that authors of the standard library must have asked the same thing, and the resulting library source code seems to confirm what the OP conjectured: there is no easy way to get ascending runs. How bad is it? I made this experiment: import Criterion.Main import qualified Data.List as L main = do let up = [1 .. 10^7 :: Int] down = reverse up print (sum up, sum down) defaultMain [ bench "length up" $ nf length up , bench "length down" $ nf length down , bench "sort up" $ nf L.sort up , bench "sort down" $ nf L.sort down ] and it shows that sorting an ascending list (which just builds the one ascending run) takes three times the work of just traversing it, but sorting a descending list (building one descending run) only two times. Now, I am not too much worried about efficiency of these particular functions (ascending/descending/sort) because I firmly believe that: 1. using a list as a container is wrong (did you mean Data.Sequence?) 2. sorting lists is more wrong (use Data.Set from the start) 3. writing a sort function yourself is most wrong, - of course with the caveat: 0. unless you get this as homework. Then you should absolutely do it (and then learn from it, and then forget the concrete instance). What worries me here much more deeply is https://github.com/haskell/criterion/issues/273 yes, that's another thing the OP did not ask about. - J.W.

1 0

Re: [Haskell-cafe] Basic list exercise
by Anthony Clayden 25 Mar '23

25 Mar '23

>* On 24 Mar 2023, at 18:44, Johannes Waldmann <johannes.waldmann at htwk-leipzig.de <http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe>> wrote: *> >* ... *>* Does the implementation in Data.List do better? *> Data.List's sort is doing a different thing. So I'm not seeing the relevance. Specifically, sort doesn't pay any attention to the incoming list's ordering. >* Since this is about "exercise" - I would expect my students *>* to find that code, so perhaps I'd point them to it right away, *>* and give the task to "understand it" (= argue that it is correct). *>* Arguing about cost seems harder. *> This (ex-)student would wonder why you'd sent me to that code. (Perhaps the lesson is: first read the question.) Why does the correctness (or otherwise) of a sort bear any relation to preserving list sequence and chopping up a list into ascending sublists? AntC

2 2

Re: [Haskell-cafe] Never-ending discussion... Was: Basic list exercise
by Johannes Waldmann 25 Mar '23

25 Mar '23

@Jerzy : I like your plan to use combinators. Then let's remove (visible) recursion completely: map (map fst ) $ groupBy (const snd) $ zip xs ( True : zipWith (<=) xs (tail xs))

2 1

Re: [Haskell-cafe] Basic list exercise
by Johannes Waldmann 24 Mar '23

24 Mar '23

> can we do better than this? Does the implementation in Data.List do better? https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.htm… note that 'ascending' does some trickery there - perhaps exactly to solve the problem you describe? Since this is about "exercise" - I would expect my students to find that code, so perhaps I'd point them to it right away, and give the task to "understand it" (= argue that it is correct). Arguing about cost seems harder. NB: 'descending' is different here, and that's no surprise since lists are asymmetric. We do have a symmetric (and strict) implementation of sequences - how do we sort these? https://hackage.haskell.org/package/containers-0.6.7/docs/src/Data.Sequence… That's not exactly an advertisement for functional programming, as it has "state" written all over the place? But it makes for a nice exercise reading the types. I needed some time to understand that the mouse-over block for an identifier contains _two_ types: the instantiated one (for the use site) and, below that, the general one (from the definition). - J.W.

3 2

ANN: NASA's Ogma 1.0.8 -- with FPrime support
by Ivan Perez 24 Mar '23

24 Mar '23

Hi everyone! I'm thrilled to announce the release of Ogma 1.0.8! Ogma is a NASA tool that facilitates integrating runtime monitors or runtime verification applications into other systems. This is one of the biggest releases of Ogma ever: We can now generate monitors for FPrime [1], a component-based flight software framework used in many NASA missions, including the Ingenuity Mars Helicopter. Since the last release, Ogma also has officially become one of the solutions recommended for monitoring in Space ROS applications [2]. Use cases supported by Ogma also include producing Robot Operating System (ROS 2) packages [3] and NASA Core Flight System (cFS) monitoring applications [4], and generating monitors directly from requirements specified using a structured natural language framework [5]. Ogma leverages existing Haskell work, like the Copilot language [6] (also funded by NASA) and BNFC [7]. For more details, including videos of monitors being generated and flown in simulators, see: https://github.com/nasa/ogma * Releases Ogma is released as a collection of packages in Hackage. The entry point is https://hackage.haskell.org/package/ogma-cli. * Code The github repo is located at: https://github.com/nasa/ogma. * What's coming The next release is planned for May 21st, 2023. Ogma is currently undergoing the qualification process necessary for NASA Class D Software. Apart from the changes required by that process, we also have the following in our roadmap: - Extend ROS 2 monitors with further information about sources of violations. - Add tests to generated code. - Simplify NASA cFS monitor generation process. We hope that you are as excited as we are and that our work demonstrates that, with the right support, Haskell can reach farther than we ever thought possible. Happy Haskelling! Ivan [1] https://github.com/nasa/fprime [2] https://space.ros.org/ [3] https://www.ros.org/ [4] https://github.com/nasa/cFS [5] https://github.com/NASA-SW-VnV/fret [6] https://github.com/Copilot-Language/copilot [7] https://github.com/BNFC/bnfc

1 0

Re: [Haskell-cafe] Basic list exercise
by Anthony Clayden 24 Mar '23

24 Mar '23

On Thu, Mar 16, 2023, 20:33 Todd Wilson <twilson at csufresno.edu <http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe>> wrote: > ... > My question: can we do better than this? It seems that this solution is > constantly building and breaking apart pairs. (Or is it, when optimized?) I don't think we can do better (as others have commented). Laziness is a benefit for peeling off only the beginning(s) of possibly-infinite (sub-)lists. Possibly splitting off the head to call sub-function `run x xs` is also "breaking apart". If you don't like pairs, you can split the returned list itself to give the pairing. Using `l@(y:zs)` as did Viktor might help a little if the compiler is particularly dumb. (GHC isn't.) > runs :: Ord a => [a] -> [[a]] > > runs [] = [] > runs l@[x] = [l] > runs (x: l@(y:zs)) > | x <= y = let (ys:zs) = runs l in ((x:ys) : zs) > | otherwise = ([x]: runs l) This solution appears to achieve the same level of laziness as Viktor's. AntC

2 1

Intend to take over package filelock
by Andreas Abel 23 Mar '23

23 Mar '23

See https://discourse.haskell.org/t/take-over-filelock-package/6037?u=andreasab… : I intend to take over https://hackage.haskell.org/package/filelock. It is a dependency of crucial Haskell infrastructure such as `pantry` and `haskell-server` (via `acid-state`). I needs a fix to work with `unix-2.8` as released with GHC 9.6: - https://github.com/takano-akio/filelock/pull/13 I have been trying to communicate this on github to the maintainer Takano Akio since 2023-02-08. I have tried to contact the maintainer by email 2023-03-12, but have gotten no response. Preferably, the maintainer would come back, but I do not have much hope, their last public github activity was 2021-08-22. -- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel(a)gu.se http://www.cse.chalmers.se/~abela/

1 0

Package takeover: OpenSCAD
by Brecht Serckx 22 Mar '23

22 Mar '23

Hi all, I would like to take over the OpenSCAD[1] package, of which I believe the maintainer is no longer active. The maintainer hasn't replied to my ticket[2] on the issue tracker or to an email to the listed email-address for over a year. On my fork[3] I have implemented multiple bugfixes and features already, and I have some ideas for future improvements. Best regards, Brecht [1] https://hackage.haskell.org/package/OpenSCAD [2] https://chiselapp.com/user/mwm/repository/OpenSCAD/tktview?name=73c74f477b [3] https://github.com/BrechtSerckx/OpenSCAD

4 8

CfP: Haskell Symposium 2023
by Niki Vazou 21 Mar '23

21 Mar '23

=============================================================================== ACM SIGPLAN CALL FOR SUBMISSIONS Haskell Symposium 2023 Seattle, WA, USA Fri 8 -- Sat 9 September, 2023 http://www.haskell.org/haskell-symposium/2023/ ================================================================================ The ACM SIGPLAN Haskell Symposium 2023 will be co-located with the 2023 International Conference on Functional Programming (ICFP). As with last year, Haskell'23 will use a single-track submission process. That is, we will only have the regular track and no early track. The Haskell Symposium presents original research on Haskell, discusses practical experience and future development of the language, and promotes other forms of declarative programming. Topics of interest include: * Language design, with a focus on possible extensions and modifications of Haskell as well as critical discussions of the status quo; * Theory, such as formal semantics of the present language or future extensions, type systems, effects, metatheory, and foundations for program analysis and transformation; * Implementations, including program analysis and transformation, static and dynamic compilation for sequential, parallel, and distributed architectures, memory management, as well as foreign function and component interfaces; * Libraries, that demonstrate new ideas or techniques for functional programming in Haskell; * Tools, such as profilers, tracers, debuggers, preprocessors, and testing tools; * Applications, to scientific and symbolic computing, databases, multimedia, telecommunication, the web, and so forth; * Functional Pearls, being elegant and instructive programming examples; * Experience Reports, to document general practice and experience in education, industry, or other contexts; * Tutorials, to document how to use a particular language feature, programming technique, tool or library within the Haskell ecosystem; * System Demonstrations, based on running software rather than novel research results. Regular papers should explain their research contributions in both general and technical terms, identifying what has been accomplished, explaining why it is significant, and relating it to previous work, and to other languages where appropriate. Experience reports and functional pearls need not necessarily report original academic research results. For example, they may instead report reusable programming idioms, elegant ways to approach a problem, or practical experience that will be useful to other users, implementers, or researchers. The key criterion for such a paper is that it makes a contribution from which other Haskellers can benefit. It is not enough simply to describe a standard solution to a standard programming problem, or report on experience where you used Haskell in the standard way and achieved the result you were expecting. Like an experience report and a functional pearl, tutorials should make a contribution from which other Haskellers can benefit. What distinguishes a tutorial is that its focus is on explaining an aspect of the Haskell language and/or ecosystem in a way that is generally useful to a Haskell audience. Tutorials for many such topics can be found online; the distinction here is that by writing it up for formal review it will be vetted by experts and formally published. System demonstrations should summarize the system capabilities that would be demonstrated. The proposals will be judged on whether the ensuing session is likely to be important and interesting to the Haskell community at large, whether on grounds academic or industrial, theoretical or practical, technical, social or artistic. Please contact the program chair with any questions about the relevance of a proposal. If your contribution is not a research paper, please mark the title of your experience report, functional pearl, tutorial or system demonstration as such, by supplying a subtitle (Experience Report, Functional Pearl, Tutorial Paper, System Demonstration). Submission Details ================== Formatting ---------- Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines. Authors should use the `acmart` format, with the `sigplan` sub-format for ACM proceedings. For details, see: http://www.sigplan.org/Resources/Author/#acmart-format It is recommended to use the `review` option when submitting a paper; this option enables line numbers for easy reference in reviews. Functional pearls, experience reports, tutorials and demo proposals should be labelled clearly as such. Lightweight Double-blind Reviewing ---------------------------------- Haskell Symposium 2023 will use a lightweight double-blind reviewing process. To facilitate this, submitted papers must adhere to two rules: 1. Author names and institutions must be omitted, and 2. References to authors' own related work should be in the third person (e.g., not "We build on our previous work" but rather "We build on the work of "). The purpose of this process is to help the reviewers come to an initial judgement about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult (e.g., important background references should not be omitted or anonymised). In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For instance, authors may post drafts of their papers on the web or give talks on their research ideas. A reviewer will learn the identity of the author(s) of a paper after a review is submitted. Page Limits ----------- The length of submissions should not exceed the following limits: Regular paper: 12 pages Functional pearl: 12 pages Tutorial: 12 pages Experience report: 6 pages Demo proposal: 2 pages There is no requirement that all pages are used. For example, a functional pearl may be much shorter than 12 pages. In all cases, the list of references is not counted against these page limits. Deadlines --------- Paper submission: 1 June 2023 (Thu) Notification: 4 July 2023 (Tue) Camera ready: 18 July 2023 (Tue) Deadlines are anywhere on Earth. Submission ---------- Submissions must adhere to SIGPLAN's republication policy (http://sigplan.org/Resources/Policies/Republication/) and authors should be aware of ACM's policies on plagiarism (https://www.acm.org/publications/policies/plagiarism) Program Committee members are allowed to submit papers, but their papers will be held to a higher standard. The paper submission deadline and length limitations are firm. There will be no extensions, and papers violating the length limitations will be summarily rejected. Papers should be submitted through HotCRP at: https://haskell23.hotcrp.com/ Improved versions of a paper may be submitted at any point before the submission deadline using the same web interface. Supplementary material: Authors have the option to attach supplementary material to a submission, on the understanding that reviewers may choose not to look at it. This supplementary material should not be submitted as part of the main document; instead, it should be uploaded as a separate PDF document or tarball. Supplementary material should be uploaded at submission time, not by providing a URL in the paper that points to an external repository. Authors can distinguish between anonymised and non-anonymised supplementary material. Anonymised supplementary material will be visible to reviewers immediately; non-anonymised supplementary material will be revealed to reviewers only after they have submitted their review of the paper and learned the identity of the author(s). Resubmitted Papers: authors who submit a revised version of a paper that has previously been rejected by another conference have the option to attach an annotated copy of the reviews of their previous submission(s), explaining how they have addressed these previous reviews in the present submission. If a reviewer identifies him/herself as a reviewer of this previous submission and wishes to see how his/her comments have been addressed, the conference chair will communicate to this reviewer the annotated copy of his/her previous review. Otherwise, no reviewer will read the annotated copies of the previous reviews. Proceedings =========== Accepted papers will be included in the ACM Digital Library. Their authors will be required to choose one of the following options: - Author retains copyright of the work and grants ACM a non-exclusive permission-to-publish license (and, optionally, licenses the work with a Creative Commons license); - Author retains copyright of the work and grants ACM an exclusive permission-to-publish license; - Author transfers copyright of the work to ACM. For more information, please see ACM Copyright Policy (http://www.acm.org/publications/policies/copyright-policy) and ACM Author Rights (http://authors.acm.org/main.html) Accepted proposals for system demonstrations will be posted on the symposium website but not formally published in the proceedings. Publication date: The official publication date of accepted papers is the date the proceedings are made available in the ACM Digital Library. This date may be up to two weeks prior to the first day of the conference. The official publication date affects the deadline for any patent filings related to published work. Artefacts ========= Authors are encouraged to make auxiliary material (artefacts like source code, test data, etc.) available with their paper. Authors can opt to have these artefacts published alongside their paper in the ACM Digital Library (copyright of artefacts remains with the authors). Artefacts must be included as part of their submission to HotCRP and should consist of a .zip file containing the artefact materials, a README explaining the contents of the artefact and how it should be used, and a LICENSE file. If an accepted paper's artefacts are made permanently available for retrieval in a publicly accessible archival repository like the ACM Digital Library, that paper qualifies for an Artefact badge (https://www.acm.org/publications/policies/artifact-review-badging) Program Committee ================= Alexander Green Standard Chartered, UK David Thrane Christiansen The Haskell Foundation, Denmark Edsko de Vries Well-Typed LLP, Netherlands Exequiel Rivas Tallinn University of Technology Facundo DomÃnguez Tweag Florian Zuleger TU Vienna, Austria Graham Hutton University of Nottingham, UK Jasper Van der Jeugt Snyk, Switzerland Jennifer Paykin Intel, USA Jesper Cockx Delft University of Technology, Netherlands Jose Nuno Oliveira University of Minho & INESC TEC, Portugal Michael Sperber Active Group GmbH, Germany Michel Steuwer University of Edinburgh, UK Niki Vazou (chair) IMDEA Software Institute, Spain Rumyana Neykova Brunel University London, UK Trevor L. McDonell (co-chair) Utrecht University, Netherlands Ugo Dal Lago University of Bologna, Italy & INRIA, France Wen Kokke University of Edinburgh, UK Leonidas Lampropoulos University of Maryland, College Park, USA If you have questions, please contact the chairs at niki.vazou(a)imdea.org andt.l.mcdonell(a)uu.nl. ================================================================================

1 0