- Beginners - Haskell.org

Memoization
by Shawn Willden 28 Oct '09

28 Oct '09

Hi, I've just begun experimenting with Haskell, and I'm having a lot of fun, but my first semi-serious program is in need of some optimization, and based on the results of profiling I think a really good start is to memoize one particular function which is called many, many times (and currently consumes over 80% of the program run time). The function takes a two-dimensional range and a location within that range and returns a list of the locations vertically and horizontally adjacent to that location and within the bounds type Bounds = ((Int,Int),(Int,Int)) type Location = (Int,Int) adjacentCells :: Bounds -> Location -> [Location] adjacentCells bounds (col, row) = filter valid cells where valid loc = inRange bounds loc neighborLoc' = [(col-1,row),(col+1,row),(col,row-1),(col,row+1)] The ranges are fairly small -- certainly no more than 10x10, and each location has an associated list of at most 4 neighbors (edge locations have less). During a given run of the program, the bounds are fixed. So, any tips on how I can memoize this function? I have read the Memoization page on the wiki, and I understand (I think) the recursive memoization section, but it's not clear to me how to apply that approach. Section one on non-recursive memoization seems like what I want, but I don't understand the section and the links provided haven't shed any light for me. The section uses the following notation to describe how to construct a map to be used to hold the keys and values: Map () b := b Map (Either a a') b := (Map a b, Map a' b) Map (a,a') b := Map a (Map a' b) but I'm not sure what that notation is. It's not Haskell code, I don't think. Any and all suggestions appreciated. Thanks, Shawn.

2 1

Re: [Haskell-beginners] Chessboard Module, opinions on…
by iæfai 28 Oct '09

28 Oct '09

If I had a clock, I would consider it :P On 2009-10-28, at 11:20 AM, Darrin Thompson wrote: > On Wed, Oct 28, 2009 at 2:33 AM, iæfai <iaefai(a)me.com> wrote: >> The chess AI process is something I still have to hunt for mind >> you, but the >> part that is the most interesting is that I am going to be >> controlling a >> $50,000 robot with this in class :P. >> > > For $50k do you get a robot that can play a serious intimidating > blitz? Can it smack the clock with Class A player _authority_? :-) > > -- > Darrin

1 0

Fwd: [Haskell-beginners] Chessboard Module, opinions on…
by Andrew Wagner 28 Oct '09

28 Oct '09

