- Haskell-Cafe - Haskell.org

IFL23 first CFP
by Pieter Koopman 03 Apr '23

03 Apr '23

*Call for papers* The 35th Symposium on Implementation and Application of Functional Languages (IFL 2023) Braga, Portugal, August 29th-August 31st, 2023 *Important dates* Draft paper submission: July 31st, 2023 Draft paper notification: August 1st, 2023 Early registration deadline: August 11th, 2023 Late registration deadline: August 23rd, 2023 Symposium: August 29th - August 31st (3 days) *Scope* The goal of the IFL symposia is to bring together researchers actively engaged in the implementation and application of functional and function-based programming languages. IFL 2022 will be a venue for researchers to present and discuss new ideas and concepts, work in progress, and publication-ripe results related to the implementation and application of functional languages and function-based programming. Topics of interest to IFL include, but are not limited to: * language concepts * type systems, type checking, type inferencing * compilation techniques * staged compilation * run-time function specialization * run-time code generation * partial evaluation * abstract interpretation * metaprogramming * generic programming * automatic program generation * array processing * concurrent/parallel programming * concurrent/parallel program execution * embedded systems * web applications * embedded domain specific languages * security * novel memory management techniques * run-time profiling performance measurements * debugging and tracing * virtual/abstract machine architectures * validation, verification of functional programs * tools and programming techniques * industrial applications *Submissions and peer-review * Following IFL tradition, IFL 2023 will use a post-symposium review process to produce the formal proceedings. Before the symposium authors submit draft papers. These draft papers will be screened by the program chair to make sure that they are within the scope of IFL. The draft papers will be made available to all participants at the symposium. Each draft paper is presented by one of the authors at the symposium. Notice that it is a requirement that accepted draft papers are presented physically at the symposium. After the symposium, a formal review process will take place, conducted by the program committee. Reviewing is single blind. There will be at least 3 reviews per paper. The reviewers have 6 weeks to write their reviews. For the camera-ready version the authors can make minor revisions which are accepted without further reviewing. Contributions submitted for the draft paper deadline must be between two and twelve pages long. For submission details, please consult the IFL 2023 website at https://ifl23.github.io/ <https://ifl21-publicity-dot-yamm-track.appspot.com/2FXkDEWOUAQ2Tbyu5BN0P9Im…> . *Where * IFL 2023 will be held physically in Braga, Portugal, arranged by University of Minho. See the IFL 2023 website at https://ifl23.github.io/ <https://ifl21-publicity-dot-yamm-track.appspot.com/2vSkCLOx6DJpj_Yo1M1_gXPf…> for more information. [image: beacon]

1 0

GPT & Haskell
by Gregory Guthrie 02 Apr '23

02 Apr '23

>From a colleague: GPT Pretty smart(?!). But this is of course simple, and searchable. Still... -------------------------------------------------------------------------------------------------- GPT-4 when prompted: Write binary search in Haskel. Print results using putStrLn. Ensure bug-free code by specifying preconditions, postconditions, invariants, variants, internal states. gives the following response: -- Binary search in Haskell -- Precondition: the list is sorted in ascending order -- Postcondition: the function returns the index of the target element if found, or Nothing otherwise -- Invariant: the search space is always within the bounds of the list -- Variant: the search space decreases by half at each recursive call -- Internal state: the lower and upper bounds of the search space binarySearch :: Ord a => [a] -> a -> Maybe Int binarySearch xs x = go xs x 0 (length xs - 1) where go xs x lo hi | lo > hi = Nothing -- base case: search space is empty | x == midElem = Just mid -- base case: target element is found | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half where mid = (lo + hi) `div` 2 -- calculate the middle index midElem = xs !! mid -- get the middle element -- Print results using putStrLn main :: IO () main = do let xs = [1, 3, 5, 7, 9] -- a sorted list of integers let x = 5 -- a target element to search for let result = binarySearch xs x -- call the binary search function case result of -- pattern match on the result Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned The above code runs: https://onecompiler.com/cpp/3z48yt2pp [cid:image001.png@01D963E1.B0EB6AB0]

20 38

Re: [Haskell-cafe] GPT & Haskell
by Aloïs Cochard 01 Apr '23

01 Apr '23

