- Haskell-Cafe - Haskell.org

Fun with Haskell, runST, MArray, and a few queens.
by David Sankel 05 Mar '04

05 Mar '04

Hello Enthusiasts, My fiancee was assigned the n-queens problem in her Data Structures class. It was a study in backtracking. For those unfamiliar with the problem: one is given a grid of n x n. Return a grid with n queens on it where no queen can be attacked by another. Anyway, I decided to try an implementation in Haskell (as I often do with her assignments). Instead of the imperative approach (adding a queen and then getting rid of it), I opted for a functional one (the grid is passed to recursive calls, etc.). The interesting thing about this assignment is the runtimes: (n=10) ghc 58.749s ghc -O 12.580s javac 1.088s The Haskell version takes significantly longer (and it gets worse for larger inputs). So it seems that imperative algorithms are much better for certain problems. Since Haskell is supposed to have the ability to run imperative algorithms, I was wondering if any of you could explain how runST and MArray could be used to solve this problem (or is there a better way?). I am also interested in the run times you get with these two implementations of the n-queens problem. David module Main where import Array import Maybe boardSizeToTest = 10 main = print $ fromJust $ solution (emptyBoard boardSizeToTest) boardSizeToTest --The Board datatype. A n x n array indexed starting with 1. data Board = Board Int (Array (Int,Int) Int) deriving Eq instance Show Board where show (Board n b) = concat [ (printLine b a) ++ "\n" | a <- [n,n-1..1] ] where printLine board row = concat [ (str (board ! (row,a))) | a <- [1..n] ] str (-1) = "q" --It's a queen str 0 = "." --It's an empty spot str a = show a --It's a spot that can be attacked by a queen --Helper function from Gentle Introduction to Haskell mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b mkArray f bnds = array bnds [(i, f i) | i <- range bnds] --Another helper function to update arrays (/-) :: (Ix a) => Array a b -> [(a, (b -> b))] -> Array a b (/-) array s = array // (map (\ (a, f) -> (a,f (array!a))) s) --An empty chessboard emptyBoard :: Int -> Board emptyBoard n = Board n $ mkArray (\_->0) ((1,1),(n,n)) --Adds a queen to the board and adds 1 in all the positions the queen --could feasible move. addQueen :: Board -> (Int,Int) -> Board addQueen b@(Board n board) c = Board n $ newBoard // [(c, -1)] where Board _ newBoard = queenHelper b (+1) c --Removes a queen from the board and subtracts 1 in all the positions the queen --could have feasible moved. removeQueen :: Board -> (Int,Int) -> Board removeQueen b@(Board n board) c = Board n $ newBoard // [(c, 0)] where Board _ newBoard = queenHelper b ((-)1) c queenHelper :: Board -> (Int->Int) -> (Int, Int) -> Board queenHelper (Board n board) f (row,column) = Board n $ board /- horizontal /- vertical /- negPosDiag /- posNegDiag /- negNegDiag /- posPosDiag where vertical = [ ((r,column),f) | r <- [1..n] ] horizontal = [ ((row,c),f) | c <- [1..n] ] negPosDiag = [ ((row-i,column+i),f)| i <- [1..(min (n-column) (row-1))]] posNegDiag = [ ((row+i,column-i),f)| i <- [1..(min (column-1) (n-row))]] negNegDiag = [ ((row-i,column-i),f)| i <- [1..(min (column-1) (row-1))]] posPosDiag = [ ((row+i,column+i),f)| i <- [1..(min (n-column) (n-row))]] --Returns all the positions on the board that do not have a queen and cannot --be attacked by a queen already on the board. possiblePositions (Board n board) = filter (\a -> board ! a == 0) [ (row,column) | row <- [1..n], column <- [1..n] ] --Finds a solution given a board and a number of queens to put on it solution :: Board -> Int -> Maybe Board solution board 0 = Just board solution board i = let solutions = catMaybes $ [ solution (addQueen board c) (i-1) | c <- (possiblePositions board) ] in if solutions == [] then Nothing else Just $ head solutions

5 5

[Haskell-cafe] Re: Fun with Haskell, runST, MArray, and a few queens. (Imperative Haskell Version)
by David Sankel 05 Mar '04

05 Mar '04

