March 2004 - Haskell-Cafe

[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 03 Mar '04

03 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