- Haskell-Cafe - Haskell.org

Haskell shootout game
by Hugh Perkins 17 Jul '07

17 Jul '07

Had an idea: a real shootout game for Haskell. The way it would work is: - you email a haskell program to a specific address - it shows up on a web-page The webpage shows the last submitted solution for each person - anyone can select two solutions and click "Fight" -> the scripts "fight" in an arena for a second or so, and the results are published to the website The arena itself comprises: - a 2d grid, of a certain size (or maybe variable size) - each grid cell can be a wall, or one of the opponents - the boundaries of the grid are walls - random blocks of wall are placed around the grid The opponents only perceive what is in a section of space to their front, in a 45 degree arc from either side of the direction they are facing - each player can face along one of the four grid axes Each player takes it in turns to move - at each move the player can: - move one square - turn 90 degrees, in either direction - fire Firing will score one point if the opponent is in the line of fire at that time, and there are no intervening walls. Opponents can see the direction the other opponent is facing, as long as the other opponent is in their view arc, and there are no intervening walls. Each turn is represented by a function something like: doturn :: String -> [[GridValue]] -> (Action,String) -- [[GridValue]] is a map of what Me sees this turn, or has seen previously -- the Strings are a way for the function to pass state to itself between moves data GridValue = Opponent | Me | Wall | Empty data Action = Fire | MoveNorth | MoveSouth |MoveEast | MoveWest | TurnLeft | TurnRight | Wait -- (players can move backwards and sideways) The turn would be run as a separate thread, which either terminates successfully, or is aborted after a fixed time x milliseconds (maybe 10 milliseconds?) The String that doturn produces at the end of a turn is passed back in at the beginning of the next turn (so one could use gread/gshow to serialize/deserialize arbitrary data types, and there is no limitation on what data can be stored in the state). After say 1000 turns, the results are the points of each script. (or we could give each script a number of "lives" and if its loses them all the other script wins outright) This can run on a hosted webserver probably, because each match is part of a webpage request, and lasts a maximum of about a second, so shouldnt be terminated prematurely by cpu-monitoring scripts.

10 10

Ann: Emping 0.3
by Hans van Thiel 17 Jul '07

17 Jul '07

Hello All, Version 0.3 of Emping is available. Emping is a utility that reads a table in a csv (comma separated) format that can be generated from Open Office Calc (spreadsheet), derives all shortest rules for a selected attribute, and writes them to a .csv file that can be read by OO Calc. The shortest rules may be partially ordered by implication (entailment) and equivalence (equality) and the top level is also shown in .csv format. Optionally all logical entailments and equalities are listed as well. If the data set contains ambiguous rules or more occurrences of the same rule, the user is warned. The main difference with V0.2 is that v0.3 can now handle intermediate size files (100 to a few thousand rules) because the transformation of conjunctive form (ands of ors) to disjunctive (ors of ands), which seemed to be exponential in the number of rules, has been optimized by using an intermediate 'maybe tree'. Probably I also used the wrong fold, without strictness, in the prior version, but it would still have been exponential. I 'think' it's now closer to linear to the number of rules, and quadratic to the number of attributes. But tests show the completion time is highly dependent on how well the data is structured. Obviously, much has still to be done. More info, for those who are interested, on http://j-van-thiel.speedlinq.nl/emp/empug.html Thank you, Hans van Thiel

1 0

Why does Data.Map exist when...
by Tony Morris 17 Jul '07

