January 2012 - Beginners

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

04 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

Haskell and TimeZones
by Thiago Negri 03 Jan '12

03 Jan '12

Hi, How does Haskell handle TimeZone? Do I need to use Oslon to have a historical database of TimeZones in Haskell? I tried reading the package description and everything, but it seems complicated. Is there any easy to follow tutorial available? For example, here in Brazil the daylight savings rules change every year. How do I update the Haskell Data.Time.* packages to know of the new rules? Or does it uses the TimeZone database from O.S.? I'm looking for a solution that works in any platform (mac, linux, windows). Thanks, Thiago.

2 1

Fundamentals of List Comprehension and Recursion
by Cody Haberkorn 02 Jan '12

02 Jan '12

Hi all, I high school programmer and just started learning Haskell. Haskell so far seems to be an awesome language. I began reading "Learn you Haskell for a Great Good!" I am confused with list comprehension, as I am coming from an imperative programming language (Java). From my understanding, list comprehension is synonymous to Java's for-loop and what not. For example: let xs = [1,2,3,4,5] [x | x <- xs] I believe it is saying that "bound x to xs, and do (print) x." Another example: let rightTriangles' = [ (a,b,c) | c <- [1..10] , b <- [1.. c], a <- [1.. b], a^2 + b^2 == c^2, a+b+c == 24] ghci > rightTriangles' [(6 ,8 ,10)] I believe it is saying "store c with the numbers 1-10, b is length of c, and a is the length of b. Print the answer (a,b,c) which satisfies a^2 + b^2 == c^2, a+b+c == 24. It may seem that I am answering my own question, but when it becomes more complicated or I am ask to do specific tasks that involves list comprehensions, I do not know how to read or compose one. Second, can someone do a line by line breakdown of this code? The book does a sub-par job explaining it. -- Creating our own sum function sum ' :: (Num a) => [a] -> a sum ' [] = 0 sum ' (x:xs) = x + sum ' xs Summed up: How did you learn Haskell and how long did it take before you became competent? This is my second day and I am already running into problems. I have to re-read things where as Java it came easy to me. Any book or tutorials? Can someone explain list comprehension and my recursion code? Thanks, - Cody p.s The questions so far have been over my head (is this a " true beginner's email list"?), I'll try to answer what I can.

2 1

ghc-pkg
by Gregory Guthrie 02 Jan '12

02 Jan '12

What is the remedy (is there a simple remedy?) if "ghc-pkg check" reports something amiss? ------------------------------------------- C:\Users>ghc-pkg check There are problems in package hoogle-4.2.6: dependency "blaze-builder-0.3.0.1-157e8a92bc5ef27895f938613ecfdcb1" doesn't exist There are problems in package warp-0.4.3: dependency "blaze-builder-0.3.0.1-157e8a92bc5ef27895f938613ecfdcb1" doesn't exist There are problems in package wai-0.4.1: dependency "blaze-builder-0.3.0.1-157e8a92bc5ef27895f938613ecfdcb1" doesn't exist There are problems in package http-types-0.6.5.1: dependency "blaze-builder-0.3.0.1-157e8a92bc5ef27895f938613ecfdcb1" doesn't exist There are problems in package case-insensitive-0.3.0.1: dependency "hashable-1.1.2.1-25dfe4e720b096d06d0cf57f76c49caf" doesn't exist There are problems in package blaze-builder-enumerator-0.2.0.2: dependency "blaze-builder-0.3.0.1-157e8a92bc5ef27895f938613ecfdcb1" doesn't exist There are problems in package scion-0.1.0.9: dependency "AttoJson-0.5.10-4932e72997280d8c2e35b4aca3328284" doesn't exist The following packages are broken, either because they have a problem listed above, or because they depend on a broken package. hoogle-4.2.6 warp-0.4.3 wai-0.4.1 http-types-0.6.5.1 case-insensitive-0.3.0.1 blaze-builder-enumerator-0.2.0.2 scion-0.1.0.9

2 1

Re: [Haskell-beginners] suggestions for optimizing sudoku solver
by Ray Song 02 Jan '12

02 Jan '12

An array with destructive updates (IO/ST) may help. You can also look into the exact cover problem and dancing links. If I recall correctly, this problem can be transformed to a 729*324 matrix. 在 2012-1-3 上午8:10，"Peter Hall" <peter.hall(a)memorphic.com>写道：

1 0

Audio packages
by Sourabh 02 Jan '12

02 Jan '12

Thanks for the reply. I will give wxHaskell a shot for the audio. Any ideas on how to resolve #2? > Finally, I have started getting this error every time I do a cabal install now: > Setup.hs:1:8: > Could not find module `Distribution.Simple': > Use -v to see a list of the files searched for. > 2. What should I do to get cabal to start installing stuff again?

2 4

Re: [Haskell-beginners] suggestions for optimizing sudoku solver
by Peter Hall 02 Jan '12

02 Jan '12

Thanks, It was really just an exercise that I'd set myself, and I wouldn't buy a book just for that. But, you're second person to recommend it to me, and it should have some good insight that will help me think the right way about other problems, so I've ordered it. Any other more general comments about my code? Peter On Mon, Jan 2, 2012 at 11:01 PM, Michael Serra <mk.serra(a)gmail.com> wrote: > This book by Richard Bird covers optimizing a Sudoku solver with equational > reasoning, along with quite a few other algorithms. > > On Sun, Jan 1, 2012 at 9:27 PM, Peter Hall <peter.hall(a)memorphic.com> wrote: >> >> 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 >> >> _______________________________________________ >> Beginners mailing list >> Beginners(a)haskell.org >> http://www.haskell.org/mailman/listinfo/beginners > >

1 0

Testing the water
by Cody Haberkorn 01 Jan '12

01 Jan '12

A little unsure of how this works, but we'll see! Thanks, - c

2 1