- Haskell-Cafe - Haskell.org

Open Kattis Problem Srednji: Hints to improve my algorithm
by Dominik Bollmann 24 Sep '20

24 Sep '20

Hi Haskell-Cafe, I've been trying to solve the Open Kattis Problem called Srednji recently, unfortunately without success. Given a sequence A and a number B within that sequence this problem asks to find all odd sub-sequences of A that, when sorted, have B as their median in the middle. That is, from A we may remove some prefix and/or suffix and if the resulting sub-sequence -- when sorted -- contains B in the middle, then this sub-sequence is a solution. The problem asks to find the number of all solutions. Check out https://open.kattis.com/problems/srednji for the details. My Haskell solution below tries to find the number of odd sub-sequences by first locating the median and then repeatedly moving left and right from that median to find larger and larger sub-sequence candidates. Each found candidate is checked to have B in the middle when sorted in order to become a solution. Moreover, I also extend each such candidate further to the left (and to the right, respectively) to determine whether these leftward or rightward extensions are solutions, too. I think with this approach I systematically enumerate all solutions. Unfortunately, though, this approach is too slow and times out on the 11th hidden test cases. I'd therefore be thankful for hints about different approaches to solving this problem more efficiently. Thanks! Dominik. ==================================================================== My current, slow Haskell code is this: import Data.Maybe import Data.Sequence (Seq, (<|), (|>)) import qualified Data.Sequence as Seq import qualified Data.Vector.Unboxed as Vec data SubSeq = SubSeq { getBalance :: {-# UNPACK #-} !Int , getSubSeq :: Seq Int , from :: {-# UNPACK #-} !Int , to :: {-# UNPACK #-} !Int } balancedSubSeqs :: [Int] -> Int -> [SubSeq] balancedSubSeqs seq med = do candidate <- leftRight [val0] let lefts = leftLeft candidate [] rights = rightRight candidate [] candidate ?: lefts ++ rights where medidx = fromJust (Vec.findIndex (== med) arr) val0 = SubSeq 0 (Seq.singleton med) medidx medidx arr = Vec.fromList seq leftRight cands@(SubSeq balance seq i j : _) | i-1 < 0 || j+1 >= Vec.length arr = cands | otherwise = let v1 = arr Vec.! (i-1) v2 = arr Vec.! (j+1) balance' = newBalance balance v1 v2 seq' = (v1 <| seq) |> v2 in leftRight (SubSeq balance' seq' (i-1) (j+1) : cands) leftLeft cand@(SubSeq balance seq i j) sols | i-2 < 0 = sols | otherwise = let v1 = arr Vec.! (i-2) v2 = arr Vec.! (i-1) balance' = newBalance balance v1 v2 seq' = v1 <| v2 <| seq newCand = SubSeq balance' seq' (i-2) j in leftLeft newCand (newCand ?: sols) rightRight cand@(SubSeq balance seq i j) sols | j+2 >= Vec.length arr = sols | otherwise = let v1 = arr Vec.! (j+1) v2 = arr Vec.! (j+2) balance' = newBalance balance v1 v2 seq' = seq |> v1 |> v2 newCand = SubSeq balance' seq' i (j+2) in rightRight newCand (newCand ?: sols) newBalance old n1 n2 | n1 < med, n2 < med = old - 2 | n1 > med, n2 > med = old + 2 | otherwise = old infixr 5 ?: --(?:) :: SubSeq -> [SubSeq] -> [SubSeq] x@(SubSeq b _ _ _) ?: xs | b == 0 = x : xs | otherwise = xs main :: IO () main = do [len, median] <- fmap read . words <$> getLine seq <- fmap read . words <$> getLine let solutions = balancedSubSeqs seq median print (length solutions)

3 5

Re: [Haskell-cafe] Are explicit exports and local imports desirable in a production application?
by Olaf Klinke 23 Sep '20

23 Sep '20

Dear Ignat, have you seen https://wiki.haskell.org/Import_modules_properly https://wiki.haskell.org/Qualified_names I find the arguments convincing. Even in my own packages I sometimes get lost where a certain function was imported from. When neither exports nor imports are done explicitly, you usually have only two choices: 1. search all sources (e.g. with grep -l) 2. rely on the haddock index Maybe your IDE can do that for you, but you can't expect all downstream users or all your colleagues to do the same. -- Olaf

8 10

Re: [Haskell-cafe] Readable Haskell
by Ignat Insarov 22 Sep '20

22 Sep '20

Hello Ian and Mario. > > We have retina screens, GPU accelerated rendering and magical > > auto-completion. > > Who's "we"? 1 and 2 are constrained by money. 1 and 3 are also > constrained by personal preference. > > I need a _big_ screen because I also do photo processing beside coding, > and I can't afford 2 screens, one big and another high density. > > Command shell is a very old and peculiar human interface — if human at > > all. They had 80 character wide screens and visibly lagging connexion. > > We have retina screens, GPU accelerated rendering and magical > > auto-completion. > > You might have that. I, as a blind braille display user, > have one line of at most 80 characters. When I am traveling, I > typically only have 40 characters. Given these constraints, I still > consider a command line interface superior to any sort of buttonized > nonesense. But thats just me, apparently. This is not how I expected my message to be understood. I did not mean to imply that every Haskell programmer has or should have a retina screen and a high performance GPU — only that, as a profession, we have way better tools now than back then. In humanities, it is usual for there to be either a normal distribution or a Pareto distribution in any large enough sample of data. So, unlike in precise sciences, a counter-example does not refute a proposition. What matters is that there is a trend. And there is a trend associated with larger and finer displays. It dawns on even the most _«old school»_ people by now. See for example a letter on Linux Kernel Mailing List.[1] > When I tile my terminal windows on my display, I can have 6 terminals > visible at one time, and that's because I have them three wide. And I > could still fit 80% of a fourth one side-by-side. > > And guess what? That's with my default "100x50" terminal window (go to > your gnome terminal settings, you'll find that the 80x25 thing is just > an initial default that you can change), not with some 80x25 one. And > that's with a font that has anti-aliasing and isn't some pixelated > mess. I have no specific insight about how to optimize readability for people that listen to code[2] or sense it with their hands. What I am sure of is that there are better ways to go about it than dwelling in the past. [1]: https://lkml.org/lkml/2020/5/29/1038 [2]: https://www.vincit.fi/fi/software-development-450-words-per-minute/

4 4

Readable Haskell
by Misja Alma 21 Sep '20

21 Sep '20

Hi, I have been writing Haskell in my spare time for a couple of years now, but when I showed some code lately to a friend he remarked that he didn't find it very readable. Actually I agree, when I look at my own code of a couple of months old I have trouble figuring out too what exactly it is doing. I'm coming from a Java and Scala background and there, especially for Java, are some generally accepted best practices that make sure that your teammates don't have too much trouble reading your code. E.g. write short functions with a single responsibility, use variable, class and function names that explain what they are meant for, etc. I think some of those best practices, like short functions with single responsibility, are useful for Haskell as well. But Haskell is a different language than Java and has its own strong points and pitfalls regarding readability, so it probably needs different coding standards as well. I have been looking on the Internet if I could find some tips about improving readability but all I could find was http://www.haskellforall.com/. Although there are some useful tips in there, this site seems to be aimed at making Haskell easier to read for newcomers from other languages. What I am interested in are tips from real projects that are built by real teams. Does anybody have any tips, or are there some sites or books that I could read about this topic? Thanks, Misja

15 20

Re: [Haskell-cafe] Readable Haskell
by Taeer Bar-Yam 20 Sep '20

20 Sep '20

Can we agree that it's possible to go too far? Even in the global scope. https://github.com/Quotation/LongestCocoa. I think another factor that comes into play is how frequently you use the function/value. If it comes up only once in a while, then every time someone encounters it they are likely to have to remind themselves what all the abreviations mean. If it comes up more frequently, then they likely already saw it 10 lines ago, and remember. If it comes up very frequently, then whatever name you assign it takes on its own meaning. Think about `map` or, in bash land `ls` and `cd`. Unless you just started using bash, you're not going to think "Oh. cd stands for 'change directory'". It's just… cd. And at the same time, using a long name for something that's going to come up every couple of lines is, IMO, distracting. Having all of the information be within what your eye can easily take in at once has huge advantages. Not to mention, can you imagine writing `changeDirectory` and `printDirectoryContents` every time? It's a balancing act. Obviously, the opposite extreme carries its own problems. --Taeer

6 5

[ANN] Reanimate v1.0
by Lemmih 20 Sep '20

20 Sep '20

It is my great pleasure to announce version 1.0 of the Reanimate animation library. Reanimate aims to be a batteries-included way of creating animations and illustrations. To see it in action, visit: https://reanimate.github.io/ Reanimate wouldn't be here without help and I'd like to thank Jan Hrček for writing the Elm viewer, Shaurya Gupta for performance improvements, William Yaoh for writing documentation, Mike Pilgrem for ImageMagick v7 support, and Xie Ruifeng for LaTeX and text encoding fixes. Furthermore, I'd like to thank Eve, Joe, Rodrigo, Brad, Aron, and Ben for their help and support. Finally, I'd like to thank the GitHub sponsors who are financing server costs and making Reanimate the best it can be. Hackage: https://hackage.haskell.org/package/reanimate Haddock: https://hackage.haskell.org/package/reanimate/docs/Reanimate.html Tutorial: https://reanimate.readthedocs.io/en/latest/tut_equation/ GitHub: https://github.com/reanimate/reanimate/ Website: https://reanimate.github.io/ Discord: https://discord.gg/Qs28Dv6 Sponsors: https://github.com/sponsors/Lemmih Best wishes, David.

1 0

program description based programming
by Luc Duponcheel 18 Sep '20

18 Sep '20

Hellot Just started with the new version of the PDBP library. https://github.com/PDBP Work in progress. Expect frequent additions (and changes). Luc -- __~O -\ <, (*)/ (*) reality goes far beyond imagination

1 0

Are explicit exports and local imports desirable in a production application?
by Ignat Insarov 18 Sep '20

18 Sep '20

I apologize if this topic has already been clarified elsewhere — please refer me. The present message can also be seen _(and answered)_ on the Haskell Discourse board.[1] To clarify, an explicit export: module X (…) where … An explicit import: import X (…) ## I would like to question the desirability of explicit exports and local imports in a production application. I want to make two cases: * That explicit exports are never necessary. Moreover, that explicit exports are harmful as they make checking of non-exported definitions impossible. * That explicit imports are not necessary when importing a module from the same package. By default, I make an easy claim that none are desirable since they incur mindless typing effort and thereby unfairly tax the programmer. Let us then consider the justifications for their use despite that. ### Explicit exports. When there are no explicit exports, everything is exported from a module. Recall a case when this is disadvantageous: abstract types. The values of abstract types must only be obtained via smart constructors. So their definitions should not be made available. Explicit exports may provide that. However, there is another practice: putting dangerous definitions of the supposedly abstract type `X` into a module `X.Internal`, then importing them to module `X` and defining smart constructors there. By default, a module only exports the definitions defined in itself — there are no re-exports. So, a user importing `X` cannot invoke unsafe constructors from `X.Internal`, and they know better than to import the dangerous module directly. In the former case above, the internal definitions remain out of reach for a test suite. In the latter case, they may be freely checked as needed. ### Explicit imports. Recall the scenario in which explicit imports are useful. * A module `"p" X` from package `p` imports a module `"q" Y` from package `q v0.0.0`. * The package `q` bumps the third version number and exports a definition `Y.d` which name coincides with an already defined definition `X.d`. What happens? * If imports are explicit, nothing happens. The maintainers of `p` are safe if they set a restriction as weak as `q ^>= 0.0`. * If imports are implicit, there would be a clash of names if `p` is built against `q v0.0.1`, but the build would pass if it is built against a less recent version `q v0.0.0.1`. The maintainers of `p` might not even notice that the package does not build in some cases. When they do, they would have to set a restriction `q ^>= 0.0.0` But surely there is only one version to build against if the two modules reside in the same package. So the overlapping names will necessarily result in an error that would immediately be rectified. It is no different from any other compile time error. ## Are my considerations fair? [1]: https://discourse.haskell.org/t/are-explicit-exports-and-local-imports-desi…

3 8

ghcxxxx.exe in Local\Temp in Windows
by Sumit Raja 18 Sep '20

18 Sep '20

Hi, Running ghc 8.8.4 + cabal 3.2 on Windows. M365 malware scanner identified that ghcbdbc.exe in my temp directory was the Wacatac malware. I checked and there is a large number of these ghcxxxx.exe files in there. They look like build artefacts from cabal repl. The malware scanner process tree is cabal -> gcc -> realgcc -> collect2 with ld.exe being the exec that created it. Admin is confident that Wacatac was removed or it was a false alarm but I need to provide some details on why this build artefact is created. Anyone know what these files are? Thanks Sumit

1 0

[ANN] base16-bytestring-1.0.0.0
by Emily Pillmore 17 Sep '20

17 Sep '20

Hello Everyone, I'm pleased to announce version 1.0.0.0 of the `base16-bytestring` library. This release marks an epochal change in the library's structure, changing some existing features, and adding others. There was only on PR contribution marking this release, but it was a big omnibus one. In the latest release, we... * Improved performance by 3-4x for encode, 4-5x for decode. * Changed the ` decode` signature to return an error message with offset. The signature will now be ` ByteString -> Either String ByteString` in alignment with other encoding standards. * Actually test using the test vectors defined in the RFC, and uses property tests to ensure invariants hold. * Added lenient decoders to the API * Added ` -XTrustworthy` annotations to the relevant exposed modules * Rewrote the haddocks to be more up to date and fancy-styled. * Added benchmarks to the `.cabal` file as opposed to being a separate target, so they can be run at toplevel, and can exist as an integral part of the spec. * Bumped the Cabal version to 1.12 Thanks to Herbert and Mikhail for helping make this happen. Cheers, Emily

1 0