July 2023 - Haskell-Cafe

Re: [Haskell-cafe] Musings on lists
by Olaf Klinke 14 Jul '23

14 Jul '23

The fact that [a] is a linked list is exploited in Data.List.tails as well as in https://hackage.haskell.org/package/suffixtree where suffixes and internal segments of the tree all use Cons cells of the original list, so the overhead is only in the tree structure itself. In fact, exploiting the location of the internal tree nodes relative to the original list, one could compress the list similarly to the Lempel-Ziv 78 algorithm. This way, bioinformaticians manage to create full-text index structures [*] that are not much larger, or even smaller than, the original text. Olaf [*] Lempel-Ziv 78 creates a suffix tree of the text holding only a subset of all suffixes, namely those starting at a block boundary. This already suffices to find all occurrences of substrings spanning a block boundary.

1 0

Musings on lists
by Todd Wilson 13 Jul '23

13 Jul '23

Deaf Cafe, I'm an educator using Haskell, and I've been telling my students certain stories about Haskell evaluation that I'm now starting to question, so I'm writing for some clarification. I've written before about similar things (e.g., "Basic list exercise" from Mar 16), so it seems my own education on this topic is not yet complete! My apologies if this is too trivial for the Cafe. One story I tell students is that list concatenation, xs ++ ys, ends up "copying" the elements of xs but not the elements of ys, and in particular an expression like xs ++ [a], putting a new element at the end of a list, is particularly expensive, at least compared to x : xs, putting one at the beginning, which seems obvious, right? But here is my question: isn't xs ++ ys just a thunk that, as elements are "requested" from it, produces them first from xs and then, when those run out, defers entirely to ys from that point on? If so, then the elements of xs aren't "copied" any more than the elements of ys are; they are just produced from different places. Even the expression xs ++ [a] isn't problematic in this light: just act like xs, but with one more "card up the sleeve" when you are done. Have I gotten that right? Second, if the above is correct, then if there is a nesting, (xs ++ ys) ++ zs, and we want an element from it, there will be two steps before we can get that element from xs. And this will continue until xs is exhausted, at which point we get new elements in one step from ys, and finally in zero steps from zs. But ++ is associative, and so this list is also xs ++ (ys ++ zs), which requires less work getting the elements from xs. Is this kind of optimization something that is or can be done (automatically)? Thanks for your indulgence, Todd Wilson

6 7

Re: [Haskell-cafe] Musings on lists
by Olaf Klinke 13 Jul '23

13 Jul '23

Perhaps, if the students have been in contact with a language that has explicit pointers (C or C++), let them implement linked lists and concatenation in that procedural language. (An AI will likely also produce a correct implementation nowadays.) The advantage is that one can inspect the values of the pointers to see whether any copying has happened. Then the students easily see that only the spine (structure holding pointers) is re-created, but the memory the list elements point to is never touched. That is an instance of parametricity, I believe. The fact that length (replicate 3 undefined ++ replicate 2 undefined) evaluates to 5 also shows this. Olaf

2 1

[TFP 2024 Call for Papers] 25th International Symposium on Trends in Functional Programming
by Peter Achten 12 Jul '23

12 Jul '23

