- Beginners - Haskell.org

For most geometric algorithms (e.g. Graham Scan) sorting the points & not using trig functions is usually better.
by KC 09 Jan '12

09 Jan '12

Often you sort the points to find a boundary point (extremal point). Using trig functions burns a lot of CPU cycles so if one can use the inner product, etc. so much the better. -- -- Regards, KC

1 0

Imperfect Graham Scan
by Zhi-Qiang Lei 08 Jan '12

08 Jan '12

Hi, The Graham Scan function I wrote, looks like running well. But when I put it in QuickCheck, it just failed in some case. Anyone can show me some clues about the problem? Thanks. When I test it in ghci with some example, it returns the right result. *Main> let xs = [Point {x = 1.0, y = 1.0},Point {x = 0.0, y = 4.0},Point {x = 0.0, y = 6.0},Point {x = 3.0, y = 5.0},Point {x = 4.0, y = 4.0},Point {x = 4.0, y = 1.0},Point {x = 3.0, y = 3.0},Point {x = 2.0, y = 2.0},Point {x = 5.0, y = 5.0}] *Main> grahamScan xs [Point {x = 1.0, y = 1.0},Point {x = 4.0, y = 1.0},Point {x = 5.0, y = 5.0},Point {x = 0.0, y = 6.0},Point {x = 0.0, y = 4.0}] *Main> grahamScan it [Point {x = 1.0, y = 1.0},Point {x = 4.0, y = 1.0},Point {x = 5.0, y = 5.0},Point {x = 0.0, y = 6.0},Point {x = 0.0, y = 4.0}] However, QuickCheck find some points which can fail it. Could it be a data type overflow problem? prop_scan_idempotent xs = not (null xs) ==> (grahamScan . grahamScan) xs == grahamScan xs *Main> quickCheck prop_scan_idempotent *** Failed! Falsifiable (after 13 tests and 4 shrinks): [Point {x = -6.29996952110807, y = -91.37172300100718},Point {x = 9.353314917365527, y = 64.35532141764591},Point {x = -23.826685687218355, y = 60.32049750442556},Point {x = -1.4281411275074123, y = 31.54197550020998},Point {x = -2.911218918860731, y = 15.564623822256719}] === code === module GrahamScan (grahamScan, Point(..)) where import Data.List import Data.Ratio data Point = Point { x :: Double, y :: Double } deriving (Eq, Show) instance Ord Point where compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2) data Vector = Vector { start :: Point, end :: Point } deriving (Eq) cosine :: Vector -> Double cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) instance Ord Vector where compare a b = compare (f a) (f b) where f = negate . cosine sort' :: [Point] -> [Point] sort' xs = pivot : fmap end sortedVectors where sortedVectors = sort . fmap (Vector pivot) . delete pivot $ xs pivot = minimum xs counterClockwise :: Point -> Point -> Point -> Bool counterClockwise (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) > (y2 - y1) * (x3 - x1) scan :: [Point] -> [Point] scan (p1 : p2 : p3 : xs) | counterClockwise p1 p2 p3 = p1 : scan (p2 : p3 : xs) | otherwise = scan (p1 : p3 : xs) scan xs = xs grahamScan :: [Point] -> [Point] grahamScan = scan . sort' . nub === code === Best regards, Zhi-Qiang Lei zhiqiang.lei(a)gmail.com

6 6

Parse error in pattern
by Zhi-Qiang Lei 07 Jan '12

07 Jan '12

Hi, I am writing a Graham Scan function. What puzzles me is it cannot be compiled. Does anyone know what is wrong with "scan"? Thanks. ==== compile ==== bogon% ghc GrahamScan.hs -- NORMAL -- [1 of 1] Compiling Main ( GrahamScan.hs, GrahamScan.o ) GrahamScan.hs:30:1: Parse error in pattern: scan ==== compile ==== ==== code ==== data Point a = Point { x :: a, y :: b } instance Ord (Point a) where compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2) data Vector a = Vector { start :: Point a, end :: Point a } cosine :: Vector a -> Ratio a cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) instance Ord (Vector a) where compare a b = compare (f a) (f b) where f = negate . cosine sort' :: [Point a] -> [Point a] sort' xs = minPoint : fmap end sortedVectors where sortedVectors = sort $ map (Vector minPoint) $ delete minPoint xs minPoint = minimum xs ccw :: Point a -> Point a -> Point a -> Bool ccw (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) > 0 scan :: [Point a] -> [Point a] scan p1 : p2 : p3 : xs | ccw p1 p2 p3 = p1 : scan (p2 : p3 : xs) | otherwise = scan (p1 : p3 : xs) scan xs = xs grahamScan :: [Point a] -> [Point a] grahamScan = scan . sort' ==== code ==== Best regards, Zhi-Qiang Lei zhiqiang.lei(a)gmail.com