> I say this is a case of bad code. Of course language <foo> is faster and > better if you write horribly bad code in language <bar>. > Taking the first solution found by searching with google I get times > around 0.015s (real) for the Haskell version and 1.7s for your Java > solution (which also seems to be overcomplicated to me). That's cool. Although the java algorithm is beyond any doubt overcomplicated, I'd like to reproduce it using Haskell's imperative constructs because not all backtracking algorithms have a simple closed form solution. What I've done using monads is a little better in speed, but not the huge improvement I was expecting. Any comments as to what I'm doing wrong here? Updated Table: ghc�� 58.749s ghc -O�� 12.580s ghc -O (monad version) 8.284s javac�� 1.088s David module Main where import Control.Monad.ST import GHC.Arr import Maybe import Ix main = print $ runST something n = 10 -- Used only for output data Board = Board Int (Array (Int,Int) Int) deriving Eq instance Show Board where show (Board n b) = concat [ (printLine b a) ++ "\n" | a <- [n,n-1..1] ] where printLine board row = concat [ (str (board ! (row,a))) | a <- [1..n] ] str (-1) = "q" --It's a queen str 0 = "." --It's an empty spot str a = show a --It's a spot that can be attacked by a queen --Finds a solution given a board and a number of queens to put on it solution board 0 = return True solution board i = do possibleP <- (possiblePositions board) trySolution possibleP where trySolution [] = return False trySolution (c:cs) = do addQueen board c good <- solution board (i-1) if good then return True else do removeQueen board c trySolution cs --Returns all the positions on the board that do not have a queen and cannot --be attacked by a queen already on the board. -- possiblePositions board = -- do -- p <- sequence [ readSTArray board (row,column) >>= -- (\a -> return (a == 0,(row,column))) -- | row <- [1..n], column <- [1..n] ] -- return $ map (\(_,b)->b) $ filter (\(a,_)-> a) p possiblePositions board = do -- let indices = range $! boundsSTArray board let indices = [ (row,column) | row <- [1..n], column <- [1..n] ] p <- sequence $ map (\i -> readSTArray board i >>= (\a -> if a == 0 then return $ Just i else return Nothing )) indices -- return $ map (\(_,b)->b) $ filter fst p return $ catMaybes p arrayToBoard board = do it <- sequence [ readSTArray board (a,b) >>= (\s -> return ((a,b),s)) | a <- [1..n], b <- [1..n] ] return (Board n (array ((1,1),(n,n)) it)) emptyBoard = newSTArray ((1,1),(n,n)) 0 something = do board <- emptyBoard solution board n arrayToBoard board --Adds a queen to the board and adds 1 in all the positions the queen --could feasible move. addQueen b c = do queenHelper b (+1) c writeSTArray b c (-1) --Removes a queen from the board and subtracts 1 in all the positions the queen --could have feasibly moved. removeQueen b c = do queenHelper b (\a -> a - 1) c writeSTArray b c 0 --Helper function to update arrays (/-) array s = do sequence_ [ readSTArray array b >>= \n -> writeSTArray array b $! (c n) | (b,c) <- s ] return array queenHelper board f (row,column) = do board /- (horizontal ++ vertical ++ negPosDiag ++ posNegDiag ++ negNegDiag ++ posPosDiag) where vertical = [ ((r,column),f) | r <- [1..n] ] horizontal = [ ((row,c),f) | c <- [1..n] ] negPosDiag = [ ((row-i,column+i),f)| i <- [1..(min (n-column) (row-1))]] posNegDiag = [ ((row+i,column-i),f)| i <- [1..(min (column-1) (n-row))]] negNegDiag = [ ((row-i,column-i),f)| i <- [1..(min (column-1) (row-1))]] posPosDiag = [ ((row+i,column+i),f)| i <- [1..(min (n-column) (n-row))]]

1 0

Instance Problem
by 98222＠oa.cmbchina.com 05 Mar '04

05 Mar '04

How can I do this: class M a where tok::a->String instance M String where tok s="String" instance Num a=>M a where tok n="Number" instance (for all other types a)=>M a where tok x="Other"

1 0

State Monad
by Georg Martius 04 Mar '04

04 Mar '04

Hi folks, I have a question to the State Monad or Monads in general - I'am not sure. Lets assume I have functions to transform strings. I can use the State Monad as follows: strTrans :: String -> String strTrans s = s ++ s f :: State String () f = do put "hallo" modify strTrans modify strTrans' ... Up to this point everything is clear. Now I have also functions to map from (a, String) -> (a,String). I could write: modifyT :: ((a, String) -> (a, String)) -> a -> State String a modifyT trans a = do str <- get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put "hallo" modify strTrans i <- modifyT strIntTrans 4 -- strIntTrans :: (Int, String) -> (Int, String) i' <- modifyT strIntTrans i ... But this is obviously awkward. How can I stick two Monads in each other? I could't figure out how to use StateT. Any help would be appreciated. Thanks! Georg

4 4

a rant from a stoned suicidal person
by Chris Moline 04 Mar '04

04 Mar '04