# TFP 2024 -- Call for Papers (trendsfp.github.io) ## Important Dates Submission deadline: pre-symposium, full papers, Saturday 4 November, 2023 Submission deadline: pre-symposium, draft papers, Wednesday 30 November, 2023 Notification: pre-symposium submissions, Friday 8 December, 2023 TFPIE Workshop: Tuesday 9 January, 2024 TFP Symposium: Wednesday 10 - Friday 12 January, 2024 Submission deadline: post-symposium review, Friday 23 February, 2024 Notification: post-symposium submissions, Friday 5 April, 2024 The Symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming, taking a broad view of current and future trends in the area. It aspires to be a lively environment for presenting the latest research results, and other contributions. This year, TFP will take place in-person at Seton Hall University, in South Orange, NJ in the United States. It is co-located with the Trends in Functional Programming in Education (TFPIE) workshop, which will take on the day before the main symposium. Please be aware that TFP has several submission deadlines. The first, November 4, is for authors that wish to have their full paper reviewed prior to the symposium. Papers that are accepted in this way must also be presented at the symposium. The second, November 30, is for authors that wish to present their work or work-in progress at the symposium first without submitting to the full review process for publication. These authors can then take into account feedback received at the symposium and submit a full article for review by the third deadline, February 23. ## Scope The symposium recognizes that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five article categories. High-quality articles are solicited in any of these categories: * Research Articles: Leading-edge, previously unpublished research work * Position Articles: On what new trends should or should not be * Project Articles: Descriptions of recently started new projects * Evaluation Articles: What lessons can be drawn from a finished project * Overview Articles: Summarizing work with respect to a trendy subject Articles must be original and not simultaneously submitted for publication to any other forum. They may consider any aspect of functional programming: theoretical, implementation-oriented, or experience-oriented. Applications of functional programming techniques to other languages are also within the scope of the symposium. Topics suitable for the symposium include, but are not limited to: * Functional programming and multicore/manycore computing * Functional programming in the cloud * High performance functional computing * Extra-functional (behavioural) properties of functional programs * Dependently typed functional programming * Validation and verification of functional programs * Debugging and profiling for functional languages * Functional programming in different application areas: security, mobility, telecommunications applications, embedded systems, global computing, grids, etc. * Interoperability with imperative programming languages * Novel memory management techniques * Program analysis and transformation techniques * Empirical performance studies * Abstract/virtual machines and compilers for functional languages * (Embedded) domain specific languages * New implementation strategies * Any new emerging trend in the functional programming area If you are in doubt on whether your article is within the scope of TFP, please contact the TFP 2024 program chair, Jason Hemann. ## Best Paper Awards TFP awards two prizes for the best papers each year. First, to reward excellent contributions, TFP awards a prize for the best overall paper accepted for the post-conference formal proceedings. Second, each year TFP also awards a prize for the best student paper. TFP traditionally pays special attention to research students, acknowledging that students are almost by definition part of new subject trends. A student paper is one for which the authors state that the paper is mainly the work of students, the students are the paper’s first authors, and a student would present the paper. In both cases, it is the PC of TFP that awards the prize. In case the best paper happens to be a student paper, then that paper will receive both prizes. ## Instructions to Authors Authors must submit papers to: <https://easychair.org/conferences/?conf=tfp24> Authors of papers have the choice of having their contributions formally reviewed either before or after the Symposium. Further, pre-symposium submissions may either be full (earlier deadline) or draft papers (later deadline). ## Pre-symposium formal review Papers to be formally reviewed before the symposium should be submitted before the early deadline and will receive their reviews and notification of acceptance for both presentation and publication before the symposium. A paper that has been rejected for publication but accepted for presentation may be resubmitted for the post-symposium formal review. ## Post-symposium formal review Draft papers will receive minimal reviews and notification of acceptance for presentation at the symposium. Authors of draft papers will be invited to submit revised papers based on the feedback receive at the symposium. A post-symposium refereeing process will then select a subset of these articles for formal publication. ## Paper categories Draft papers and papers submitted for formal review are submitted as extended abstracts (4 to 10 pages in length) or full papers (20 pages). The submission must clearly indicate which category it belongs to: research, position, project, evaluation, or overview paper. It should also indicate which authors are research students, and whether the main author(s) are students. A draft paper for which all authors are students will receive additional feedback by one of the PC members shortly after the symposium has taken place. ## Format Papers must be written in English, and written using the LNCS style. For more information about formatting please consult the Springer LNCS Guidelines web site: <https://www.springer.com/gp/computer-science/lncs/conference-proceedings-gu…> ## Organizing Committee Jason Hemann PC Chair Seton Hall University, USA Stephen Chang Symposium Chair University of Massachusetts Boston, USA Shajina Anand Local Arrangements Seton Hall University, South Orange, USA

1 0

Re: [Haskell-cafe] Representing a type system in Haskell
by Olaf Klinke 11 Jul '23

11 Jul '23

