- Haskell-Cafe - Haskell.org

Is the Haskell list comprehension just a Cartesian product machine?
by Galaxy Being 08 Dec '21

08 Dec '21

If I were a teacher of high-schoolers wanting to add some theory to Haskell could I explain Haskell list comprehensions as basically just a Cartesian/cross product machine? Would this be accurate? And then the combinatorics product rule also seems at play here. I would appreciate any theoretical explanation of what a list comprehension is about. ⨽ Lawrence Bottorff Grand Marais, MN, USA borgauf(a)gmail.com

3 2

with -XOverloadedStrings, when is the implied fromString floated out?
by Johannes Waldmann 07 Dec '21

07 Dec '21

Dear Cafe, with OverloadedStrings, the compiler inserts `fromString` applications at String literals. I was wondering - are these floated out? {-# language OverloadedStrings #-} import Data.String import Debug.Trace data Foo = Foo deriving Show instance IsString Foo where fromString "Foo" = trace "**fromString**" Foo main = let { f Foo = "Foo" :: Foo; g _ = "Foo" :: Foo } in print $ map (f . g) [0..1] With ghc -O1, I get **fromString** [Foo,Foo] That's good - not just floated out, but also interned (? - both "Foo" are really the same, just one call) With ghc -00, and in ghci, I get **fromString** **fromString** **fromString** **fromString** [Foo,Foo] no floating here. Is there a way to get this floated in ghci? The background of my question is that overloaded strings, and ghci, are heavily used in Tidal Cycles https://hackage.haskell.org/package/tidal I guess it's mostly fine, because it's rare (in live coding performance) that application code contains function definitions. - J.

2 1

Re: [Haskell-cafe] Endo a, endomorphisms
by Olaf Klinke 06 Dec '21

06 Dec '21

> it might be possible that the intention was > to state that function composition is an endomorphism of the set of endofunctions (Endo a). > So again, given that the context is the Data.Monoid library, it seems much more appropriate to > say that Endo a forms a monoid of endofunctions under composition. As the examples I presented > above show, even stating that function composition is an endomorphism of Endo a (endofunctions) > seems incorrect. > What you write does not even type-check: Composition is an operation (b -> c) -> (a -> b) -> (a -> c) so it is a binary operation. Hence it cannot form an endomorphism, because you can't unify the above type with (x -> x). No ambiguity here. > opening :: String -> String > opening = ("Hello, " ++) > > closing :: String -> String > > closing = (++ "!") > > eo = Endo opening > > ec = Endo closing This is a manifestation of the fact that every monoid has a function a -> Endo a given by \a -> Endo (mappend a) This is indeed a monoid homomorphism (by virtue of associativity). Your 'eo' is of this kind. But then you mixed in another monoid homomorphism, namely \a -> Endo (flip mappend a) where your 'ec' is of this kind. It is not true in general that you can mix these two monoid homomorphisms. Only for commutative monoids the above two homomorphisms are identical. And (String,++) is not commutative. Indeed we could not give a Monoid instance to naked (a -> a) because it overlaps with the Semigroup instance you mention. But historically this is not the reason why the Endo newtype was introduced. One could argue that the Semigroup instance should also be on a newtype. I'd be in favour of such a proposal. Olaf P.S.: Let S be a functor (a signature) and a be an S-algebra, that is, there is a structure map alpha :: S a -> a. Then for any r, the type (r -> a) is an S-algebra, too. Indeed, alpha' :: Functor s => (s a -> a) -> s (r -> a) -> r -> a alpha' alpha sf = \r -> alpha (fmap ($x) sf) This is what makes the ReaderT transformer work. For Semigroup, the signature is S a = (a,a) and alpha = uncurry (<>).

1 0

Endo a, endomorphisms
by Adrian 05 Dec '21

05 Dec '21

In the Data.Monoid library there is a monoid type instance for Endo a that is described in the following manner: > The monoid of endomorphisms under composition. I understand how it is a monoid of endofunctions, but am unclear on how it is a monoid of endomorphisms. In the pattern: "forms a monoid of X under Y", X refers to the set and Y to the associative binary operation. So it seems that X in this case is the set of endofunctions. However, it might be possible that the intention was to state that function composition is an endomorphism of the set of endofunctions (Endo a). However even this statement seems difficult to prove in Haskell: opening :: String -> String opening = ("Hello, " ++) closing :: String -> String closing = (++ "!") eo = Endo opening ec = Endo closing appEndo (Endo $ opening <> closing) "Haskell" -- "Hello, HaskellHaskell!" (appEndo eo <> appEndo ec) "Haskell" -- "Hello, HaskellHaskell!" appEndo (eo <> ec) "Haskell -- "Hello, Haskell!" (opening <> closing) "Haskell" -- "Hello, HaskellHaskell!" (opening . closing) "Haskell" -- "Hello, Haskell!" I believe the reason for this behavior is that the fallback for mappend for the general endofunction with type a -> b is found in the Base library as: -- @since 4.9.0.0 instance Semigroup b => Semigroup (a -> b) where f <> g = \x -> f x <> g x

3 7

Output order of Data.List.permutations?
by Johannes Waldmann 05 Dec '21

05 Dec '21

Dear Cafe - what is the ordering of the output of https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.OldList.htm… - and why is it not lexicographic? E.g., *Main> last $ L.permutations [1..8] [5,3,6,2,7,1,8,4] note: [5,_,6,_,7,_,8,_] and [_,3,_,2,_,1,_,4] indeed, an auxiliary function is called "interleave". Data.List.permutations appeared in base-4.0.0.0 (ghc-6.10.1, 2008) https://downloads.haskell.org/~ghc/6.10.1/docs/html/users_guide/release-6-1… What is the source of the algorithm? Is it any of the algorithms in Knuth AOCP 4A(I) 7.2.1.2? Hard to tell - as they are given in an imperative style. The implementation *is* fast, e.g., L.sort . L.permutations seems better than a naive lexicographic enumeration lp1 [] = [[]] lp1 xs = do (ys, z:zs) <- zip (L.inits xs) (L.tails xs) (z:) <$> lp1 (ys <> zs) (un-scientifically measured with :set +s) Here, clearly, L.inits and "<>" are bad. NB - I was looking in to this because of https://www.mathekalender.de/wp/calendar/challenges/challenge-01/ Yes I know that can be solved without enumeration. - J.

1 2

ANN: NASA's ogma
by Ivan Perez 03 Dec '21

03 Dec '21

Dear café We are thrilled to announce the release of Ogma, a new open-source NASA tool, written in Haskell, to generate hard-realtime C runtime monitoring applications from high-level specifications. Ogma takes the output of existing tools, like NASA's requirements elicitation tool FRET [2], and produces monitors in Copilot [3], a runtime verification language that can be compiled to hard-realtime C99. Ogma is also able to produce monitoring applications for NASA's Core Flight System (cFS), which can be compiled alongside existing applications to flag requirement violations. On the website you will see several videos, including one with a FRET requirement being monitored inside the XPlane flight simulator by taking the code generated by Ogma and making it accessible to the simualtor via a custom on-screen plugin. This is research-only software (Class E) and it has not been certified for use in aircraft or UAVs. We are currently using it for upcoming experiments at NASA Langley. We'd like to also take this opportunity to publicly thank the team that creates BNFC, for their tool, their response to technical questions during the development of ogma, and for accommodations made to help us speed up our release process. If you have any issues, feel free to open a ticket in the github repo directly. Happy haskelling, [1] https://github.com/NASA/ogma [2] https://github.com/NASA-SW-VnV/fret [3] https://github.com/Copilot-Language/copilot

1 0

Why and How the External STG Interpreter is Useful (Online presentation, Dec 2, Thursday, 17:00 UTC)
by Csaba Hruska 03 Dec '21

03 Dec '21

Hello, Today I'll do a presentation about the external stg interpreter. If you are interested please join and ask questions. https://skillsmatter.com/meetups/13654-haskell-stg-interp Regards, Csaba Hruska Abstract: Haskell: Why and How the External STG Interpreter is Useful The external STG interpreter is a from scratch implementation of the STG machine in Haskell. Currently it supports almost all GHC primops and RTS features. It can run real world Haskell programs that were compiled with GHC Whole Program Compiler (GHC-WPC). GHC-WPC is a GHC fork that exports the whole program STG IR. The external STG interpreter is an excellent tool to study the runtime behaviour of Haskell programs, i.e. it can run/interpret GHC or Pandoc. The implementation of the interpreter is in plain simple Haskell, so it makes compiler backend and tooling development approachable for everyone. It already has a programmable debugger which supports step-by-step evaluation, breakpoints and execution region based inspection. It also can export the whole program memory state and call-graphs to files for further investigation. These features make it easy to find a memory leak or to identify a performance bottleneck in a large real world Haskell application. https://github.com/grin-compiler/ghc-whole-program-compiler-project

1 1

Re: [Haskell-cafe] Breaking change to Eq accepted by Core Libraries Committee
by Olaf Klinke 03 Dec '21

03 Dec '21

For what it's worth, one of the examples listed in the issue where (/=) is not simply the negation of (==) is violating the laws. It is the one in https://hackage.haskell.org/package/numbers-3000.2.0.2/docs/Data-Number-Int… That module defines two intervals to be equal if their bounds are equal, but to be unequal only if they are disjoint. In my eyes this speaks for the proposal, because the library author would have been unable to write the broken instance. (And I did look at the proposal some time ago, whence I feel it was indeed discussed or at least mentioned on this list before.) Olaf

6 7

Trends in Functional Programming in Education 2022 2nd call for submissions
by Elena Machkasova 03 Dec '21

03 Dec '21

TFPIE 2022 Call for papers https://wiki.tfpie.science.ru.nl/TFPIE2022 (February 11th 2022, Krakow, Poland co-located with TFP 2022 and Lambda Days) TFPIE 2022 welcomes submissions describing techniques used in the classroom, tools used in and/or developed for the classroom and any creative use of functional programming (FP) to aid education in or outside Computer Science. Topics of interest include, but are not limited to: FP and beginning CS students FP and Computational Thinking FP and Artificial Intelligence FP in Robotics FP and Music Advanced FP for undergraduates FP in graduate education Engaging students in research using FP FP in Programming Languages FP in the high school curriculum FP as a stepping stone to other CS topics FP and Philosophy The pedagogy of teaching FP FP and e-learning: MOOCs, automated assessment etc. Best Lectures - more details below In addition to papers, we are requesting best lecture presentations. What's your best lecture topic in an FP related course? Do you have a fun way to present FP concepts to novices or perhaps an especially interesting presentation of a difficult topic? In either case, please consider sharing it. Best lecture topics will be selected for presentation based on a short abstract describing the lecture and its interest to TFPIE attendees. The length of the presentation should be comparable to that of a paper. In addition, the speaker can provide commentary on effectiveness or student feedback. Submissions Potential presenters are invited to submit an extended abstract (4-6 pages) or a draft paper (up to 20 pages) in EPTCS style. The authors of accepted presentations will have their preprints and their slides made available on the workshop's website. Papers and abstracts can be submitted via easychair at the following link: https://easychair.org/conferences/?conf=tfpie2022 After the workshop, presenters are invited to submit (a revised version of) their article for the formal review. The PC will select the best articles for publication in the Electronic Proceedings in Theoretical Computer Science (EPTCS). Articles rejected for presentation and extended abstracts will not be formally reviewed by the PC. Important Dates Submission deadline: January 5th 2022, Anywhere on Earth. Notification: January 10th 2022 (Note: earlier submissions will receive earlier response) TFPIE Registration Deadline: TBA Workshop: February 11th 2022 Submission for formal review: April 15th 2022, Anywhere on Earth. Notification of full article: June 1st 2022 Camera ready: July 1st 2022 Program Committee Peter Achten, Radboud University, Netherlands Stephen Chang, University of Massachusetts Boston, USA John Hughes, Chalmers University of Technology, Sweden Elena Machkasova (Chair) - University of Minnesota Morris, USA Kristina Sojakova - INRIA, Paris, France Melinda Tóth, Eötvös Loránd University, Budapest, Hungary Keynote speaker Our keynote talk is "The perfect Functional Programming course" by Peter Achten. Registration information This year TFPIE takes place on the second day of the Lambda Days, concurrent with TFP. Participants will need to register for the Lambda Days. Please note that TFP and TFPIE have in-person attendance only. For registration fee, the deadlines, and the link to register see the Lambda Days web site: https://www.lambdadays.org/lambdadays2022 Registration and attendance are mandatory for at least one author of every paper that is presented at the workshop. Presenters will have their registration fee waived. Only papers that have been presented at TFPIE may be submitted to the post-reviewing process. Best regards, Elena Machkasova -- Dr. Elena Machkasova Associate Professor of Computer Science Division of Science and Mathematics University of Minnesota, Morris Office: Sci 2325 (320) 589-6308 http://cda.morris.umn.edu/~elenam/ Pronouns: she/her/hers or any other

1 0

Call for Haskell.org Committee Nominations
by Ida Bzowska 02 Dec '21

02 Dec '21

Hey, The Haskell.org Committee is looking for members. Maybe this is you or someone from your friends? Please read this post https://discourse.haskell.org/t/call-for-haskell-org-committee-nominations/… and drop us a line. λCheers Ida Bzowska

1 0