i want to start off by apologizing. im lonely. i dont know anyone. anyone at all who is liek me. im different. everyone else is content to just watch tv all the time and then on weekends go and get drunk. im not. i am not threatening anything here when i say waht i am about to say. i know that waht i am about to say is not appropriate for haskell-cafe. i know this. but this needs to be said. im going to kill myself not right now. no you dont need to do anything. this is a plea. im begging you. ok see here im on my knees. my not-stoned self is going to hate me for this. but he needs the help and i know hes going to forgive me. because im him:) isnt that funny? i have no friends. none at all. im surrounded by motherfucking idiots *IDIOTS* i dont hate them. ok, im lying i hate them. i hate you. i hate this mothierfucking list. all i want is a goddamned friend who is *like me* i like thinking about shit. i like philosophy and math and all that stuff. dont suggest going to college. im sorry but ive found this out the hard way. im a loser. im a motherfucking loser. im too lazy. i have difficulty speling nad pronoundni big words. i do drugs. i know everyone says drugs are bad, but i like them. deal with it however you wnat. sned me to jail if you feel the need to. because i dont care anymroe do you hera that? I DONT FUCKING GIvE A ShIT ANYMORE im going to kill myself. i must. do you why i must? because im going insane. im surrounded by people but im completey alone. I HAVE NO IONE TO TAlK TO I AM LOSER I MUST DIE because im a loser so i am sendign this mesage to this list even though none of you care. none of you wnat ot deal with my problems. thats fine. i respect that. but i have noone and i cant find anyone and so i am begging PLEASE PUT ME OUT OF MY FUCKI*NG MISERY SHOOT ME * chris is crying * so anyways i am sorry for bothering you with this incoherent message but hers your mesage for the day FUCK YOU!

2 1

Re: [Haskell-cafe] State Monad
by Wolfgang Jeltsch 04 Mar '04

04 Mar '04

Am Mittwoch, 3. März 2004 18:15 schrieb Georg Martius: > Thanks for your answer. I got it now. > It works with lift instead of liftM. Yes, of course. > Georg Wolfgang

1 0

Trouble with [in,string]char* with hdirect
by Vincenzo aka Nick Name 03 Mar '04

03 Mar '04

Hi all, I am experimenting with hdirect for the first time, and I can't figure out how to call an haskell function of type String -> IO Int from C. I already can compile and use a function of type Char -> IO Int, so I assume to be using the right command line arguments. I have, in Math.idl ---- module Math { int munlink([in,string]char *s); }; ---- in Math.hs ---- module Math where munlink :: String -> IO Int munlink s = putStr ("Hey!" ++ s ++ "\n") >> return (-1) ---- This is the generated .hs file: module MathProxy where import Prelude (fromEnum, toEnum) import qualified Prelude import qualified Foreign.Ptr (Ptr) import qualified HDirect (unmarshallString) import qualified Math (munlink) munlink_proxy :: Prelude.String -> Prelude.IO Prelude.Int munlink_proxy = wrap_munlink Math.munlink foreign export ccall "munlink" munlink_proxy :: Foreign.Ptr.Ptr Prelude.String -> Prelude.IO Prelude.Int wrap_munlink :: (Prelude.String -> Prelude.IO Prelude.Int) -> Foreign.Ptr.Ptr Prelude.String -> Prelude.IO Prelude.Int wrap_munlink munlink_meth s = do s <- HDirect.unmarshallString s munlink_meth s I get a type error when compiling MathProxy.hs, and the strange thing is that commenting out the type declaration for "munlink_proxy" makes my program work like a charm. Errors from the compiler follow, any help will be highly appreciated. Vincenzo Ciancia ghc -O2 -fglasgow-exts Math.hs -c ihc -fshow-idl-in-comments -s -fhs-to-c --gen-headers -fuse-ints-everywhere -c Math.idl ghc -O2 -c main.c -o main.o ghc -O2 -fglasgow-exts -package hdirect MathProxy.hs -c MathProxy.hs:15: Couldn't match `GHC.Ptr.Ptr GHC.Base.String' against `GHC.Base.String' Expected type: GHC.Base.String -> GHC.IOBase.IO GHC.Base.Int Inferred type: GHC.Ptr.Ptr GHC.Base.String -> GHC.IOBase.IO GHC.Base.Int In the application `wrap_munlink Math.munlink' In the definition of `munlink_proxy': munlink_proxy = wrap_munlink Math.munlink MathProxy.hs:17: Couldn't match `GHC.Base.String' against `GHC.Ptr.Ptr GHC.Base.String' Expected type: GHC.Ptr.Ptr GHC.Base.String -> GHC.IOBase.IO GHC.Base.Int Inferred type: GHC.Base.String -> GHC.IOBase.IO GHC.Base.Int When checking declaration: foreign export ccall "munlink" munlink_proxy :: GHC.Ptr.Ptr GHC.Base.String -> GHC.IOBase.IO GHC.Base.Int