> So this type system was designed such that I could: > Get a value of a type -> Convert it to lua types -> call lua code > with it -> Convert into my type system -> Type check the result I think you're describing a functor here, at least a commutative square. You're looking at a subset of Haskell, described by the types of your scripting language, whose functions can be mapped to another language (lua in your case). Personally, I would try to avoid defining, parsing and type-checking an entirely new language if there is a chance of embedding it into Haskell. Especially when it must be quite feature-rich as for writing games. Perhaps a quasi-quoter is sufficient? Also have a look at 'zoom' and 'focus' from the lens package. They let you write state transformers that care only about a subset of your huge game state, where the subset is described by a lens. Olaf

1 0

Second Call for Papers: JFP Special Issue on Program Calculation (papers due 1st Dec)
by Graham Hutton 11 Jul '23

11 Jul '23

================================================================== JFP Special Issue on Program Calculation https://tinyurl.com/prog-calc We invite submissions to the Journal of Functional Programming Special Issue on Program Calculation. Notification of intent : 20 October 2023 Submission deadline : 1 December 2023 SCOPE The idea of program calculation, in which programs are derived from specifications using equational reasoning techniques, has been a topic of interest in functional programming since its earliest days. In particular, the approach allows us to systematically discover how programs can be defined, while at the same time obtaining proofs that they are correct. The aim of this special issue is to document advances that have been made in the field of program calculation in recent years. TOPICS Full-length, archival-quality submissions are solicited on all aspects of program calculation and related topics. Specific topics of interest include but are not limited to: - Program derivation and transformation; - Inductive and co-inductive methods; - Recursion and co-recursion schemes; - Categorical and graphical methods; - Tool support and proof assistants; - Efficiency and resource usage; - Functional algorithm design; - Calculation case studies. The special issue will also consider papers on program calculation that are not traditional research papers. This may include pearls, surveys, tutorials or educational papers, which will be judged by the usual JFP standards for such submissions. Papers will be reviewed as regular JFP submissions, and acceptance in the special issue will be based on both JFP's quality standards and relevance to the theme. NOTIFICATION OF INTENT Authors must notify the special issue editors of their intent to submit by 20 October 2023. The notification of intent should be submitted by filling out the following form, which asks for data to help identify suitable reviewers: tinyurl.com/intent-to-submit If you miss the notification of intent deadline, but still wish to submit, please contact the special-issue editors. SUBMISSIONS Papers must be submitted by 1 December 2023. Submissions should be typeset in LaTeX using the JFP style file, and submitted through the JFP Manuscript Central system. Choose "Program Calculation" as the paper type, so it gets assigned to the special issue. Further author instructions are available from: tinyurl.com/JFP-instructions We welcome extended versions of conference or workshop papers. Such submissions must clearly describe the relationship with the initial publication, and must differ sufficiently that the author can assign copyright to Cambridge University Press. Prospective authors are welcome to discuss submissions with the editors to ensure compliance. SPECIAL-ISSUE EDITORS Graham Hutton <graham.hutton(a)nottingham.ac.uk> Nicolas Wu <n.wu(a)imperial.ac.uk> IMPORTANT DATES We anticipate the following schedule: 20 October 2023 : Notification-of-intent deadline 1 December 2023 : Submission deadline 22 March 2024 : First round of reviews 12 July 2024 : Revision deadline 4 October 2024 : Second round of reviews, if applicable 29 November 2024 : Final versions due ================================================================== This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please contact the sender and delete the email and attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham. Email communications with the University of Nottingham may be monitored where permitted by law.

1 0

Call for Talks: Haskell Implementors' Workshop 2023 (deadline extension)
by Ryan Scott 10 Jul '23

10 Jul '23

