August 2007 - Haskell-Cafe

Error building takusen with Cabal-1.1.6.2
by John Dell'Aquila 19 Aug '07

19 Aug '07

Setup.hs wants a module that Cabal hides. Am I doing something wrong (newbie :-) or should I try to fall back to Cabal-1.1.6.1? $ ghc --make -o setup Setup.hs Setup.hs:13:7: Could not find module `Distribution.Compat.FilePath': it is hidden (in package Cabal-1.1.6.2)

4 3

Sudoku Solver
by Adrian Neumann 18 Aug '07

18 Aug '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: RIPEMD160 Hi, I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out the first solution it finds. Why is it, that [0,0,0,7,0,6,9,0,0] [9,0,0,0,0,4,7,0,0] [7,0,0,0,0,0,4,0,0] [0,2,7,0,3,5,8,0,0] [6,9,5,8,2,0,0,0,0] [0,8,0,0,0,0,5,0,0] [0,3,0,0,0,0,0,0,0] [8,7,0,9,0,0,0,0,0] [0,0,0,0,0,0,0,0,0] is solved instantly, but when I remove just one number my program takes forever? === import Array import List import System type Field = Array Int (Array Int Int) isEmpty :: Int -> Bool isEmpty = (==) 0 done :: Field -> Bool done a = isFull a && checkField a isFull::Field -> Bool isFull a = notElem (0) $ (concat.(map elems).elems) a readField :: [[Int]]->Field readField = (listArray (1,9).map (listArray (1,9))) checkField :: Field -> Bool checkField a = check (rows a) && check (columns a) && check (squares a) where check b = and $ ((map ((==1).length)).concat.(map group).clean) b clean = map (dropWhile isEmpty.sort) columns::Field -> [[Int]] columns a = [[a!i!j|i<-[1..9]]|j<-[1..9]] rows :: Field -> [[Int]] rows a = [[a!i!j|j<-[1..9]]|i<-[1..9]] squares :: Field -> [[Int]] squares a = [[a!(i+n)!(j+m)|i<-[1..3],j<-[1..3]] |n<-[0,3,6],m<-[0,3,6]] - -- creates a list of all allowed entries genMoves :: Field -> [Field] genMoves a = concat [update a i j|i<-[1..9],j<-[1..9],isEmpty (a!i!j)] where update b i j= [b //[(i,b!i //[(j,x)])]|x<-[1..9], checkField (b //[(i,b!i //[(j,x)])])] play :: [Field] -> Maybe Field play (f:a) | done f= Just f | isFull f= play a | otherwise = play ((genMoves f)++a) play [] = Nothing main :: IO () main = do x <- getArgs let field = read (x!!0) :: [[Int]] let erg=play [readField field] case erg of Just a -> putStrLn $ concat $ map ((++"\n").show) (rows a) Nothing -> putStrLn "Es gibt keine Loesung" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGtx0r11V8mqIQMRsRA7P5AJ9lG3mF3fHpUiyOqCeRVOOEGozp1wCeI80C RfD/U5y+yEgF0fe+kRwDbUI= =Ngss -----END PGP SIGNATURE-----

9 14

Chessboard-building in Haskell
by Andrew Wagner 18 Aug '07

18 Aug '07

I've started a blog series on writing a chess engine in Haskell. I just posted the second blog entry today: http://sequence.complete.org/node/361 I suspect there's more work to be done on that function, though. It seems like there should be a nice way to remove that flip in apply. Any thoughts?

2 1

Re: Hints for Euler Problem 11
by ronguida＠mindspring.com 18 Aug '07

18 Aug '07

Thank you for all the hints. Here's how I ended up solving it: > module Main > where > > import Data.List > import Data.Maybe > > gridText = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\ > \49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\ > \81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\ > \52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\ > \22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\ > \24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\ > \32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\ > \67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\ > \24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\ > \21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\ > \78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\ > \16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\ > \86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\ > \19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\ > \04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\ > \88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\ > \04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\ > \20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\ > \20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\ > \01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" > type Grid a = [[a]] > readGrid :: (Read a) => String -> Grid a > readGrid = (map ((map read) . words)) . lines > grid :: Grid Integer > grid = readGrid gridText takeExactly - extract the first "n" elements of a list; there must be at least "n" elements, n > 0 > takeExactly :: (Monad m) => Int -> [a] -> m [a] > takeExactly n xs | n > 0 = > let ys = take n xs in > if length ys == n > then return ys > else fail "takeExactly: list is too short" > | otherwise = fail "takeExactly: empty list" > extractGroups :: Int -> [[a]] -> [[a]] > extractGroups n = catMaybes . map (takeExactly n) > gridExtractGroups :: Int -> Grid [a] -> Grid [a] > gridExtractGroups n = filter (not . null) . map (extractGroups n) gridTails - generate a list of grids with sequential starting places Parameters a and b determine the offset bewteen successive grids, as follows: (note that a, b may not be negative) Grid x_{0,1.., 0,1..} -> [ Grid x_{ 0, 1 .., 0, 1 ..} , Grid x_{ a, a+1 .., b, b+1 ..} , Grid x_{2*a, 2*a+1 .., 2*b, 2*b+1 ..} etc. ] > gridTails :: (Int, Int) -> Grid a -> [Grid a] > gridTails (a,b) xs = > if not $ null $ concat xs > then xs : gridTails (a,b) ((drop a) $ map (drop b) xs) > else [] transpose3d - converts x_{i,j,k} to x_{j,k,i} using sequence is x_{i,j,k} -> x_{j,i,k} -> x_{j,k,i} > transpose3d :: [Grid a] -> Grid [a] > transpose3d = map transpose . transpose reorient - transform a direction vector so that both components are non-negative > reorient :: (Int, Int) -> (Grid a -> Grid a, (Int, Int), Grid b -> Grid b) > reorient (a,b) > | a>=0 && b>=0 = (id , ( a, b), id) > | a< 0 && b>=0 = (reverse , (-a, b), reverse) > | a>=0 && b< 0 = (map reverse , ( a,-b), map reverse) > | a< 0 && b< 0 = (reverse . map reverse, (-a,-b), reverse . map reverse) makeEls - convert a grid to grid of Equidistant Letter Sequences > makeEls :: (Int, Int) -> Grid a -> Grid [a] > makeEls vec = let (reflect2, rvec, reflect1) = reorient vec in > reflect2 . transpose3d . gridTails rvec . reflect1 > getGroups :: Int -> (Int, Int) -> Grid a -> [[a]] > getGroups n (a,b) = concat . gridExtractGroups n . makeEls (a,b) > findMaxProduct :: (Ord a, Num a) => Int -> (Int, Int) -> Grid a -> a > findMaxProduct n (a,b) = maximum . map product . getGroups n (a,b) > main :: IO() > main = do > print $ findMaxProduct 4 (1,0) grid > print $ findMaxProduct 4 (0,1) grid > print $ findMaxProduct 4 (1,1) grid > print $ findMaxProduct 4 (1,-1) grid -- Ron

9 18

Bathroom reading
by Dougal Stanton 17 Aug '07

17 Aug '07

I'm looking for cool but mind-bending examples of functional brilliance. Let us say, hypothetically, you had a bathroom without any reading material. And having read all the Dilbert and Garfield you could seriously stomach, decide you should educate yourself while "on the job". :-) So you decide to print up some "one-liner" style programs into a little booklet. Something between credit-card and postcard sized, with a neat but mind-bending program on it. Don Stewart occasionally swoops in with some fixpoint malarkey to defuse heated discussions. I mean that kind of thing, but with a slightly wider scope than just fibs... Suggestions, please! D.

12 13

Re: [Haskell-cafe] monte carlo trouble
by Chad Scherrer 17 Aug '07

17 Aug '07

I'm using ListT now, trying to do this: type Sample a = ListT (State StdGen) a randomStreamR :: (RandomGen g, Random a) => (a,a) -> g -> ([a], g) randomStreamR bds g =(randomRs bds g1, g2) where (g1,g2) = split g sample :: [a] -> Sample a sample [] = ListT (State f) where f s = case next s of (_,s') -> ([],s') sample xs = do let bds = (1, length xs) xArr = listArray bds xs i <- ListT . State $ randomStreamR bds return $ (xArr ! i) -- Simple example, for testing main = mapM_ print . flip evalState (mkStdGen 1) . runListT $ do x <- sample [1..100] y <- sample [1..x] return (x,y) The abstraction seems much better now, but even the simple little example blows up in memory. Here's a snippet from profiling with -auto-all -caf-all (after I interrupted it): CAF:lvl4 Main 261 1 0.0 0.0 100.0 100.0 main Main 273 0 0.0 0.0 100.0 100.0 sample Main 274 1 100.0 100.0 100.0 100.0 randomStreamR Main 276 1 0.0 0.0 0.0 0.0 I'm wondering if the bind for ListT is still effectively building every possibility behind the scenes, and sampling from that. I could redo the Sample monad by hand, if that could be the problem, but I'm not sure what changes would need to be made. Or maybe it's building lots of different arrays and holding them for too long from the GC. Or maybe it's a strictness/laziness issue I'm missing. Still not so sure when I need case vs let/where. How would you guys going about tracking down the problem? Thanks, Chad On 8/15/07, Paul Johnson <paul(a)cogito.org.uk> wrote: > Chad Scherrer wrote: > > Thanks for your replies. > > > > I actually starting out returning a single element instead. But a > > given lookup might return [], and the only way I could think of to > > handle it in (State StdGen a) would be to fail in the monad. But > > that's not really the effect I want - I'd rather have it ignore that > > element. Another option was to wrap with Maybe, but then since I > > really want a sequence of them anyway, I decided to just wrap in a > > List instead. Is there a way Maybe would work out better? > Ahh. How about using ListT Gen then? That (if I've got it the right > way round) works like the list monad (giving you non-determinism), but > has your random number generator embedded as well. Take a look at "All > About Monads" at http://www.haskell.org/all_about_monads/html/. Each > action in the monad may use a random number and produce zero or more > results. > > Paul. > > >

2 1

defining last using foldr
by Alexteslin 17 Aug '07

17 Aug '07

Hi, I am trying to do the exercise which asks to define built-in functions 'last' and 'init' using 'foldr' function, such as last "Greggery Peccary" = 'y' the type for my function is: myLast :: [Char] -> Char I am not generalizing type so that make it less complicated. But what ever i am trying would not work. The only function type foldr takes as an argument is either (a->a->a) or (a->b->b) and none of the functions i found that would match this type from Char to Char. So in other words should be (Char->Char-Char). I can define the function without foldr but that misses the point of the exercise. Any hint will be appreciated, Thank you -- View this message in context: http://www.nabble.com/defining-last-using-foldr-tf4269357.html#a12151145 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

8 22

What to do about an absent package maintainer?
by Adam Langley 17 Aug '07

17 Aug '07

The HsOpenSSL package[1] is good work, but the author doesn't respond to email(*). I've a bunch of darcs patches to add tests, DSA support and fast Integer <-> BIGNUM functions. Can I use my Hackage account to upload version 0.2 if someone else uploaded 0.1? It is reasonable? I'm guessing that this issue will start to occur more often now that we have Hackage. It's probably good to have some policy. Cheers, (*) It's been > 1 month, with emails from several different addresses. [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsOpenSSL-0.1 -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org

1 0

Re: [Haskell-cafe] Remember the future
by Andrew Coppin 17 Aug '07

17 Aug '07

Gwern Branwen wrote: > On 0, Andrew Coppin <andrewcoppin(a)btinternet.com> scribbled: > >> I've seen comments in various places that monads allow you to "borrow >> things from the future". >> >> That sounds completely absurd to me... can anybody explain? >> > > Take a look at issue 6 of The Monad Reader; search for time travel. <http://www.haskell.org/haskellwiki/The_Monad.Reader> > Mmm... yes... I've read this before. It didn't make any sense then either. (The example is too big and complicated. It obscures the thing it's trying to illustrate...)

1 0

GHC linking problems
by SevenThunders 17 Aug '07

17 Aug '07

I have a large Haskell/C project that needs to be linked against an even larger set of C libraries and object files (OpNet) on a linux box (Fedora Core 7). So far I have been able to link my Haskell libraries to some C test code containing a main function without incident. However the link flags are very complex having been extracted from ghc. (e.g. it requires a host of -u flags and then a bunch of links to external C libraries including a long list of Haskell libraries.) Unfortunately control over the OpNet compilation and linking process is weak at best. Moreover it is not clear how the linking occurs and there is some suspicion that it ultimately creates a dynamic link library which it loads from some external process (the exact calls to gcc are hidden). During the OpNet build we get the following error /usr/lib/ghc-6.6.1/libHSrts.a(Main.o): In function `main': Main.c:(.text+0x22): undefined reference to `__stginit_ZCMain' Main.c:(.text+0x43): undefined reference to `ZCMain_main_closure' collect2: ld returned 1 exit status I do not get this error when statically linking my libraries to a standalone C function containing a main() function. What should I look for? Are there known work arounds to this problem? It's troubling that exporting Haskell to C should be this problematic. Unfortunately I can not use ghc to compile the OpNet code as you might imagine. -- View this message in context: http://www.nabble.com/GHC-linking-problems-tf4270650.html#a12155220 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 5