Thanks for fixing the link Nenad, I leave you with an excerpt from Oleg's last paper which contains that beautiful quote: ``This make me think that the authors are under the impression that compilers can magically transform bad code into efficient high-quality code by clever enough optimizations. As a compiler writer, I consider this a complete myth that many students and non-compiler-developers hope is a truth. I agree that compilers should aim to improve the efficiency of the code given as input, but one cannot expect the compiler to recognize algorithms and swap them for ones with better asymptotic complexity or *make other major code transformations that really should be the job of the programmer*. [emphasis mine]'' Magnus Myreen. On Sat, 1 Apr 2023 at 18:06, Nenad Končar <nlpresearcher(a)gmail.com> wrote: > GPT-4 when prompted with an improved prompt: > > *Write binary search in Haskel. Print results using putStrLn. Ensure > bug-free code by specifying preconditions, postconditions, invariants, > variants and internal states. Calculate the middle index using a safer > formula to avoid intermediate overflow.* > > > > gives the following response: > > *-- Binary search is a recursive algorithm that finds an element in a > sorted list by* > > *-- repeatedly dividing the list into two halves and comparing the element > with the middle value.* > > *-- It returns the index of the element if found, or Nothing otherwise.* > > > > *-- Precondition: The input list must be sorted in ascending order.* > > *-- Postcondition: The output index must be within the bounds of the list > and point to the element, or be Nothing.* > > *-- Invariant: The element, if present, must be in the current sublist.* > > *-- Variant: The length of the current sublist decreases by half at each > recursive call.* > > *-- Internal state: The current sublist is defined by two indices: low and > high.* > > > > *binarySearch :: Ord a => [a] -> a -> Maybe Int* > > *binarySearch xs x = go xs x 0 (length xs - 1)* > > * where* > > * -- The go function performs the recursive search on the sublist > [low..high].* > > * go :: Ord a => [a] -> a -> Int -> Int -> Maybe Int* > > * go xs x low high* > > * -- Base case 1: The sublist is empty, so the element is not found.* > > * | low > high = Nothing* > > * -- Base case 2: The middle value is equal to the element, so the > index is found.* > > * | xs !! mid == x = Just mid* > > * -- Recursive case 1: The element is smaller than the middle value, > so search in the left half.* > > * | x < xs !! mid = go xs x low (mid - 1)* > > * -- Recursive case 2: The element is larger than the middle value, > so search in the right half.* > > * | otherwise = go xs x (mid + 1) high* > > * where* > > * -- Calculate the middle index using a safer formula to avoid > overflow.* > > * mid = low + (high - low) `div` 2* > > > > *-- A sample list to test the binary search function.* > > *sampleList :: [Int]* > > *sampleList = [1, 3, 5, 7, 9, 11, 13, 15]* > > > > *-- A sample element to search for in the list.* > > *sampleElement :: Int* > > *sampleElement = 9* > > > > *-- Print the result of the binary search using putStrLn.* > > *main :: IO ()* > > *main = do* > > * let result = binarySearch sampleList sampleElement* > > * case result of* > > * Nothing -> putStrLn "Element not found."* > * Just i -> putStrLn $ "Element found at index " ++ show i ++ "."* > > The above code runs: > *https://onecompiler.com/haskell/3z4c7f5dt > <https://onecompiler.com/haskell/3z4c7f5dt>* > > > Furthermore, GPT-4 when prompted: > > *For the binary search algorithm, list all possible preconditions, > postconditions, invariants, variants, internal states, underflows, > overflows, divisions by zero, mistakes, errors, bugs, run-time exceptions, > faults, defects and pitfalls.* > > and then prompting GPT-4 again with: > > *Summarize the following:* > > *<result from the previous prompt given to * *GPT-4* > *>* > > gives the following response: > > *Hi there,* > > *I hope this email finds you well. I am writing to summarize the > following:* > > > > > > > > > > > *- The algorithm searches for a target value in a sorted array using > binary search. - The algorithm returns the index of the target value in the > array or -1 if the target value is not found. - The algorithm does not > modify the input array. - The algorithm assumes that the input array is > sorted in ascending or descending order, the target value is comparable > with the elements of the array, and the lower and upper bounds of the > search range are valid indices of the array. - The algorithm maintains the > invariant that the target value is always within the search range or does > not exist in the array. - The algorithm reduces the size of the search > range by at least one after each iteration. - The algorithm handles edge > cases such as empty array, single element array, target value at the first > or last position of the array, lower and upper bounds being equal, negative > or large positive integers, and division by zero when calculating the > middle index. - The algorithm avoids integer underflow or overflow when > calculating the middle index by using bitwise operations instead of > arithmetic operations. - The algorithm has been tested with various test > cases to ensure its correctness and efficiency. - The algorithm has been > verified using formal methods to prove its preconditions, postconditions, > invariants and variants.* > *Please let me know if you have any questions or feedback about the > algorithm. I appreciate your time and attention.* > > > The following web pages provide some credence to GPT-4's claim of > avoiding overflows/underflows by using bitwise operations instead of > arithmetic operations: > > https://stackoverflow.com/questions/10078778/bitwise-overflow-checking-in-c > > https://www.opensourceforu.com/2009/03/joy-of-programming-how-to-detect-int… > > The truth is that bitwise operations can recognise if an overflow is about > to happen prior to it happening. I do not see how bitwise operations can > *avoid* overflow and therefore GPT-4's claim in this case, in my humble > view, should be classified as it having a *vivid imagination*. > > > > > > > On Sat, 1 Apr 2023 at 16:11, Nenad Končar <nlpresearcher(a)gmail.com> wrote: > >> Here is the correct link to Haskel code: >> >> https://onecompiler.com/haskell/3z4c7f5dt >> >> On Sat, 1 Apr 2023 at 15:42, Gregory Guthrie <guthrie(a)miu.edu> wrote: >> >>> Yes, will check on it. >>> >>> >>> >>> That is because the reason that a simple program was used was because >>> the example was to ask GPT to solve it is a range of languages, one of >>> which was Haskell and there were links to solutions in all of them.. >>> >>> >>> >>> “*Write binary search in xxxx. Ensure bug-free code by specifying >>> preconditions, postconditions, invariants, variants, internal states.”* >>> >>> >>> >>> { HTML, CSS and JavaScript, C++, Haskell, JavaScript, Python, >>> CommonLisp, C, C#, PHP, Java, Go, Erlang, Alloy, TLA+, X-Machine, PVS >>> Verifier, SPIN model checker, Guarded Command Language, Hoare triples, >>> Gries & Owicki concurrent code} >>> >>> >>> >>> It was an interesting exercise from Dr. Nenad Koncar, a successful NL >>> researcher and developer. I’ll ask him for a corrected link to the Haskell >>> version. >>> >>> >>> >>> Dr. Gregory Guthrie >>> >>> >>> >>> *From:* Aloïs Cochard <alois.cochard(a)gmail.com> >>> *Sent:* Saturday, April 1, 2023 8:23 AM >>> *To:* Gregory Guthrie <guthrie(a)miu.edu> >>> *Cc:* haskell-cafe(a)haskell.org; Nenad Končar <nlpresearcher(a)gmail.com>; >>> Haskell Community < >>> replies%2Bf6607596e3ee63f105e2b0327b86f062(a)discourse.haskell.org> >>> *Subject:* Re: [Haskell-cafe] GPT & Haskell >>> >>> >>> >>> Dear Gregory, >>> >>> >>> >>> Can you please fix your onecompiler vanity link? It points to the C++ >>> runtime implementation. >>> >>> >>> >>> Thanks >>> >>> >>> >>> On Fri, 31 Mar 2023 at 22:04, Gregory Guthrie <guthrie(a)miu.edu> wrote: >>> >>> From a colleague: >>> >>> GPT Pretty smart(?!). >>> >>> But this is of course simple, and searchable. >>> >>> >>> >>> Still… >>> >>> >>> -------------------------------------------------------------------------------------------------- >>> >>> GPT-4 when prompted: >>> >>> *Write binary search in Haskel. Print results using putStrLn. Ensure >>> bug-free code by specifying preconditions, postconditions, invariants, >>> variants, internal states.* >>> >>> >>> >>> gives the following response: >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> *-- Binary search in Haskell -- Precondition: the list is sorted in >>> ascending order -- Postcondition: the function returns the index of the >>> target element if found, or Nothing otherwise -- Invariant: the search >>> space is always within the bounds of the list -- Variant: the search space >>> decreases by half at each recursive call -- Internal state: the lower and >>> upper bounds of the search space binarySearch :: Ord a => [a] -> a -> Maybe >>> Int binarySearch xs x = go xs x 0 (length xs - 1) where go xs x lo hi >>> | lo > hi = Nothing -- base case: search space is empty | x == >>> midElem = Just mid -- base case: target element is found | x < >>> midElem = go xs x lo (mid - 1) -- recursive case: search in the left half >>> | otherwise = go xs x (mid + 1) hi -- recursive case: search in the >>> right half where mid = (lo + hi) `div` 2 -- calculate the >>> middle index midElem = xs !! mid -- get the middle element -- Print >>> results using putStrLn main :: IO () main = do let xs = [1, 3, 5, 7, 9] >>> -- a sorted list of integers let x = 5 -- a target element to search for >>> let result = binarySearch xs x -- call the binary search function case >>> result of -- pattern match on the result Nothing -> putStrLn "Element >>> not found" -- print a message if Nothing is returned Just i -> putStrLn >>> $ "Element found at index " ++ show i -- print a message with the index if >>> Just i is returned* >>> >>> >>> >>> The above code runs: >>> >>> *https://onecompiler.com/cpp/3z48yt2pp >>> <https://onecompiler.com/cpp/3z48yt2pp>* >>> >>> _______________________________________________ >>> 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. >>> >>> >>> >>> -- >>> >>> *Λ\oïs* >>> >>> http://twitter.com/aloiscochard >>> >>> http://github.com/aloiscochard >>> >> -- *Λ\oïs* http://twitter.com/aloiscochard http://github.com/aloiscochard