---------- Forwarded message ---------- From: Andrew Wagner <wagner.andrew(a)gmail.com> Date: Wed, Oct 28, 2009 at 11:19 AM Subject: Re: [Haskell-beginners] Chessboard Module, opinions on… To: iæfai <iaefai(a)me.com> Ah, ok. You may also be interested in this protocol then: http://www.gnu.org/software/xboard/engine-intf.html . It's a widely-used standard for communication between chess AIs and UIs. On Wed, Oct 28, 2009 at 11:07 AM, iæfai <iaefai(a)me.com> wrote: > I am not making an AI, I am using an existing AI, so how I store it > internally will not be of consequence to it. > > - iæfai > > On 2009-10-28, at 8:00 AM, Andrew Wagner wrote: > > Just a note to let you know: it's virtually impossible to use a >> linked-list-of-linked-list or two-dimensional-array board representation as >> the basis of a serious AI. It's just too inefficient (see >> http://www.cis.uab.edu/hyatt/boardrep.html for some other options). >> >> That said, if you want to use this as the basis of being able to play >> through games or something, it's great. >> >> On Wed, Oct 28, 2009 at 2:11 AM, Joe Fredette <jfredett(a)gmail.com> wrote: >> Awesome, have you cabal-ized it? If not, it's pretty simple (look up >> 'cabal' on the haskellwiki). Then you can upload it to hackage to be toyed >> with. >> >> One thing that might be a cool direction to go w/ your project (sounds >> like you intend to make a chess playing program, this is somewhat orthogonal >> to that goal) is to build a "playback" machine. For instance, I play chess >> with people by email on a fairly regular basis. Specifically, we submit >> moves to one another in semi-standard[1] algebraic chess notation. So I >> might see a game like: >> >> >> 1. Kb3 e5 >> 2. d3 d6 >> ... >> n. a4->a5 e6->d7 >> >> Where the first move is White, moving his knight to B-3, then black moves >> his pawn from e7 to e5. etc. >> a move followed by a * is a check, followed by two stars is a mate. etc. >> You can poke at the wiki page for ACN for the appropriate syntax. My >> suggestion is that- often times we go many days in between moves, and so I >> don't keep track (in my head) of the last few moves he made, which can >> sometimes indicate weak points/general strategies. It would be _really_ nice >> to be able to replay old board positions at will, given this ACN notation of >> the game. Might be a nice (simple) use case for Parsec, and I imagine that >> most chess engines will have something like that (assuming they operate on >> STDIN/OUT) -- even if the syntax may be different. This will give you the >> "backend" to plug it onto anyway. >> >> Anywho, good luck with your project, it looks nice! >> >> /Joe >> >> PS, Just noticed the little function you use to display the board (and >> stuff). You may want to poke around the 2d Pretty printers on hackage, they >> may make it easier/more extensible to render the board. Also, `cout`? >> Someone's got a bit o' the ++ in 'em... :) >> >> >> >> [1] Okay, we mostly make it up, but it's _consistently_ arbitrary... >> >> >> >> On Oct 28, 2009, at 1:56 AM, iæfai wrote: >> >> >> I have just recently finished a 'ChessBoard' module that is meant to >> represent a chess board. I could use some opinions and/or suggestions on the >> module. >> >> To give an example of how this can be used right now, and was my immediate >> goal, you can do this: >> >> *ChessBoard> putStr $ cout defaultBoard >> +----+----+----+----+----+----+----+----+ >> | RB | NB | BB | QB | KB | BB | NB | RB | >> +----+----+----+----+----+----+----+----+ >> | PB | PB | PB | PB | PB | PB | PB | PB | >> +----+----+----+----+----+----+----+----+ >> | | | | | | | | | >> +----+----+----+----+----+----+----+----+ >> | | | | | | | | | >> +----+----+----+----+----+----+----+----+ >> | | | | | | | | | >> +----+----+----+----+----+----+----+----+ >> | | | | | | | | | >> +----+----+----+----+----+----+----+----+ >> | PW | PW | PW | PW | PW | PW | PW | PW | >> +----+----+----+----+----+----+----+----+ >> | RW | NW | BW | QW | KW | BW | NW | RW | >> +----+----+----+----+----+----+----+----+ >> >> I have not determined exactly how I will be making moves, but the logic >> will not be in my program. I am going to be using a chess engine in another >> process (I haven't chosen a chess engine yet that works on both windows and >> mac through stdin/stdout). >> >> The module itself follows, I appreciate any thoughts you might have. >> >> >> module ChessBoard where >> >> import Data.Sequence >> import Data.Foldable >> import Data.Maybe >> import Data.List as List >> >> class NiceLook a where >> cout :: a -> String >> >> >> data Piece = Bishop | Rook | Knight | King | Queen | Pawn | NoPiece >> deriving (Show, Eq) >> >> instance NiceLook Piece where >> cout Bishop = "B" >> cout Rook = "R" >> cout Knight = "N" >> cout Queen = "Q" >> cout Pawn = "P" >> cout King = "K" >> cout _ = " " >> >> data Colour = Black | White | NoColour >> deriving (Show, Eq) >> >> instance NiceLook Colour where >> cout Black = "B" >> cout White = "W" >> cout NoColour = " " >> >> -- error "..." might be useful >> >> data Square = Square Piece Colour >> deriving (Show, Eq) >> >> instance NiceLook (Square) where >> cout (Square p c) = (cout p) ++ (cout c) >> >> data Row = Row (Seq Square) >> deriving (Show, Eq) >> >> instance NiceLook (Row) where >> cout (Row s) = "|" ++ foldMap (\x -> " " ++ cout x ++ " |") s >> -- thnx Saizan >> >> makeRow n = case (List.length n) of >> 8 -> Row (fromList n) >> _ -> error "Row is not 8 squares" >> >> makeColouredSquares n c = makeRow $ map makeSquare (zip n (replicate 8 c)) >> >> makeSquare (n,c) = Square n c >> >> pawns = [Pawn, Pawn, Pawn, Pawn, Pawn, Pawn, Pawn, Pawn] >> back = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook] >> blank = [NoPiece, NoPiece, NoPiece, NoPiece, NoPiece, NoPiece, NoPiece, >> NoPiece] >> >> data Board = Board (Seq Row) >> deriving (Show, Eq) >> >> instance NiceLook (Board) where >> cout (Board c) = borderOutput ++ "\n" ++ (foldMap (\x -> cout x ++ "\n" >> ++ borderOutput ++ "\n") c) >> >> defaultBoard = Board (makeColouredSquares back Black <| >> makeColouredSquares pawns Black <| >> makeColouredSquares blank NoColour <| >> makeColouredSquares blank NoColour <| >> makeColouredSquares blank NoColour <| >> makeColouredSquares blank NoColour <| >> makeColouredSquares pawns White <| >> makeColouredSquares back White <| empty) >> >> >> borderOutput = "+" ++ (List.foldr1 (++) $ replicate 8 "----+") >> >> _______________________________________________ >> Beginners mailing list >> Beginners(a)haskell.org >> http://www.haskell.org/mailman/listinfo/beginners >> >> _______________________________________________ >> Beginners mailing list >> Beginners(a)haskell.org >> http://www.haskell.org/mailman/listinfo/beginners >> >> >

1 0

nim
by John Moore 27 Oct '09

27 Oct '09