2 2

Programming GTK
by gabre＠caesar.elte.hu 06 Jan '12

06 Jan '12

Hello! I am writing a turtle graphics program in Haskell. Now, I am working on the GUI (Gtk2HS). I am a newbie, I have never programmed event driven systems. I have a Button, and when it is clicked the code written in a a TextView is drawn in a DrawingArea. There are some problems: when "Expose event" happens (I dont really know, if I use the right words, but I mean, when another window is in focus, or another window comes before the turtle graphics window etc.) my drawing disappears (I know, it is the normal behaviour). I would like to redraw it, but I dont know, how. I have a function with events... connectGui gui = do onDestroy (mainWin gui) mainQuit onClicked (btn gui) (drawProgram gui) afterActivateLeaf (quitbtn gui) (widgetDestroy (mainWin gui)) (where gui is a record, containing all the GUI elements, such as the buttons) ...but the drawProgram function draws everything, and if I add the "onExpose" with the same drawing function, everything is redrawn although the Button was never clicked before. So I would like to modify the code: -if the button was already clicked and redraw is needed, then it should be done -if the button was never clicked, then there must be no redraw Could you tell me, how can I do this? Gabre

1 0

Re: [Haskell-beginners] Beginners Digest, Vol 43, Issue 4
by Gregory Guthrie 05 Jan '12

05 Jan '12

Thanks - I did try a cabal install xxx" for the missing packages, a few seemed to succeed, a few failed, and now I get a longer list of overall failures! :-) ... There are problems in package scion-0.1.0.9: dependency "AttoJson-0.5.10-4932e72997280d8c2e35b4aca3328284" doesn't exist dependency "binary-0.5.0.2-72c84eaab351d41e936261d8d5d416f5" doesn't exist dependency "list-tries-0.4.1-a2fcbc51b309eb5aade37b40c6ef166e" doesn't exist There are problems in package bytestring-show-0.3.4: dependency "binary-0.5.0.2-72c84eaab351d41e936261d8d5d416f5" doesn't exist There are problems in package carray-0.1.5: dependency "binary-0.5.0.2-72c84eaab351d41e936261d8d5d416f5" doesn't exist dependency "ix-shapable-0.1.0-68747ed518a0145d47f8095a08e0bcbb" doesn't exist ... The following packages are broken, either because they have a problem listed above, or because they depend on a broken package. warp-0.4.6.3 tagsoup-0.12.3 simple-sendfile-0.2.0 blaze-builder-enumerator-0.2.0.3 scion-0.1.0.10 aeson-0.3.2.11 hashable-1.1.2.1 blaze-textual-0.2.0.4 double-conversion-0.2.0.1 derive-2.5.4 hoogle-4.2.6 warp-0.4.3 wai-0.4.1 simple-sendfile-0.1.2 http-types-0.6.5.1 case-insensitive-0.3.0.1 blaze-builder-enumerator-0.2.0.2 bmp-1.1.2.1 scion-0.1.0.9 bytestring-show-0.3.4 carray-0.1.5 unordered-containers-0.1.4.2 I tried an install (reinstall?) of the things it lists as missing, and generally they report "already installed". For example; >cabal install AttoJson Resolving dependencies... No packages to be installed. All the requested packages are already installed. If you want to reinstall anyway then use the --reinstall flag. (same for binary, list-tries, ix-shapable, ...) >ghc --version The Glorious Glasgow Haskell Compilation System, version 7.0.3 Some things do seem to resolve after a few iterations through re-installations, but others seem stuck, and overall the process seems like a mess. > What is the remedy (is there a simple remedy?) if "ghc-pkg check" reports something amiss? > > In this case, the simple remedy is to reinstall the packages which the error messages say do > not exist (blaze-builder, hashable, AttoJson) and then reinstall any packages you want to use > which depend on them. > > -Brent

1 0

Re: [Haskell-beginners] WinRT and Haskell
by Antoine Latter 05 Jan '12

05 Jan '12