1 0

Re: [Haskell-cafe] GPT & Haskell
by Gregory Guthrie 01 Apr '23

01 Apr '23

---------- Forwarded message ---------- From: "Nenad Končar" <nlpresearcher(a)gmail.com<mailto:nlpresearcher@gmail.com>> To: Levent Erkok <erkokl(a)gmail.com<mailto:erkokl@gmail.com>> Cc: Gregory Guthrie <guthrie(a)miu.edu<mailto:guthrie@miu.edu>>, "haskell-cafe(a)haskell.org<mailto:haskell-cafe@haskell.org>" <haskell-cafe(a)haskell.org<mailto:haskell-cafe@haskell.org>>, Haskell Community <replies%2Bf6607596e3ee63f105e2b0327b86f062(a)discourse.haskell.org<mailto:replies%2Bf6607596e3ee63f105e2b0327b86f062@discourse.haskell.org>> Bcc: Date: Sat, 1 Apr 2023 00:00:09 +0200 Subject: Re: [Haskell-cafe] GPT & Haskell On Fri, 31 Mar 2023 at 23:24, Levent Erkok <erkokl(a)gmail.com<mailto:erkokl@gmail.com>> wrote: This code is buggy when lo + hi overflows your integer type. Classic (extremely) corner case bug: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html Thank you kindly for pointing this out. GPT-4, when prompted, is able to detect and correct the overflow mistake as follows: After I introduced a purposeful mistake in the Haskel code, I prompted GPT-4 as follows: If the following Haskel code contains any logical mistakes then correct the code for me: -- Binary search in Haskell -- Precondition: the list is sorted in ascending order -- Postcondition: the function returns the index of the target element if found, or Nothing otherwise -- Invariant: the search space is always within the bounds of the list -- Variant: the search space decreases by half at each recursive call -- Internal state: the lower and upper bounds of the search space binarySearch :: Ord a => [a] -> a -> Maybe Int binarySearch xs x = go xs x 0 (length xs - 1) where go xs x lo hi | lo > hi = Nothing -- base case: search space is empty | x == midElem = Just mid -- base case: target element is found | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half where mid = (lo - hi) `div` 2 -- calculate the middle index midElem = xs !! mid -- get the middle element -- Print results using putStrLn main :: IO () main = do let xs = [1, 3, 5, 7, 9] -- a sorted list of integers let x = 5 -- a target element to search for let result = binarySearch xs x -- call the binary search function case result of -- pattern match on the result Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned and then GPT-4 replied: Hello, Thank you for sending me your Haskell code for binary search. I appreciate your interest in learning this functional programming language. I have reviewed your code and found a few logical mistakes that need to be corrected. Here is the revised code with some comments explaining the changes: -- Binary search in Haskell -- Precondition: the list is sorted in ascending order -- Postcondition: the function returns the index of the target element if found, or Nothing otherwise -- Invariant: the search space is always within the bounds of the list -- Variant: the search space decreases by half at each recursive call -- Internal state: the lower and upper bounds of the search space binarySearch :: Ord a => [a] -> a -> Maybe Int binarySearch xs x = go xs x 0 (length xs - 1) where go xs x lo hi | lo > hi = Nothing -- base case: search space is empty | x == midElem = Just mid -- base case: target element is found | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half where mid = lo + (hi - lo) `div` 2 -- calculate the middle index using a safer formula to avoid overflow midElem = xs !! mid -- get the middle element -- Print results using putStrLn main :: IO () main = do let xs = [1, 3, 5, 7, 9] -- a sorted list of integers let x = 5 -- a target element to search for let result = binarySearch xs x -- call the binary search function case result of -- pattern match on the result Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned The main mistake in your code was in the calculation of the middle index. You used `(lo - hi) `div` 2`, which is incorrect because it will always give a negative value. The correct formula is `lo + (hi - lo) `div` 2`, which ensures that the middle index is always within the bounds of the list. This formula also avoids overflow issues that might occur if you use `(lo + hi) `div` 2`. I hope this helps you understand binary search better and improve your Haskell skills. Please let me know if you have any questions or feedback. I would love to hear from you and help you further. Happy coding! The improved code runs: https://onecompiler.com/haskell/3z4avpx6n On Mar 31, 2023, at 1:02 PM, Gregory Guthrie <guthrie(a)miu.edu<mailto:guthrie@miu.edu>> wrote: From a colleague: GPT Pretty smart(?!). But this is of course simple, and searchable. Still… -------------------------------------------------------------------------------------------------- GPT-4 when prompted: Write binary search in Haskel. Print results using putStrLn. Ensure bug-free code by specifying preconditions, postconditions, invariants, variants, internal states. gives the following response: -- Binary search in Haskell -- Precondition: the list is sorted in ascending order -- Postcondition: the function returns the index of the target element if found, or Nothing otherwise -- Invariant: the search space is always within the bounds of the list -- Variant: the search space decreases by half at each recursive call -- Internal state: the lower and upper bounds of the search space binarySearch :: Ord a => [a] -> a -> Maybe Int binarySearch xs x = go xs x 0 (length xs - 1) where go xs x lo hi | lo > hi = Nothing -- base case: search space is empty | x == midElem = Just mid -- base case: target element is found | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half where mid = (lo + hi) `div` 2 -- calculate the middle index midElem = xs !! mid -- get the middle element -- Print results using putStrLn main :: IO () main = do let xs = [1, 3, 5, 7, 9] -- a sorted list of integers let x = 5 -- a target element to search for let result = binarySearch xs x -- call the binary search function case result of -- pattern match on the result Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned The above code runs: https://onecompiler.com/cpp/3z48yt2pp <image001.png> _______________________________________________ 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.