TL;DR: The submission deadline for the 2023 Haskell Implementors' Workshop has been extended to June 16. ================================== ACM SIGPLAN Haskell Implementors' Workshop https://icfp23.sigplan.org/home/hiw-2023 Seattle, Washington, United States, September 4, 2023 Co-located with ICFP 2023 https://icfp23.sigplan.org/ Important dates --------------- Deadline: July 16, 2023 (AoE) (extended) Notification: August 4, 2023 Workshop: September 4, 2023 The 15th Haskell Implementors' Workshop is to be held alongside ICFP 2023 this year in Seattle. 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 to 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 short lightning 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 2023. 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 are encouraged to attend the workshop -- we need your feedback to keep the Haskell ecosystem thriving. Students working with Haskell are especially 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 can be made via HotCRP at https://icfp-hiw23.hotcrp.com until July 16 (anywhere on earth). We will also have a lightning talks session. These have been very well received in recent years, and we aim to increase the time available to them. Lightning talks should be ~7mins and are scheduled on the day of the workshop. 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 ----------------- * Gergő Érdi (Standard Chartered Bank) * Sebastian Graf (Karlsruhe Institute of Technology) * Wen Kokke (University of Strathclyde) * Ryan Scott (Galois, Inc.) * Rebecca Skinner (Mercury) * Li-yao Xia (University of Edinburgh) Contact ------- * Ryan Scott <ryan.gl.scott at gmail.com>

1 1

Representing a type system in Haskell
by Talha Qamar 10 Jul '23

10 Jul '23

Hello everyone, I'm working on a game engine in Haskell. The thing is, while I want to write the architecture in Haskell, I'm thinking of using something else as the actual scripting language. Long story short, how would I represent a type system in Haskell? I've gotten _something_ together that works a bit like this: ``` data Type = -- ...all possible types data Value = -- ...all possible types again data TypedValue = TypedValye Type Value ``` But I'm concerned if this is the ideal way of doing things, particularly when I get to complex types like structs or tagged unions. Any help would be appreciated. Sent from Proton Mail mobile

2 2

Re: [Haskell-cafe] Representing a type system in Haskell
by Talha Qamar 10 Jul '23

10 Jul '23

This looks perfect! I think I'll spend a couple days looking this over and grokking it. Thanks for your time. Sent from Proton Mail mobile -------- Original Message -------- On Jul 10, 2023, 6:56 PM, Brandon Allbery wrote: > You might look at https://web.cecs.pdx.edu/~mpj/thih/thih.pdf which shows how to implement Haskell's own type system (minus various GHC extensions) in Haskell, and adapt to whatever language you're implementing. On Mon, Jul 10, 2023 at 8:36 AM Talha Qamar via Haskell-Cafe wrote: > > > Hello everyone, I'm working on a game engine in Haskell. The thing is, while I want to write the architecture in Haskell, I'm thinking of using something else as the actual scripting language. > > Long story short, how would I represent a type system in Haskell? I've gotten _something_ together that works a bit like this: > > ``` > data Type = -- ...all possible types > data Value = -- ...all possible types again > data TypedValue = TypedValye Type Value > ``` > But I'm concerned if this is the ideal way of doing things, particularly when I get to complex types like structs or tagged unions. > > Any help would be appreciated. > > Sent from Proton Mail mobile > > > _______________________________________________ > Haskell-Cafe mailing list > To (un)subscribe, modify options or view archives go to: > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > Only members subscribed via the mailman list are allowed to post. -- brandon s allbery kf8nh allbery.b(a)gmail.com

1 0

servant streaming question
by Zoran Bošnjak 10 Jul '23

10 Jul '23

Hi all, I would like to reuse some streaming functions from the turtle package in the context of the servant streaming handler. Relevant references: https://hackage.haskell.org/package/turtle-1.6.1/docs/Turtle-Shell.html https://hackage.haskell.org/package/turtle-1.6.1/docs/Turtle-Prelude.html https://hackage.haskell.org/package/servant-0.20/docs/Servant-Types-SourceT… As a simple example: Turtle.Prelude.ls function represents stream of FilePaths (directory listing of some path) ls :: FilePath -> Shell FilePath Servant streaming is based around SourceT IO a, for example: type ListFiles = "ls" :> StreamGet NewlineFraming PlainText (SourceT IO FilePath) The problem is that the streaming (Shell a) is not exactly the same as servant's (SourceT IO a). But as far as I understand, they both represent "stream of values of type 'a'". My question is: Is a generic conversion function possible? Something like: shellToSource :: forall a. Shell a -> SourceIO a shellToSource = ?? ... such that I could reuse the 'ls' and write a streaming servant handler like this: listFilesHandler :: Handler (SourceIO FilePath) listFilesHandler = pure $ shellToSource $ Turtle.Prelude.ls "somePath" Appreciate any suggestion. regards, Zoran

3 3