April 2014 - Haskell-Cafe

Seems a wrong implementation of Graham Scan in Haskell Wiki
by Yang Leo 11 Apr '14

11 Apr '14

The implementation in the page: http://www.haskell.org/haskellwiki/Graham_Scan_Implementation seems to be wrong. Given a Point list as follows: pts5 = [Point (0,0), Point (0,4), Point (1,4), Point (2,3), Point (6,5), Point (6,0)] The gscan will output a wrong answer which included a inner point Point (1,4). That is because the implemented algorithm cannot handle the situation where multiple consecutive points need to be removed. Here is my implementation: ``` module GrahamScan where import Data.List (sortBy) import Data.Function (on) -- 9. define data `Direction` data Direction = GoLeft | GoRight | GoStraight deriving (Show, Eq) -- 10. determine direct change via point a->b->c -- -- define 2D point data Pt = Pt (Double, Double) deriving (Show, Eq, Ord) isTurned :: Pt -> Pt -> Pt -> Direction isTurned (Pt (ax, ay)) (Pt (bx, by)) (Pt (cx, cy)) = case sign of EQ -> GoStraight LT -> GoRight GT -> GoLeft where sign = compare ((bx - ax) * (cy - ay)) ((cx - ax) * (by - ay)) -- 12. implement Graham scan algorithm for convex -- -- Helper functions -- -- Find the most button left point buttonLeft :: [Pt] -> Pt buttonLeft [] = Pt (1/0, 1/0) buttonLeft [pt] = pt buttonLeft (pt:pts) = minY pt (buttonLeft pts) where minY (Pt (ax, ay)) (Pt (bx, by)) | ay > by = Pt (bx, by) | ay < by = Pt (ax, ay) | ax < bx = Pt (ax, ay) | otherwise = Pt (bx, by) -- -- Main convex :: [Pt] -> [Pt] convex [] = [] convex [pt] = [pt] convex [pt0, pt1] = [pt0, pt1] convex pts = scan [pt0] spts where -- Find the most buttonleft point pt0 pt0 = buttonLeft pts -- Sort other points `ptx` based on angle <pt0->ptx> spts = tail (sortBy (compare `on` compkey pt0) pts) where compkey (Pt (ax, ay)) (Pt (bx, by)) = (atan2 (by - ay) (bx - ax), {-the secondary key make sure collinear points in order-} abs (bx - ax)) -- Scan the points to find out convex -- -- handle the case that all points are collinear scan [p0] (p1:ps) | isTurned pz p0 p1 == GoStraight = [pz, p0] where pz = last ps scan (x:xs) (y:z:rsts) = case isTurned x y z of GoRight -> scan xs (x:z:rsts) GoStraight -> scan (x:xs) (z:rsts) -- I choose to skip the collinear points GoLeft -> scan (y:x:xs) (z:rsts) scan xs [z] = z : xs ``` The source file is at https://github.com/robturtle/Haskell/blob/master/ch03/GrahamScan.hs Maybe not elegant for I just finished the first 3 chapters in Real World Haskell. However it at least correctly computes the example `pts5`

2 1

How to find consumer packages on Hackage?
by Han Joosten 11 Apr '14

11 Apr '14

Hi, I wonder if there is a (simple?) way to find out which packages use some package foo? The reason I would like this is that I am interested in using configFile in a project, and I would like to look at some example usage of it. So in my case I am interested in knowing what packages use configFile. I presume there is a generic way to find out.... Cheers Han Joosten

2 2

Confused about type seen in the wild
by Alexander Solla 10 Apr '14

10 Apr '14

I'm using the yesod-markdown package as a "template" for making my own yesod-mathjax package. I'm pretty much done, and it does compile now, but I'm just really confused by a type that looks like bad syntax. In fact, I ended up trying to "fix" it, which lead to errors: mathJaxField :: Monad m => RenderMessage (HandlerSite m) FormMessage => Field m MathJax Notice that there are two type arrows (=>). Interestingly, mathJaxField :: ( Monad m , RenderMessage (HandlerSite m) FormMessage ) => Field m MathJax compiles too. So it looks like currying/uncurrying, at the type level. But when did this start? I'm using GHC 7.6.3

8 18

ANN.: TreeViz v0.0.6 release.
by David Banas 10 Apr '14

10 Apr '14

I’ve just posted version `v0.0.6’ of the TreeViz package to both Hackage and GitHub. This release fixes the “mixed decimation style failure” bug, in which a DIF stage followed by a DIT stage, followed by anything was giving incorrect numerical results for the FFT. Cheers, -db

1 0

ANN.: TreeViz v0.0.6 release.
by David Banas 10 Apr '14

10 Apr '14

I’ve just posted version `v0.0.6’ of the TreeViz package to both Hackage and GitHub. This release fixes the “mixed decimation style failure” bug, in which a DIF stage followed by a DIT stage, followed by anything was giving incorrect numerical results for the FFT. Cheers, -db

1 0

Stackage with GHC 7.8: build results
by Michael Snoyman 10 Apr '14

10 Apr '14

