October 2009 - Beginners

Circular Linked Lists
by Matthew J. Williams 04 Feb '10

04 Feb '10

Dear All How would one mimic, in Haskell, a C++ circular linked list i.e., where the last element precedes (points to) the first? Sincerely Matthew J. Williams

10 20

Class definition syntax
by Shawn Willden 01 Nov '09

01 Nov '09

I have a program that makes use of various data types built on top of Arrays. In some cases, they're data types that contain an Array plus some additonal information, in others, they're just "newtype" Arrays, so that I can use typechecking to make sure that I'm not using the wrong kind of object. I'd really like to define an "ArrayOps" class with all of the operations I need, and define instances for all of the specific types. I also use some "raw" Array objects, so it would be even better if I could make an instance of my class for Array. And, ideally, I'd like to use the Array operations for my class operations. So, I want something like: class ArrayOps a where (!) :: a -> i -> e (//) :: a -> (i,e) -> a bounds :: a -> (i,i) range :: a -> [i] 'i' and 'e' are the index and element types, respectively. Obviously, the signatures above reference type variables that aren't declared, and really must be constrained to be the 'i' and 'e' that were used in building the type 'a' (which is an Array i e). Something like the following (though this obviously doesn't work): class ((Array.Array i e) a) => ArrayOps a where ... I'm sure there must be a way to do this, but I can't figure out what the syntax would look like. Thanks, Shawn.

3 9

Ord [] instance
by Keith Sheppard 01 Nov '09

01 Nov '09

the compare function for lists seems to be work like (leaving off class details): > compare [] [] = EQ > compare [] _ = LT > compare _ [] = GT > compare (x:xt) (y:yt) = case x `compare` y of > EQ -> xt `compare` yt > _ -> x `compare` y I poked around to see if I could find where this was defined in the spec or if it was an implementation specific thing (I need to be able to rely on this definition across implementations). I found this text in the report: -- Lists data [a] = [] | a : [a] deriving (Eq, Ord) -- Not legal Haskell; for illustration only Is this basically saying the same thing as my compare definition? Thanks Keith -- keithsheppard.name

2 2

hierarchy of modules
by Michael Mossey 01 Nov '09

01 Nov '09

I want to have a hierarchy of modules for a local project. Not submitting it to Hackage yet. I just want to refer to my local modules as Basics.CSound Basics.Node Algo.Fux etc. how does one set this up? Thanks, Mike

4 5

list monad question
by Matthias Guedemann 31 Oct '09

31 Oct '09

Hi, a friend of mine wanted to write function (in Perl) that creates all tuples of length 3 of the elements of a given list, e.g. [(0,0,0),(0,0,1),(0,0,2),...,(5,5,5)] for the list [0..5]. Trying to get better at Haskell, I wrote a small function using the list monad for this (tuples replaced with lists) all3 ls = do a <- ls b <- ls c <- ls return [a,b,c] Now I want to make it capable to create all combinations of length n instead of fixed length 3 (that's why list instead of tuple), but I don't really see how. As the do notation translates to ls >>= \a -> etc. I thought it should be possible to have some sort of "foldr (>>=)" over a list of length n, but I can't figure out how to collect the variable number of results in a list for the "return". Any hints for that? best regards Matthias -- __________________________________________________________ ___ __ __ Dipl. Inf. Matthias Guedemann / __\/ _\ /__\ Computer Systems in Engineering / / \ \ /_\ Otto-von-Guericke Universitaet Magdeburg / /___ _\ \//__ Tel.: 0391 / 67-19359 \____/ \__/\__/ __________________________________________________________

7 16

beginner question
by Luca Ciciriello 31 Oct '09

31 Oct '09

Hi all. Just a very basic question. I need to write a function str2lsts :: String -> [[String]] in order to transorm a string like: "\"1\",\"cat\",\"dog\"§\"2\",\"duck\",\"goose\"" in the list of lists: [["1","cat","dog"],["2","duck","goose"]] I've tried to mix recursion, pattern matching and list comprehension, but the obtained result was embarrassing complex (> 20 lines of awful code). I think that a more simple solution certainly exists. Thanks in advance for any idea. Luca _________________________________________________________________ Download Messenger onto your mobile for free http://clk.atdmt.com/UKM/go/174426567/direct/01/

4 4

Chessboard Module, opinions on…
by iæfai 29 Oct '09

29 Oct '09

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 "----+")

6 14

Memoization
by Shawn Willden 29 Oct '09

29 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 29 Oct '09

29 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 29 Oct '09

29 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