17 Jul '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 ...it seems to be a special case of Set? Does Data.Map add anything more useful than Map' below? import Data.Set as Set newtype MyPair a b = MP (a, b) deriving Show instance (Eq a) => Eq (MyPair a b) where MP (a, _) == MP (a', _) = a == a' instance (Ord a) => Ord (MyPair a b) where MP (a, _) `compare` MP(a', _) = a `compare` a' type Map' k a = Set (MyPair k a) - -- Tony Morris http://tmorris.net/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGnDgEmnpgrYe6r60RAu4FAJ93Fwcx7ZX08+qO4ZlzRVV52TXpNQCeNr7u ioq0XrWt/Wymfh52W1spiFk= =FC5h -----END PGP SIGNATURE-----

5 4

-O2 compile option can give speed increase over -O. Fasta shootout program test runs.
by Richard Kelsall 17 Jul '07

17 Jul '07

I have been playing with the Fasta program in the shootout to see if I can make it umm faster. Starting from dons program on this page and adding some timing calculations as suggested on this wiki page http://shootout.alioth.debian.org/gp4/benchmark.php?test=fasta&lang=ghc&id=2 http://www.haskell.org/haskellwiki/Timing_computations I added different OPTIONS into the top line of the program did a ghc --make fasta.hs and ran it each time with fasta 2500000 (This is one tenth of the shootout figure.) These runs all keep the existing OPTIONS of -fbang-patterns -fexcess-precision Seconds OPTIONS Added ------- ------------- 40.5 40.5 -funbox-strict-fields 40.4 {-# INLINE rand #-} 17.2 -O 17.0 -O -fvia-C 14.4 -O -optc-march=pentium4 11.5 -O2 11.2 -O3 11.5 -O3 {-# INLINE rand #-} 11.3 -O2 -optc-march=pentium4 There was a bit of variation, I've averaged over two runs. This is on an Intel Pentium D 2.66GHz running W2K and GHC 6.6.1. It seems the -O2 option can give a significant speed increase relative to just the -O option. This is contrary to the documentation which says http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise.ht… http://www.haskell.org/ghc/docs/latest/html/users_guide/faster.html it won't make any difference. I guess it's program, architecture and operating system specific, but according to these figures the -O2 option seems well worth a try for programs that need speed. It may be that we sacrifice bounds checking or something important with -O2, I don't know. Richard.

5 4

Re: hMapping polymorphic functions
by oleg＠pobox.com 17 Jul '07

17 Jul '07

hMapping polymorphic functions is indeed quite challenging, but can be done. That was the topic of the message Type-class overloaded functions: second-order typeclass programming with backtracking http://okmij.org/ftp/Haskell/poly2.txt The challenge is how to avoid specifying the context too early or at all and keep the context to the bare minimum. Your particular case is simple however: applying the function (\x->[x]) that applies literally to any argument type and is defined only by one case: > data FnListify = FnListify > > instance TypeCast [a] r => Apply FnListify a r where > apply _ x = typeCast [x] > > list1 = 'a' :*: "a" :*: True :*: HNil > test1 = hMap FnListify list1 *Poly2> test1 "a" :*: (["a"] :*: ([True] :*: HNil)) Within the Poly2 framework, the example becomes > data FnListify = FnListify > > instance TypeCast Otherwise r => GFN n FnListify a r > instance TypeCast [a] r => Apply (GFnA n FnListify) a r where > apply _ x = typeCast [x] > > instance TypeCast [a] r => Apply FnListify a r where > apply _ x = typeCast [x] > > test2 = hMap (GFn FnListify) list1 *Poly2> test2 "a" :*: (["a"] :*: ([True] :*: HNil)) The advantage of making things more complicated than they are is that we can add more clauses to our generic function. For example, we may choose to handle Booleans in a different way, by negating them. We add (perhaps in a different module, so the original code remains as it was) > data OnlyBool > instance TypeCast OnlyBool r => GFN Z FnListify a r > instance Apply OnlyBool Bool HTrue > instance TypeCast HFalse r => Apply OnlyBool a r > > instance Apply (GFnA Z FnListify) Bool Bool where > apply _ x = not x and now, *Poly2> test2 "a" :*: (["a"] :*: (False :*: HNil)) P.S. It may be worth sending me a carbon copy (CC) of any question relating to HList, OOHaskell, continuations, etc. I can no longer afford reading every message on Haskell-Cafe (or even every tenth message).

1 0

A really bad way to say "all isSpace"
by Neil Mitchell 17 Jul '07

17 Jul '07

Hi, Reading through the code to read: read s = case [x | (x,t) <- reads s, ("","") <- lex t] of [x] -> x [] -> error "Prelude.read: no parse" _ -> error "Prelude.read: ambiguous parse" Reading through the code to lex, it appear that it will return [("","")] if and only if all isSpace t. If this is really the case, does it make sense to state all isSpace t? It has a much clearer meaning to me. Thanks Neil

2 2

Haskell for categorists
by Miguel Mitrofanov 17 Jul '07

17 Jul '07

Just being curious. There are a lot of tutorials ensuring the reader that, although Haskell is based on category theory, you don't have to know CT to use Haskell. So, is there ANY Haskell tutorial for those who do know CT? I don't need it, personally, but still...

6 5

More on improving the mailing list
by dons＠cse.unsw.edu.au 17 Jul '07

17 Jul '07

An interesting study on problem resolution and feedback on some technical mailing lists, "How to Help Mailing Lists Help Readers (Results of Recent Data Analysis) " http://praxagora.com/andyo/professional/mailing_list_follow_up/ including graphs! :) With conclusions at the end on how to improve mailing lists by /integrating material into wikis/, and providing both theoretical and practical advice for a given problem. -- Don

1 0

ANNOUNCE: CC-delcont-0.1; Delimited continuations for Haskell
by Dan Doel 17 Jul '07

17 Jul '07

Hello, After a bit of hacking, and much documenting, I'm pleased to announce a preliminary release of a delimited continuation library for Haskell. The implementation is drawn from "A Monadic Framework for Delimited Continuations"[1] by Dybvig, Petyon Jones and Sabry, although it has some abstraction available over said implementation (there is both a monad and a transformer; control operations will work interchangeably with either. In addition, all four control operators from "Shift to Control"[2] are implemented). In addition, I have done the adaptation necessary to include the Haskell implementation of the dynamic scoping investigated in "Delimited Dynamic Binding"[3] by Kiselyov, Shan and Sabry, and it has been included. One can think of it as embeddings of the reader or state monads into the delimited control monads (only more flexible). In the future, I'd like to also, possibly, include something like Oleg's generic zippers, and possibly other useful abstractions based on delimited continuations, if I find them. But that's work for another day, I suppose. If you wish to try it out, a package is available on hackage: Page: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/CC-delcont-0.1 Tabrall: http://hackage.haskell.org/packages/archive/CC-delcont/0.1/CC-delcont-0.1.t… However, I should warn that it's fairly dependent on GHC HEAD at the moment: 1) It uses the Unsafe.Coerce module 2) It uses GADTs to store type class evidence 3) It uses GHC-features that haddock will choke on, so haddock.ghc will be required for docs (and I haven't gotten that working yet to check that the haddock is bug-free), which in turn requires GHC HEAD. 1 & 2 could be relaxed if there's interest. Please feel free to let me know if you find any bugs, or have any suggestions for improvements. I'll follow up this message with a message containing an example program and a discussion thereof. Cheers, Dan Doel 1: http://www.cs.indiana.edu/~sabry/papers/monadicDC.pdf 2: http://www.cs.rutgers.edu/~ccshan/recur/recur.pdf 3: http://okmij.org/ftp/papers/DDBinding.pdf

1 2

problem with IO, strictness, and "let"
by Michael Vanier 16 Jul '07

16 Jul '07

I stumbled across a problem with IO and strictness that I could fix, but I can't understand why the fix works. I've compressed it down into a program which simply computes the number of lines in a file. Here is a version that doesn't work: module Main where import System.IO import System.Environment process_file :: FilePath -> IO () process_file filename = do h <- openFile filename ReadMode c <- hGetContents h let cs = unlines $ lines c hClose h putStrLn $ show $ length cs main :: IO () main = do args <- getArgs process_file (args !! 0) This will return a length of 0 lines for any input file. Obviously, the "let" is not being evaluated strictly (nor would we expect it to be), so that when the evaluation is requested, the file is already closed and the length of the list of lines is 0 (though I might have expected an error). I then tried this: process_file :: FilePath -> IO () process_file filename = do h <- openFile filename ReadMode c <- hGetContents h let cs = id $! lines c -- try to strictly evaluate the let binding hClose h putStrLn $ show $ length cs which also failed exactly as the previous version did (i.e. always returning 0). Then I gave up on "let" and did this: process_file :: FilePath -> IO () process_file filename = do h <- openFile filename ReadMode c <- hGetContents h cs <- return $! lines c hClose h putStrLn $ show $ length cs This works. However, I don't understand why this version works and the previous version doesn't. Can anyone walk me through the evaluation? Also, is there a way to make "let" strict? TIA, Mike

12 19