1 0

[Haskell] [ANNOUNCE] Haskell Language Server 1.10.0.0 released
by Zubin Duggal 31 Mar '23

31 Mar '23

Binaries for this release are available at https://downloads.haskell.org/~hls/haskell-language-server-1.10.0.0/. These binaries can be installed using [GHCup](https://www.haskell.org/ghcup/) or version [2.0.0 and above](https://github.com/haskell/vscode-haskell/releases) of the VSCode extension. Older versions of the VSCode extension will not attempt to download this version. # Changelog - Support for GHC 9.6 - Binaries for GHC 9.2.7 and GHC 9.6.1 - Eval plugin support for GHC 9.4+ (#3391) - Don't show lenses for TH generated instances when using hls-class-plugin (#3531) For the full release notes, see https://github.com/haskell/haskell-language-server/releases/tag/1.10.0.0 Happy editing! - Zubin

2 1

Munich Haskell Meeting, 2023-03-29 @ 19:30
by Leah Neukirchen 27 Mar '23

27 Mar '23

Dear all, This week, our monthly Munich Haskell Meeting will take place again on Wednesday, March 29 at Augustiner-Gaststätte Rumpler at 19h30. For details see here: http://muenchen.haskell.bayern/dates.html If you plan to join, please add yourself to this nuudel so we can reserve enough seats! It is OK to add yourself to the dudle anonymously or pseudonymously. https://nuudel.digitalcourage.de/21as1kuu1eUg8qTt Everybody is welcome! cu, -- Leah Neukirchen <leah(a)vuxu.org> https://leahneukirchen.org/

2 1

PhD Position at KU Leuven
by Tom Schrijvers 27 Mar '23

27 Mar '23

Dear Haskell Cafe, Are you a highly motivated individual with a passion for programming languages and theory? Do you hold a master's degree in computer science or a related field and have a proven academic track record? If so, we invite you to apply for the PhD Position in Programming Languages at KU Leuven. In this position, you will join the team of Professor Tom Schrijvers, which has a strong reputation in programming language research, covering topics such as functional programming, domain-specific languages, and equational reasoning. Your research will focus on multi-stage programming and computational effects, with the aim of developing a formal calculus for multi-staging with support for algebraic effects and handlers. You will benefit from a competitive monthly stipend, an exciting interdisciplinary research environment, and the opportunity to attend international conferences and collaborate with international partners. Apply now and advance the state-of-the-art in programming language research. For more information and applications, see: https://www.kuleuven.be/personeel/jobsite/jobs/60203785?hl=en&lang=en Best, Tom Schrijvers

1 0

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