1 0

[Haskell-cafe] ITCC 2004, April 5 -7 2004 - Call For Participation, Las Vegas, USA
by jolly＠egr.unlv.edu 29 Feb '04

29 Feb '04

My apologies if this is a duplicate email. CALL FOR PARTICIPATION - ITCC 2004 http://www.itcc.info International Conference on Information Technology- ITCC 2004 is going to be held in Las vegas, NV USA.ITCC is an international forum which brings together researchers and practitioners working on different aspects of Information Technology. It is a technical congregation where the latest theoretical and technological advances on Information Technology are presented and discussed. This year's conference will bring together the world's most respected authorities on Information Retrieval, Operating Systems, Networks,Image/Video Processing, Digital Library, Coding & Data Compression,Watermarking, Simulation, Computer Graphics, Information Technology: Education, Curriculum & Accreditation, Information/Website Security, Data Mining and plethora of IT related technologies.(Pls check the advanced Program at our website). Whether you are a speaker, tutorial presenter, and/or sponsor, you will find ITCC 2004 as the best forum to share and demonstrate your knowledge with the depth and breadth of Information Technology.For registration details,Visit our Website http://www.itcc.info/ Any questions/Comments may be forwarded to it(a)egr.unlv.edu We look forward to your participation and hope to see you in Las Vegas! If you do not wish to be included in this list, and/or do not wish to receive further announcements regarding ITCC, please reply at jolly(a)egr.unlv.edu Your email address will be removed immediately from the distribution list. With Best Regards Vasu Jolly The ITCC 2004 Conference Secretary

1 0

Outstanding context : (Num b, Random b)
by "horsh 27 Feb '04

27 Feb '04

Hi, I am very new to haskell. Could anyone please explain why these two things are not equivalent: m2 = do a <- (drawInt 1 10) print a drawInt :: Int -> Int -> IO Int drawInt x y = getStdRandom (randomR (x,y)) m1 = do b <- getStdRandom (randomR (1,10)) print b the second one produces *** Binding : m1 *** Outstanding context : (Num b, Random b) in Hugs. thanks horsh

3 2

Perl-ish =~ operator
by ozone＠algorithm.com.au 24 Feb '04

24 Feb '04

In my effort to turn Haskell into a language more like Perl (muahaha)[1], I got a bit fed up and implemented something like Perl 5's =~ binding operator (a.k.a. "regex" operator); I thought maybe somebody else here might find it useful. Perl has the concept of 'contexts': a function does something different depending on what type its caller expects back from the function. Sounds like a perfect abuse of type classes, to me :). Code follows: --- {-# OPTIONS -fglasgow-exts #-} {- Need this for "instance Foo [String]" declarations -} module PLRE where -- Perl-Like Regular Expressions import Text.Regex -- Perl-Like =~ operator, which changes behaviour depending on its calling -- context class RegExContext a where (=~) :: String -> String -> a instance RegExContext Bool where s =~ re = case matchRegex (mkRegex re) s of Nothing -> False Just x -> True instance RegExContext [String] where s =~ re = case matchRegex (mkRegex re) s of Nothing -> [] Just x -> x boolContextTest string regEx = case string =~ regEx of True -> print True False -> print False stringListContextTest string regEx = case string =~ regEx of (a:x) -> print ("First match: " ++ a) _ -> error "No subexpression matches" --- Some test output for you: *PLRE> boolContextTest "foo" "^f" True *PLRE> boolContextTest "foo" "^g" False *PLRE> stringListContextTest "foo" "^(.)" "First match: f" *PLRE> stringListContextTest "goo" "^(.)" "First match: g" *PLRE> stringListContextTest "" "^(.)" *** Exception: No subexpression matches Note that you have a fairly severe restriction if you want to use =~ in your code: the Haskell compiler must be able to determine a concrete type for the context that =~ is used in. i.e. if stringListContextTest was defined as: stringListContextTest string regEx = case string =~ regEx of (a:x) -> print a _ -> error "No subexpression matches" The compiler can't concretise a type for 'a', and it'll complain about not having an instance for RegExContext [a] (which is fair enough). Even with this restriction, I'm sure it'll still be useful. It shouldn't be a bit leap to define other Perl-ish operators in this fashion, such as !~, or even s/.../. Have the appropriate amount of fun! 1. Actually, I wanted to turn Haskell into a language more suitable for text processing, but that doesn't sound as evil. -- % Andre Pang : trust.in.love.to.save

3 5