On Thu, Jan 5, 2012 at 9:55 AM, AbdulSattar Mohammed <codingtales(a)gmail.com> wrote: > WinRT has a concept of projections that expose its API. Microsoft has > implemented projections for Native (C and C++), HTML/Javascript and .NET > (from Miguel de Caza's WinRT demystified > post: http://tirania.org/blog/archive/2011/Sep-15.html) There's no mention > of creating your own projections (or I have seen none). I don't see any > reason why we can't create our own projections. If it's possible a Haskell > projection could really help. > Yep, that's what I was thinking of. I'm pretty sure the C/C++ projections rely on compiler extensions for the MS C/C++ compiler, so I don't think we could use those directly from Haskell. Antoine > > On Thu, Jan 5, 2012 at 8:11 PM, Antoine Latter <aslatter(a)gmail.com> wrote: >> >> On Thu, Jan 5, 2012 at 5:12 AM, AbdulSattar Mohammed >> <codingtales(a)gmail.com> wrote: >> > I suppose this should go into the GUI mailing list, but it is filled >> > with >> > spam. So, WinRT does not depend on the .NET Framework. C++ applications >> > can >> > directly compile to x86 and be able to use WinRT. Do we have a room for >> > Haskell development there? >> > >> >> From what I understand, WinRT is a set of COM libraries - C++ can >> directly compile to it because the MS C++ compiler has special >> extensions to handle the COM resources in the library. >> >> There is a COM library for Haskell: >> >> http://hackage.haskell.org/package/com >> >> But I've never used it. >> >> The API is encoded in a special meta-data format, which is then used >> by C++, .NET and Javascript to create the language-specific APIs - it >> might be possible to generate Haskell bindings to the COM components >> from this metadata. >> >> Antoine > > > > > -- > Warm Regards, > > AbdulSattar Mohammed

1 0

WinRT and Haskell
by AbdulSattar Mohammed 05 Jan '12

05 Jan '12

I suppose this should go into the GUI mailing list, but it is filled with spam. So, WinRT does not depend on the .NET Framework. C++ applications can directly compile to x86 and be able to use WinRT. Do we have a room for Haskell development there? -- Warm Regards, AbdulSattar Mohammed

2 1

suggestions for optimizing sudoku solver
by Peter Hall 05 Jan '12

05 Jan '12

I set myself a learning task of writing a sudoku solver. (https://github.com/peterjoel/sudoku/blob/master/src/Sudoku.hs) It works pretty well, but struggles with some of the harder grids. e.g. data/hard4.txt and data/hard5.txt take around 18 seconds to solve. Obviously there's a limit, but I feel like I should be able to make this faster. I think the main issue is reading/writing to the cells in the grid, since (!!) is O(n). Even though it never has to go beyond index 8, it will add up over the millions of times it has to do it. I imagine it could be a lot faster if I use a static, non-list data structure, but I was hoping to keep it a bit more flexible. Also, I'm struggling to get started with performance profiling. Can someone point me to some good resources? Peter

3 5

Heathrow to London from lyahgg - infinite loop
by Siddharth Karandikar 04 Jan '12

04 Jan '12

Hi all, I am trying out Heathrow to London problem given in Learn You a Haskell book. There is optimization tip given by author to avoid computing priceA = sum $ map snd pathA every time. I was trying to implement that like following - roadStep :: (Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int) roadStep (pathA, pathB, cA, cB) (Section a b c) = let forwardPriceToA = cA + a crossPriceToA = cB + b + c forwardPriceToB = cB + b crossPriceToB = cA + a + c (newPathToA, cA) = if forwardPriceToA <= crossPriceToA then ((A, a):pathA, forwardPriceToA) else ((C, c):(B, b):pathB, crossPriceToA) (newPathToB, cB) = if forwardPriceToB <= crossPriceToB then ((B, b):pathB, forwardPriceToB) else ((C, c):(A, a):pathA, crossPriceToB) in (newPathToA, newPathToB, cA, cB) But whenever I run this function - roadStep ([], [], 0, 0) (Section 50 10 30) its going in infinite loop! I am not able to figure out whats causing this .. any thoughts? Thanks, Siddharth

2 2

Haskell platform confusing to me
by Manfred Lotz 03 Jan '12

03 Jan '12

Hi all, I have 2 questions regarding Haskell platform. 1. If I would like to install the newest Haskell platform on say Ubuntu Precise which is in the making I could proceed like follows: - install all dep packges from http://packages.ubuntu.com/precise/haskell-platform which means I would manually have to download all debs and install them thereafter. Is this true? 2. I have Ubuntu Lucid and like to install the newest Haskell platform. Do I have to build it from source? I didn't find any (big picture) documentation telling me how the installation pathes possibly are. As can be seen I'm pretty confused how to proceed. -- Manfred

4 5