I'm happy to report that after about six months, enough upper bounds have been corrected on Hackage that a Stackage build with GHC 7.8 can now proceed. I've run a build with 7.8.0rc2, and have uploaded the build.log[1] and the complete cabal output for each package[2]. The good news is that most packages are building correctly, though there is still at least one package deep in the dependency tree which does not build (pcre-light). Here's a list of packages which failed to build, ignoring those which couldn't be built due to broken dependencies: * fpco-api (yes, I'm working on it) * gitlib * groundhog * monad-peel * parsestar * pcre-light * recursion-schemes * statistics * syb-extras * thyme * uniqueid [1] http://download.fpcomplete.com/ghc-7.8-builds/2014-04-09/build.log [2] http://download.fpcomplete.com/ghc-7.8-builds/2014-04-09/logs.zip

3 4

Re: [Haskell-cafe] [Haskell] ANNOUNCE: GHC version 7.8.1
by Ketil Malde 10 Apr '14

10 Apr '14

Austin Seipp <austin(a)well-typed.com> writes: > The (Interactive) Glasgow Haskell Compiler -- version 7.8.1 Congrats! > * Massive scalability improvements to the I/O manager Just a brief note from the front lines - I recompiled a heavily threaded program with (a recent pre-release) of 7.8.1 and got a 10% performance increase over 7.6.3. Nothing like free lunches - so thanks again for the great work! -k -- If I haven't seen further, it is by standing in the footprints of giants

2 1

Haskell Weekly News: Issue 290
by Daniel Santa Cruz 10 Apr '14

10 Apr '14

Welcome to issue 289 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers from April 1 to 5, 2014 Quotes of the Week * edwardk: Zombies are expensive. Top Reddit Stories * foldl is broken! Domain: well-typed.com, Score: 148, Comments: 63 On Reddit: [1] http://goo.gl/LXmJTV Original: [2] http://goo.gl/viOG5O * A small Haskell extension Domain: augustss.blogspot.nl, Score: 76, Comments: 23 On Reddit: [3] http://goo.gl/buI46t Original: [4] http://goo.gl/LnAV9y * New GHC Features for 7.10.1 and Beyond Domain: haskell.org, Score: 74, Comments: 26 On Reddit: [5] http://goo.gl/DdXTfO Original: [6] http://goo.gl/g0FPBS * Libc considered harmful Domain: sylvain-henry.info, Score: 58, Comments: 28 On Reddit: [7] http://goo.gl/aq39Mf Original: [8] http://goo.gl/qdQDXm * Category Theory by Tom LaGatta Domain: youtube.com, Score: 58, Comments: 53 On Reddit: [9] http://goo.gl/oIzG1e Original: [10] http://goo.gl/DeLu5G * Idris 0.9.12 released with major laziness, codata, and documentation updates plus metavars in types Domain: idris-lang.org, Score: 55, Comments: 25 On Reddit: [11] http://goo.gl/4MtXJS Original: [12] http://goo.gl/3tXbqC * A cool paper I found on "Functional Programming and 3D Games". It discusses everything from collision detection to physics and texturing. [PDF] Domain: cse.unsw.edu.au, Score: 52, Comments: 3 On Reddit: [13] http://goo.gl/6PYB2e Original: [14] http://goo.gl/Tf6fa2 * Error reporting with locations Domain: augustss.blogspot.fr, Score: 47, Comments: 28 On Reddit: [15] http://goo.gl/ikaENm Original: [16] http://goo.gl/hntlJT * [ANN] Haste now has a website and a mailing list Domain: haste-lang.org, Score: 42, Comments: 7 On Reddit: [17] http://goo.gl/Ife2FA Original: [18] http://goo.gl/lRWmhv * Haskell in the Newsroom Domain: infoq.com, Score: 41, Comments: 5 On Reddit: [19] http://goo.gl/M4tehD Original: [20] http://goo.gl/bpvgLA * Haskell application architecture best practices Domain: self.haskell, Score: 32, Comments: 23 On Reddit: [21] http://goo.gl/XjHfNJ Original: [22] http://goo.gl/XjHfNJ Top StackOverflow Questions * Haskell - Is it possible to make pointfree functions more readable using different combinators than (.)? votes: 11, answers: 1 Read on SO: [23] http://goo.gl/5b036l * How to detect if a program has been compiled using -threaded? votes: 10, answers: 2 Read on SO: [24] http://goo.gl/Cr7pMA * What does the star mean in this haskell code? votes: 9, answers: 2 Read on SO: [25] http://goo.gl/qnolS7 * What about arrows? votes: 9, answers: 2 Read on SO: [26] http://goo.gl/b1wwp4 * Triggering a documentation update for a Hackage package votes: 8, answers: 1 Read on SO: [27] http://goo.gl/ErTVzf * Combining Data.Dynamic and type classes votes: 7, answers: 0 Read on SO: [28] http://goo.gl/n8qMo9 * Systematically applying a function to all fields of a haskell record votes: 6, answers: 3 Read on SO: [29] http://goo.gl/tNkLGu * Transforming a List of 2-Tuples in Haskell votes: 6, answers: 3 Read on SO: [30] http://goo.gl/dDe8QP * Error in ghci which I cannot reproduce in written haskell file votes: 6, answers: 1 Read on SO: [31] http://goo.gl/bg8DCw * Why can I call a monadic function without supplying a monad? votes: 6, answers: 1 Read on SO: [32] http://goo.gl/xZZ5iO * Deriving default instances using GHC.Generics votes: 6, answers: 1 Read on SO: [33] http://goo.gl/Autu6r Until next time, [34]+Daniel Santa Cruz References 1. http://www.well-typed.com/blog/90/ 2. http://www.reddit.com/r/haskell/comments/21wvk7/foldl_is_broken/ 3. http://augustss.blogspot.nl/2014/04/a-small-haskell-extension.html 4. http://www.reddit.com/r/haskell/comments/2239wh/a_small_haskell_extension/ 5. http://www.haskell.org/pipermail/haskell-cafe/2014-April/113373.html 6. http://www.reddit.com/r/haskell/comments/21wbme/new_ghc_features_for_7101_a… 7. http://sylvain-henry.info/blog/posts/2014-04-01-libc-considered-harmful.html 8. http://www.reddit.com/r/haskell/comments/220ae4/libc_considered_harmful/ 9. https://www.youtube.com/watch?v=o6L6XeNdd_k 10. http://www.reddit.com/r/haskell/comments/229scs/category_theory_by_tom_laga… 11. http://www.idris-lang.org/idris-0-9-12-released/ 12. http://www.reddit.com/r/haskell/comments/2284s5/idris_0912_released_with_ma… 13. http://www.cse.unsw.edu.au/~pls/thesis/munc-thesis.pdf 14. http://www.reddit.com/r/haskell/comments/21zush/a_cool_paper_i_found_on_fun… 15. http://augustss.blogspot.fr/2014/04/haskell-error-reporting-with-locations.… 16. http://www.reddit.com/r/haskell/comments/226otd/error_reporting_with_locati… 17. http://haste-lang.org/ 18. http://www.reddit.com/r/haskell/comments/21x4wm/ann_haste_now_has_a_website… 19. http://www.infoq.com/presentations/haskell-newsroom-nyt 20. http://www.reddit.com/r/haskell/comments/222i82/haskell_in_the_newsroom/ 21. http://www.reddit.com/r/haskell/comments/223i80/haskell_application_archite… 22. http://www.reddit.com/r/haskell/comments/223i80/haskell_application_archite… 23. http://stackoverflow.com/questions/22872098/haskell-is-it-possible-to-make-… 24. http://stackoverflow.com/questions/22839824/how-to-detect-if-a-program-has-… 25. http://stackoverflow.com/questions/22807728/what-does-the-star-mean-in-this… 26. http://stackoverflow.com/questions/22871648/what-about-arrows 27. http://stackoverflow.com/questions/22783637/triggering-a-documentation-upda… 28. http://stackoverflow.com/questions/22876370/combining-data-dynamic-and-type… 29. http://stackoverflow.com/questions/22807619/systematically-applying-a-funct… 30. http://stackoverflow.com/questions/22828259/transforming-a-list-of-2-tuples… 31. http://stackoverflow.com/questions/22839784/error-in-ghci-which-i-cannot-re… 32. http://stackoverflow.com/questions/22841899/why-can-i-call-a-monadic-functi… 33. http://stackoverflow.com/questions/22850983/deriving-default-instances-usin… 34. https://plus.google.com/105107667630152149014/about

1 0

www.galois.com' response to Heartbleed .... .
by Vasili I. Galchin 10 Apr '14

10 Apr '14

http://corp.galois.com/blog/2014/4/9/heartbleed-a-great-time-to-think-about… BTW I am always very careful when I use memcpy .. .hate that function ... read "buffer overrun" big time .....

1 1

Automatically infer Newtype instance
by Dmitry Bogatov 09 Apr '14

09 Apr '14

Hello! I think, that Newtype instances are transitive, and there is only one sane definiton is (pack . pack). But in example below I have to use UndecidableInstances and they seems to loop somewhere (Context reduction stack overflow; size = 132). To my understanding, Ghc tries to prove, that exists only one type b, and somewhy fail at it(It is unclear, why), but is it any way to say to it that I take responsibility, that ANY b would be nice? I know about TH, but interested in more elegant solution. {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-} import Control.Newtype newtype A1 = A1 Int deriving (Eq, Show) newtype A2 = A2 A1 deriving (Eq, Show) instance Newtype A1 Int where pack = A1 unpack (A1 a) = a instance Newtype A2 A1 where pack = A2 unpack (A2 a) = a -- Here comes UndecidableInstances instance (Newtype a b, Newtype b c) => Newtype a c where pack = pack . pack unpack = unpack . unpack main = let foo :: A2 foo = pack "46" in print foo -- Best regards, Dmitry Bogatov <KAction(a)gnu.org>, Free Software supporter, esperantisto and netiquette guardian. git://kaction.name/rc-files.git GPG: 54B7F00D

4 6