Hi getting there with nimprogram well have it working in different areas. The last part is where the most trouble is import Control.Monad import System.Random initNim :: IO [Int] initNim = replicateM 3 $ randomRIO (1,10)--- This get the random numbers data PileName = A | B | C deriving (Show, Eq, Read) typeOfMove :: (PileName, Int) -> [Int] -> [Int] typeOfMove (A, x) xs = zipWith (-) xs [x,0,0] typeOfMove (B, x) xs = zipWith (-) xs [0,x,0] typeOfMove (C, x) xs = zipWith (-) xs [0,0,x] main :: IO () main = do putStrLn "Which pile A, B, or C ?" x <- readLn putStrLn "How many stones?" y <- readLn let z = typeOfMove (x,y) [9,9,9]-- cannot get the random numbers here putStrLn . show $ z *This is where the main problem is I 'm trying to run the game?* play nim = do z <- getLine newAnswer <- return (diff z) if newAnswer == [0,0,1]||[0,1,0]||[1,0,0] then putStrn "You win" else play nim newAnswer diff z ws hs =[ if z==w then w else h]-- trying to return different list here John

4 3

unix pkg on cygwin
by MH 27 Oct '09

27 Oct '09

I tried to use unix package on Cygwin and it didn't work. I found a far better solution, use Sun's VirtualBox from virtualbox.org. It runs a virtual OS on your host operating system and it works very well. I installed virtualbox on Windows host, and I am running Ubuntu inside virtualbox with Haskell on it. Works like charm. Vitualbox like VMWare, except it is free. Malik

1 0

Why is this type ambiguous?
by Maurício CA 26 Oct '09

26 Oct '09

import Foreign import Foreign.C genericCast :: (Storable a, Storable b) => a -> IO b genericCast v = let dummy = undefined size = max (sizeOf v) (sizeOf dummy) in if False then return dummy else allocaBytes size $ \p -> poke p v >> peek (castPtr p) ---- Code above gives me this: Ambiguous type variable `a' in the constraint: `Storable a' arising from a use of `sizeOf' at src/Bindings/C.hs:28:27-38 ---- It seems to refer to '(sizeOf dummy)'. But isn't the type of 'dummy' defined by 'return dummy' beeing a possible return value (and, so, dummy :: b)? Thanks, Maurício

3 4

Re: Built-in/more elegant version of this function?
by Jordan Cooper 26 Oct '09

26 Oct '09

Am Montag 26 Oktober 2009 18:49:51 schrieb Jordan Cooper: >> I was wondering if there is a built-in way to do what this function I >> wrote does (or at least a more elegant way, preferably without >> explicit recursion). >> >> f xss = map safeHead xss : f (map safeTail xss) >> >> (where safeHead/Tail are versions of head/tail that don't crash on [] >> input) > >Not quite the same, but > >Prelude> :m +Data.List >Prelude Data.List> transpose [[1,2],[],[3,4,5]] >[[1,3],[2,4],[5]] > >could be more or less what you want. Thank you, I think that will work nicely!

1 0

Built-in/more elegant version of this function?
by Jordan Cooper 26 Oct '09

26 Oct '09

I was wondering if there is a built-in way to do what this function I wrote does (or at least a more elegant way, preferably without explicit recursion). f xss = map safeHead xss : f (map safeTail xss) (where safeHead/Tail are versions of head/tail that don't crash on [] input)

2 1

nim
by John Moore 26 Oct '09

26 Oct '09

Hi All, In the game of nim I want to make a move such as take x from pile A. This will then be subtracted from the starting list.Is this correct in as much as I want to have a move Take 3 from pile A: input would be A3 I need it to return a list as I wish to take this result and use zipwith (-) [starting list][result]. How do I use the result, do I store in a variable? typeOfMove :: (a,b) -> [Int] typeOfMove ax |ax = [x,0,0] |bx = [0,x,0] |cx = [0,0,x] John

2 1

nim programme
by John Moore 25 Oct '09

25 Oct '09

Hi All, I'm attempting to write a program for the game nim.(The game of Nim is played with two players and several piles of stones. On each move a player removes as many stones as they would like but form only one pile. The player who takes the last stone wins) It not as simple as I first thought. Here is my basic starting points. Any comments would be greatly appreciated. I not well versed in Haskell yet so simple(basic) Haskell rather than well written haskell if you understand what I mean. Complicated monads are way out of my league. 1) I first get the program to give me three random piles by doing nim = do x <- getStdRandom $ randomR (1,10) y <- getStdRandom $ randomR (1,10) z <- getStdRandom $ randomR (1,10) return [x,y,z] Cant get this to work! 2) Now I need to get the program to ask for a number and which pile to remove the number from. This is tricky I thought about asking to find the elementAt elementAt :: [a] -> Int -> a elementAt list i = list !! (i-1) put this in a variable then asking the palyer how many to take away. and then subtracting the number from and then putting it back into the list but this seem impossible. Then the second player would do the same. 3) Finally we would end up with a case statement like f x = in case of x [0,0,1]-> You win [0,1,0]-> You win [0,0,1]-> You win [_,_,_]-> keep playing. Lets know what you think please, getting confused. John

5 5