- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] RE: ANN: System.FilePath 0.9
by Brian Smith 17 Jul '06

17 Jul '06

Hi Neil, On 7/17/06, Neil Mitchell <ndmitchell(a)gmail.com> wrote: > > Hi Brian, > > You sent this email just to me, and not to the list. If you indended > to send to the list then feel free to forward my bits on to the list. > > > > I know that FilePath is defined by Haskell '98 as a String and so it > cannot > > be changed. So, perhaps a new type or class should be created for this > > library (hereafter "GoodPath," although I am not suggesting that is the > best > > name). > The problem is people will have to marshal their data into this > GoodPath, and marshal it out again. When people can shortcut that > marshalling, as the current readFile/writeFile definitions ensure they > can, they will. At that point you loose all safety because people will > abuse it. I disagree. It would be trivial to create a new module that exported new definitions of file IO actions that operated on "GoodPath" instead of "FilePath," transparently delegating to the original readFile/writeFile/etc. until they could be removed in the future. This would also support the "SuperFilePath" idea you mentioned. Another thing I thought of would be a "canonicalPath" IO action (canonicalPath :: FilePath -> IO FilePath) that returns a FilePath that implements case-preserving-case-insensitive matching. For example, if there is a file named "Hello There.txt" in C:\, then (canonicalPath "c:\hello there.txt ") would give "C:\Hello There.txt"). I think that the xxxDrive functions should only be exported from System.FilePath.Windows and no System.FilePath since it is unclear as to how they should be used effectively by cross-platform software. - Brian

2 1

process simulation in functional style
by Alexander Vodomerov 17 Jul '06

17 Jul '06

Hello! I'm writing a program that simulates multiple processes. The processes may send/receive messages, do some work, or sleep for some amount of time. I have seen that many such things can be expressed in Haskell in very elegant manner using it functional or lazy properties. For example, client/server interaction may be expressed via inifinite lists as shown in "Gentle Introduction to Haskell". Another way of process simulation is describied in http://citeseer.ist.psu.edu/harcourt95extensible.html, where simple and concise CCS interperter is constructed. I've tried to apply the idea of infinite lists or CCS-style processes, but fail. The main reason is that: 1) messages are asynchronous (it may be received and handled while process are sleeping, without waking them) 2) in some cases received message may wake up process 3) all activity in system is ordered by time 4) there are >2 process and during simulations new processes may be created I've no idea how to implement 1, 2 in CCS interpeter. The approach of infinite lists seems to have problems with 3, 4. Have somebody any ideas how this can be solved in simple and concise way? With best regards, Alexander. PS. Currently I have some code (see below), but it is VERY UGLY. The main drawback is that is very "imperative". It employs notion of "Global state". It doesn't use features of Haskell and can be rewritten in ML or C++ without changes. Another flaws is that it is very unextensible, and all processes must have the same state. -- example code latency = 0.001 type Message = String type MsgM = WriterT [(Int, Message)] IO -- process may send messages -- process states next id = (id + 1) `mod` 3 type State = (Int, Int, Double) -- proc. number, counter, interval do_step :: State -> MsgM (Double, State) --- do something and then sleep do_step (id, cnt, delay) = do tell [(next id, "ping " ++ show id ++ " cnt " ++ show cnt)] return (delay, (id, cnt + 1, delay)) handle_message :: Message -> State -> MsgM State handle_message msg (id, cnt, delay) = do -- liftIO $ putStrLn $ show id ++ " received msg " ++ msg if msg !! 0 == 'p' then tell [(next id, "reply " ++ show id ++ " to " ++ msg)] else return () return (id, cnt, delay) -- global event queue data Event = MsgRecv Message | Work deriving Show type EventQueue = [(Double, Int, Event)] compare_event (t1, n1, e1) (t2, n2, e2) = compare t1 t2 type EventM = WriterT EventQueue IO queue_event :: Int -> Event -> Double -> EventM () queue_event dest ev time = tell [(time, dest, ev)] type FullState = Map.Map Int State handle_event :: Int -> Double -> Event -> FullState -> EventM FullState handle_event procnum time ev fullstate = do let localstate = (fullstate Map.! procnum) case ev of MsgRecv msg -> do (nstate, messages) <- lift $ runWriterT (handle_message msg localstate) sequence_ $ map (\(dst, msg) -> queue_event dst (MsgRecv msg) (time + latency)) messages return $ Map.insert procnum nstate fullstate Work -> do ((pause, nstate), messages) <- lift $ runWriterT (do_step localstate) sequence_ $ map (\(dst, msg) -> queue_event dst (MsgRecv msg) (time + latency)) messages queue_event procnum Work (time + pause) return $ Map.insert procnum nstate fullstate run_queue :: FullState -> EventQueue -> IO () run_queue st eventqueue = case eventqueue of [] -> return () (time, dest, ev) : rest -> do putStrLn $ "processing event " ++ (showFFloat (Just 3) time) "" ++ " at procnum " ++ show dest ++ " " ++ show ev (nst, nev) <- runWriterT (handle_event dest time ev st) let nqueue = foldl (\res -> \e -> insertBy compare_event e res) rest nev run_queue nst nqueue init_state = Map.fromList [(0, (0, 0, 0.3)), (1, (1, 0, 0.4)), (2, (2, 0, 0.5))] main = run_queue init_state [(0, 0, Work), (0, 1, Work)]

3 2

Unix gurus, help me please
by Bulat Ziganshin 17 Jul '06

17 Jul '06

Hello gurus :) i got message about problems compiling Streams 0.2.1 library on Unix systems: - I include file io.h, but this particular system has "sys/io.h" instead. I think that i should solve this problem by including HsBase.h which should include proper io.h on any system supported. One more question is whether this HsBase.h will be available on non-GHC platforms, including Hugs, yhc, jhc? - Michael Stone (which reported all these problems) suggests to use #!/usr/bin/env runhaskell instead of #!/usr/bin/runhaskell at the start of Setup.hs file. Is that really better? - mingw supports _commit operation which (as i guess) saves to disk buffers of given file. Is that true that regular unixes has fsync function to perform the same action? (and what the hell MS don't use the same name??) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

4 6

Re: Breaking cycles in a directed graph.
by C Rodrigues 16 Jul '06

16 Jul '06

I ran across this problem a while ago, working on identifying edges in dependence cycles for software pipelining. The problem you want to solve is known as the "minimum feedback arc set" problem and is NP-hard. In my case, I could use other knowledge about the problem domain to find a good approximate solution. I'll refer you to the Wikipedia article: http://en.wikipedia.org/wiki/Feedback_arc_set I hope that helps.

1 0

Haskell performance in heavy numerical computations
by Joel Reymont 16 Jul '06

16 Jul '06

Is anyone using Haskell for heavy numerical computations? Could you share your experience? My app will be mostly about running computations over huge amounts of stock data (time series) so I'm thinking I might be better of with OCaml. Thanks, Joel -- http://wagerlabs.com/

9 9

packaging modules with internal-only functions
by Evan Martin 16 Jul '06

16 Jul '06

I'm writing an FFI bindings module, and one of the pieces from the library I want to wrap is their "Error" type. > module Error where To the user of the module, I'd like to only expose the nicely wrapped interface: > data Error = Error String String > instance Typeable Error where ... -- for throwDyn But within the module's implementation, I need to share some other, internal-only functions: > type ErrorTag = () > type ErrorP = Ptr ErrorTag > withErrorP :: (ErrorP -> IO a) -> IO a Where withErrorP potentially throwDyns an Error, so it needs the first module. What is the proper way to divide these up in terms of package exports? The best options I can figure out are either to split these into multiple modules, or to have my "Error" module export them and mark them not to be documented by haddock...

1 0

Windows PowerShell "Monad"
by Chad Scherrer 16 Jul '06

16 Jul '06

Yep, that's its codename. Now, I'm not much of a Windows person. Is the name just a weird coincidence, or does it have anything to do with monads as we know them? http://en.wikipedia.org/wiki/MSH_(shell) -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

3 3

Re: Why is Day and Month bounded?
by Johan Holmquist 15 Jul '06

15 Jul '06

I'll answer my own post to elaborate: If Day (and Month) where NOT instances of Bounded, the following would be possible: [Monday .. Sunday] => should return [Monday, Tuesday ... Saturday, Sunday] => but returns [] [Saturday .. Tuesday] => should return [Saturday, Sunday, Monday, Tuesday] => but returns [] succ Saturday => should return Sunday => but yields an exception It would feel natural to be able to get the desired results above. The Haskell98 report stipulates: --->8--- For any type that is an instance of class Bounded as well as Enum, the following should hold: The calls succ maxBound and pred minBound should result in a runtime error. --->8--- So, the standard library System.Time respects that and yields exception for succ Saturday. But if Day was not an instance of Bounded should it not be legal for succ Saturday to return Sunday? Now I cannot see the advantage of letting Day (and Month) be instances of Bounded. The only thing we get out of that is access to functions maxBound and minBound, but those do not seem useful to me for either Day or Month. /Johan

6 14

ldap-haskell questions
by Ferenc Wagner 15 Jul '06

15 Jul '06

Hi, to start off, I'm using ldap-haskell straight from its darcs repo under GHC-6.4.1, and it works. Just not quite like I want. First, I can't make a static compile: $ ghc --make prog.hs -o prog works without a warning, while $ ghc --make prog.hs -o prog -optl -static [...] /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(os-ip.o)(.text+0x38a): In function `ldap_pvt_is_socket_ready': : warning: `sys_errlist' is deprecated; use `strerror' or `strerror_r' instead /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(os-ip.o)(.text+0x381): In function `ldap_pvt_is_socket_ready': : warning: `sys_nerr' is deprecated; use `strerror' or `strerror_r' instead /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(os-ip.o)(.text+0x684): In function `ldap_connect_to_host': : warning: Using 'getaddrinfo' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(util-int.o)(.text+0x232): In function `ldap_pvt_gethostbyaddr_a': : warning: Using 'gethostbyaddr_r' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(util-int.o)(.text+0x64): In function `ldap_pvt_gethostbyname_a': : warning: Using 'gethostbyname_r' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(open.o)(.text+0x1b7): In function `ldap_create': : undefined reference to `ber_memcalloc' /usr/lib/gcc-lib/i486-linux/3.3.5/../../../libldap.a(open.o)(.text+0x26d): In function `ldap_create': : undefined reference to `ber_sockbuf_alloc' [...] (plenty of undefined references elided) If I cut out the LDAP part, the above command creates a static executable just fine. Second, I find no trace of SSL/TLS routines. Is that really left out, or do I overlook something? -- Thanks, Feri.

2 2

RE: [Haskell-cafe] Comma in the front
by Tim Docker 15 Jul '06

15 Jul '06

On Jul 12, 2006, at 9:18 PM, Joel Reymont wrote: > Are cool kids supposed to put the comma in front like this? > > , foo > , bar > , baz > > Is this for historical or other reasons because Emacs formats Haskell > code well enough regardless. > > Thanks, Joel > These layouts feel a bit artificial to me. I am quite partial to python's list syntax - a trailing comma is optional. meaning you can write [ a, b, c, ] I'm surprised this approach isn't more widespread - Are there reasons why haskell syntax could not/should not be defined this way? Tim

7 8

Type of a function?
by Jenny678 14 Jul '06

14 Jul '06

Hallo Can somebody tell me the type of the following function? func :: ????????????? func f x = (z,y) where (z,y) = f x Thanks -- View this message in context: http://www.nabble.com/Type-of-a-function--tf1945843.html#a5335607 Sent from the Haskell - Haskell-Cafe forum at Nabble.com.

3 3

can't WashNGo (abstract tables)
by Ferenc Wagner 14 Jul '06

14 Jul '06

Hi, trying to put WashNGo-2.9 to a nontrivial prototyping job gave some very compelling results so far, but also got me stumped on occasions. I'd be grateful for some guidance on the following points, concerning abstract tables mainly. * selectionDisplay: looks like displayFun (fourth arg) mustn't fail for null arguments, as it's invoked with them after leaving the page it appears on. An error or a feature? Is it documented? * trying to get around the "Strings only" restriction of AT's I threw in some show-read pairs, but got the impression that the channel is not Char-clean: Base64.encode . UTF8.encode helped. What's the spec? * should a click on an AT radio button result in submission of the form? It does not, which is OK with me. But the following code fails in a rather strange way: > data Record = P String Person | R String Role | Unknown String deriving (Read,Show) > > unAtSafe :: String -> Record > unAtSafe = read . fst . UTF8.decode . Base64.decode > > edit sg = case record of > P dn p -> editPerson dn p > R dn r -> editRole dn r > Unknown s -> standardQuery "No dice" $ CGI.div $ -- provokes error in AbstractSelector.hs:115 > do p $ text s > goBack > where record = unAtSafe $ head $ unAR $ value sg > > editPerson :: String -> Person -> CGI () > editPerson dn p = > standardQuery "Edit person" $ CGI.div $ > do inputs <- personTable p > actionPar "Modify" (createPerson dn) inputs In this case Person and Role contain String fields only. The abstract table contains Records, and the above function 'edit' dispatches on the type of the selected Record. The first two cases work, the Unknown case trips on an 'error' in the WashNGo code as indicated. It's in the valueSelectionGroup function, if selectionValue is Nothing. How could I fix this? * Lastly, how can I go back some queries? goBack above is basically a 'submit0 (return ())' which continues the main 'forever' loop. But what if I need to go back in the middle of the current loop, as if the user pressed Back several times? -- Thanks, Feri.

1 0

Building Data.Time on WinXP GHC6.4.1
by Alistair Bayley 14 Jul '06

14 Jul '06

Has anyone built Ashley's Data.Time package on Windows? I ask because timestuff.c fails to compile for me because it refers to fields (tm_zone, tm_gmtoff) in struct tm which don't seem to exist on Windows (at least, mingw). Alistair

2 1

ANN: Takusen 0.5
by Alistair Bayley 14 Jul '06

14 Jul '06

Oleg and I are pleased to announce the release of a new version of Takusen (it's been a while; so long that we don't remember the last version number we used). The most significant code change is a new internal design (courtesy of Oleg) which gives better separation of concerns like statement preparation, binding, and result-set processing. Also of note is a conversion to darcs, and hosting at haskell.org (thanks to Simon Marlow): darcs get http://darcs.haskell.org/takusen ... which also has the nice property that the Haddock documentation is browseable online: http://darcs.haskell.org/takusen/doc/html/index.html A comprehensive description of API usage can be found in the documentation for module Database.Enumerator: http://darcs.haskell.org/takusen/doc/html/Database-Enumerator.html We hope that the use of darcs will encourage contributions... Other changes: - support for multiple result sets returned from functions (PostgreSQL only). Oracle support for this is in the pipeline, which will allow use of nested cursors, and processing RefCursors returned as output parameters from procedure calls. Future plans: - Cabalisation - use of Data.Time instead of System.Time - ODBC and MS Sql Server backends For those of you unfamiliar with Takusen, here is our HCAR blurb: Takusen is a library for accessing DBMS's. It is a low-level library like HSQL, in the sense that it is used to issue SQL statements. Takusen's "unique-selling-point" is a design for processing query results using a left-fold enumerator. For queries the user creates an iteratee function, which is fed rows one-at-a-time from the result-set. We also support processing query results using a cursor interface, if you require finer-grained control. Currently we fully support Oracle, Sqlite, and PostgreSQL. Alistair

1 0

Why is Day and Month bounded?
by Johan Holmquist 13 Jul '06

13 Jul '06

I fail to see why the types Day and Month in System.Time are instances of Bounded. In my world there is no last day and the successor of Saturday is Sunday -- not an exception! :) I would like to believe there is a good reason for this boundedness, but I can't see it.

1 0

Using of C constants in Haskell sources; Determining compilation environment (Unix vs Windows)
by Bulat Ziganshin 13 Jul '06

13 Jul '06

Hello Haskell, what is a best way to bring C constant (defined in header file) into the Haskell source? Haskell project is cabalized and should work with both Win and Unix while the constants are OS-specific. the best way i found at this moment is to use the following scheme: mmap.h: #if defined(mingw32_HOST_OS) || defined(__MINGW32__) || defined(_MSC_VER) .... #else INLINE int const_MAP_FILE( void ) { return MAP_FILE; } #endif mmap.hs: #if defined(mingw32_HOST_OS) || defined(__MINGW32__) || defined(_MSC_VER) .... #else foreign import ccall unsafe "mydefs.h const_MAP_FILE" mAP_FILE :: CInt #endif Second question is how to test whether program compiles under Unix or Windows environment. Posix/Win32 packages availability would be the best criterion but it can't be tested :( -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

5 6

Hackathon hesitation
by Chad Scherrer 13 Jul '06

13 Jul '06

Hi, I'm interested in attending the Hackathon, but I don't have any previous experience working on compilers. I think it could be a great learning experience, but I certainly don't want to slow progress on any work by just hanging around asking questions. I'm a mathematician/statistician, and my programming experience is limited to high-level languages like Python, R, and Haskell. I can read C (sort of), but I've been too frustrated by the lack of high-level features to do anything useful with it. I've been using Haskell for about 2 years now (every chance I get), and I'm very interested in using it to allow high-performance (preferably parallel) code to be written at a very high level of abstraction. Given this, does it seem there would be much I could help with? Thanks, Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

6 5

Re: [Haskell] Type-Level Naturals Like Prolog?
by Greg Buchholz 13 Jul '06

13 Jul '06

Jared Warren wrote: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. > Why can't Haskell (with extensions) do type-level Peano naturals in > the same fashion? The code would be something like: Also of possible interest, _Fun with Functional Dependencies_... http://www.cs.chalmers.se/~hallgren/Papers/wm01.html "This paper illustrates how Haskell's type class system can be used to express computations. Since computations on the type level are performed by the type checker, these computations are static (i.e., performed at compile-time), and, since the type system is decidable, they always terminate. Haskell thus provides a means to express static computations, and has a clear distinction between static and dynamic computations. "

1 0

Comma in the front
by Joel Reymont 13 Jul '06

13 Jul '06

Are cool kids supposed to put the comma in front like this? , foo , bar , baz Is this for historical or other reasons because Emacs formats Haskell code well enough regardless. Thanks, Joel -- http://wagerlabs.com/

6 7

Haskore dependency trouble
by Yitzchak Gale 13 Jul '06

13 Jul '06

I am having trouble installing Haskore due to a dependency issue. I am a pampered user of Debian. Thanks to wonderful work by the Cabal people and the Debian package maintainers, I have never had to use Cabal manually to install a package before. In order to learn how to do that, I practiced by installing the ever-important HNOP package. After a few tries, I found that the following sequence of commands works: ./Setup.hs configure --prefix=/usr ./Setup.hs build sudo ./Setup.hs install But similar commands for Haskore do not fair as well. The configure command fails with the following error: Setup.lhs: cannot satisfy dependency Hsc-any How can I satisfy that dependency? I am using ghc on Debian testing. I obtained Haskore from http://cvs.haskell.org/darcs/haskore Thanks! Incidentally, why is Cabal not smart enough to know that with ghc on linux the default prefix is /usr? -Yitz

5 10

Re: [Haskell] Type-Level Naturals Like Prolog?
by Niklas Broberg 13 Jul '06

13 Jul '06

On 7/13/06, Jared Warren <jawarren(a)gmail.com> wrote: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. However, Idealised Prolog > does not have data structures, and does Peano numbers like: > > natural(zero). > natural(x), succ(x,y) :- natural(y) > > And I believe (but cannot confirm): > > succ(zero,y). > succ(x,y) :- succ(y,z) That is not a valid encoding of peano numbers in prolog, so I think that's where your problems stem from. :-) % defining natural numbers natural(zero). natural(s(X)) :- natural(X). % translate to integers toInt(zero, 0). toInt(s(X), N) :- toInt(X, Y), N is Y + 1. In the same style of reasoning for Haskell, we would define > data Zero > data Succ x > > class Natural x > instance Natural Zero > instance (Natural x) => Natural (Succ x) > > class Natural x => ToInt x where > toInt :: x -> Int > > instance ToInt Zero where > toInt _ = 0 > > instance (ToInt x) => ToInt (Succ x) where > toInt _ = toInt (undefined :: x) + 1 Or we could add the toInt method directly to the Natural class like you did above. So yes, we can mimic (some of) prolog in Haskell's type language. :-) /Niklas

1 0

Breaking cycles in a directed graph.
by Daniel McAllansmith 13 Jul '06

13 Jul '06

Hello. I'm currently using Data.Graph.Inductive to represent a directed graph. I want to detect all cycles within the graph and 'break' them by inserting a minimal number of nodes that are labelled with a special cycle-breaker label. Can anyone give me advice on a good algorithm for finding the cycles and finding the optimum edges to insert the cycle-breaking nodes on? Thanks Daniel

4 6

Re: [Haskell] Type-Level Naturals Like Prolog?
by dons＠cse.unsw.edu.au 13 Jul '06

13 Jul '06

jawarren: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. However, Idealised Prolog > does not have data structures, and does Peano numbers like: > > natural(zero). > natural(x), succ(x,y) :- natural(y) > > And I believe (but cannot confirm): > > succ(zero,y). > succ(x,y) :- succ(y,z) > > Why can't Haskell (with extensions) do type-level Peano naturals in > the same fashion? The code would be something like: > > >data Zero > > > >class Natural x where > > toInt :: x -> Integer > >instance Natural Zero where > > toInt _ = 0 > >instance (Natural x, Succ x y) => Natural y where > > toInt y = undefined + 1 > > > >class Succ x y > >instance Succ Zero y > >instance Succ x y => Succ y z > > > >zero = toInt (undefined :: Zero) -- THIS SUCCEEDS > > > >one = toInt (undefined :: (Succ Zero x) => x) -- THIS FAILS > Perhaps these will be useful? http://www.haskell.org/haskellwiki/Peano_numbers http://www.haskell.org/haskellwiki/Type_arithmetic and a bit of stuff here http://www.haskell.org/haskellwiki/Smart_constructors Cheers, Don (P.S. moved to haskell-cafe(a)haskell.org, more appropriate)

2 1

Re: Why is there no splitBy in the list module?
by tpledger＠ihug.co.nz 13 Jul '06

13 Jul '06

Jared Updike wrote: > > "split" is... unconcatIntersperse. > > How about "separate"? ("split" or "splitBy" is better but it is used > all over the place in many libs) > > And for strings I definitely would use split :: [a] -> [a] -> [[a]] a > lot, just like Python's split function. And "words" works great for > breaking on multiple spaces, so I would avoid trying to fill that > need... FWIW my home-grown versions of these things are called fields and unfields.

4 4

instance Binary Data
by Bulat Ziganshin 12 Jul '06

12 Jul '06

Hello Haskell, one Streams library user asked me about support of serialization TOGETHER with type information which means implementation of "instance Binary Data" (any other variants?). can anyone describe me how i can implement this? Binary instance is very like Show/Read, just uses compact binary encoding of values -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 3

Arrows and 'do' syntax
by Greg Fitzgerald 12 Jul '06

12 Jul '06

I'm trying to translate this HXT code to use the Arrow 'do' syntax: readWriteDoc :: String -> IOSLA (XIOState s) b Int readWriteDoc path = readDocument [(a_validate, "0")] path >>> writeDocument [(a_output_encoding, isoLatin1)] "-" >>> getErrStatus This attempt fails to compile: readWriteDoc :: String -> IOSLA (XIOState s) b Int readWriteDoc = proc path -> do doc <- readDocument [(a_validate, "0")] -< path result <- writeDocument [(a_output_encoding, isoLatin1)] "-" -< doc getErrStatus -< result I get this error message: Couldn't match `(->)' against `IOSLA (XIOState s)' Expected type: t -> t1 Inferred type: IOStateArrow s XmlTree XmlTree Probable cause: `writeDocument' is applied to too many arguments in the call (writeDocument [(a_output_encoding, isoLatin1)] "-") In the command: writeDocument [(a_output_encoding, isoLatin1)] "-" -< doc Any idea what I'm doing wrong? Thanks, Greg

2 2

Re: Haskell-Cafe Digest, Vol 35, Issue 26
by Chad Scherrer 12 Jul '06

12 Jul '06

On 7/12/06, henning thielemann wrote: > There must be an algorithm for finding the minimal spanning tree or > forest. The edges that do not belong to the tree should be the labelled as > cycle-breakers. > Actually, I don't think that would do it, since you could have an acyclic directed graph like this: a -> b | | \/ \/ c -> d There are no cycles here, but the minimal spanning tree is not the whole thing. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Small syntax question
by Maurício 12 Jul '06

12 Jul '06

Hi, I can do this: (let a=3 in a) + (let b=4 in b) but not this: (a where a=3) + (b where b=3) Why? Thanks, Maurício

5 6

Problems installing HDBC-postgresql
by Martin Percossi 12 Jul '06

12 Jul '06

Hi, I'm having problems using HDBC-postgresql (I've tried both 0.99.2.1 and 1.0.0.0) with postgresql (version 8.1.4, installed in /share/pgsql). I adjust the include-dir and extra-lib-dirs to use the custom location of postgresql, and build: no error messages, everything seems fine. However, when I then try to type: ghci -package HDBC -package HDBC-postgresql , I get the error message: Loading package HDBC-postgresql-0.99.2.1 ... linking ... ghc-6.4.2: /home/mpercossi/opt/lib/HDBC-postgresql-0.99.2.1/HSHDBC-postgresql-0.99.2.1.o: unknown symbol `PQserverVersion' ghc-6.4.2: unable to load package `HDBC-postgresql-0.99.2.1' Has anyone seen this error message before? Google didn't turn up anything relevant to haskell -- however there does seem to be a PQserverVersion procedure in the libpq library -- maybe HDBC-postgresql is not seeing this due to the custom install location? TIA Martin

2 2

technique to allow innocuous ambiguity in instance declarations?
by Nicolas Frisby 12 Jul '06

12 Jul '06

Brief disclaimer: I'm using GHC 6.4.1 and haven't looked into Hugs; but I don't suspect there's much difference on this issue. Could easily be wrong there. I've hit a bit of a road bump in ambiguity regarding type class instances and transformer types (in the style of monad transformers). The interesting point is that, in this case, I believe that the ambiguity is harmless and that all possible derivations of instances would be extensionally equivalent. But the typechecker won't let me get far enough to test that hypothesis. So, I have a relation C and intuition that the property can be carried through transformations on either of its related types. I'm seeking 1) a suggested technique for formulating that intuition in such a way that the type-checker could act on it 2) a suggestion claiming that such a harmless ambiguity is down right impossible Below is pseudo-code outlining the shape of my problem. Consider a 2 parameter (both are type constructors) class: > class C f g where > nest :: f a -> g a I have instances for base types (analogous to the Identity monad). > class C IdL IdR where > nest = ... I also have transformers that I can apply to these base types and instances that correspond to "lifting" the C type class property through the transformers. > class C f g => C f (TransR g) where > nest = ... code that involves the "nest" of the C f g instance ... or > class C f g => C (TransL f) g where > nest = ... code that involves the "nest" of the C f g instance ... The simple version of my issue is that, give the instances so far, the compiler won't derive an instance for T. > type T = C (TransL IdL) (TransR IdR) The impasse is the ambiguity in the derivation from C IdL IdR to T. One could apply first TransL or apply first TransR. The "-fallow-overlapping-instances" type system extension fails to help because there is no "most specific" instance. The order of application of my transformers (i.e. transforming the left or transforming the right parameter) does not seem to matter--I have found no intuition that says the derivations ought to be distinguishable in anyway. My question: Is there a technique to allow such innocuous ambiguity in instance declarations? I experimented with introducing something akin to a trace in a third parameter to the class which would disambiguate the derivation (by specifying the order of the transformations; reminded me of "Strongly typed heterogeneous collections"), but had no luck there (perhaps someone else would). Because the ambiguity does not matter to me, I'd be fine implementing a rule such as "always transform the left parameter first", but I don't know how to/if I can formulate that in Haskell. I also tried to reduce the class to a single parameter, which incorporated the the functors into a single type. The method of the class needs those functor types available, so that approach sputtered out. Another issue is modularity: both of my attempts above would have bloated the code using the class with the details needed to disambiguate it. I certainly prefer the context "C f g" to one that exposes the disambiguation. That is, I would highly prefer a solution that allows h1 instead of h2. > h1 :: C f g => a type > h1 = ... some code with nest ... > h2 :: (C f g, DisambiguationHelper f g ?) => a type > h2 = ... some code with nest ... My harrowing suspicion is that I will need to split the property into two--something I can't readily see how to do. Thanks for your time, Nick

2 1

comdlg32.dll FFI bindings
by Jason Dagit 12 Jul '06

12 Jul '06

Hello, I was planning to create FFI bindings for GHC to be able to use comdlg32.dll and I just realized I should ask if others have already done this. I figure I'll probably just code it up by hand assuming I can find suitable documentation but if there is a tool that can generate this automatically that would be even better. Thanks, Jason

3 3

Re: Why is there no splitBy in the list module?
by Yitzchak Gale 11 Jul '06

11 Jul '06

I personally use split :: Eq a => [a] -> [a] -> [[a]] all the time, much more often than splitBy :: (a -> Bool) -> [a] -> [[a]] But I don't call it "split". By analogy with concatMap, the Haskell analogue of Perl/Python "join" is concatIntersperse. Then, by analogy with lines/unlines, the Haskell analogue of "split" is... unconcatIntersperse. Hmm...

2 1

Defining show for a function type.
by Johan Grönqvist 11 Jul '06

11 Jul '06

I am a haskell-beginner and I wish to write a Forth-like interpreter. (Only for practice, no usefulness.) I would like use a list (as stack) that can contain several kinds of values. data Element = Int Int | Float Float | Func : Machine -> Machine | ... Now I would like to have this type be an instance of the class Show, so that I can see what the stack contains in ghci. "deriving Show" is impossible as Func is not instance of Show. Can I make it instance of Show? I just want to define something like show (Func _) = "Function, cannot show" and I am not interested in actually displaying any information about the function, but I am interested in getting information about elements of other kinds. So far I have just guessed, but failed to produce anything that does not give an error stating that my function is not of the form (T a b c) where T is not an alias and a b c are simple type variables (or so). Any help appreciated! Johan

7 7

Re: [Haskell-cafe] Re: Why is there no splitBy in the list module?
by Donn Cave 11 Jul '06

11 Jul '06

Quoth John Meacham <john(a)repetae.net>: ... | just a note: I find splitBy a much nicer routine to provide. | |> splitBy :: (a -> Bool) -- ^ whether char is a separator |> -> [a] -- ^ list to split |> -> [[a]] Starting from the assumption that in most cases the list to be split will be [Char], so we can reasonably hold this up against string functions in other languages -- I think split is commonly split :: String -> String -> [String] i.e., the separator is [a], not a. Of course next they'll want regular expressions, but I use string separators of length > 1 a lot and rarely bother with regexps. But string splitBy might be an interesting alternative to regexp splits. Something like splitBy :: ([a] -> Maybe Int) -> [a] -> [[a]] breakBy :: ([a] -> Maybe Int) -> [a] -> Maybe ([a], [a]) breakBy f s = by [] f s where by _ _ [] = Nothing by c f s@(a:ax) = case f s of Just n -> Just ((reverse c), (drop n s)) Nothing -> by (a:c) f ax splitBy f s = case breakBy f s of Just (l, r) -> l:(splitBy f r) Nothing -> [s] Where in the simplest case the matching function would simply compare with a separator string, but could easily do more - eat up trailing blanks, for example. Note use of Maybe, basically to disambiguate end of data with and without match. Donn Cave, donn(a)drizzle.com

1 0

Re: [Haskell-cafe] type dependency
by Donn Cave 11 Jul '06

11 Jul '06

Quoth Henning Thielemann <lemming(a)henning-thielemann.de>: ... | Will you make that plotter wrapper public? Why not - I don't expect it's going to be big news in the computing world, but it's easy to set the files up. See http://staff.washington.edu/donn/ezp/hsezp.html Thanks to Bulat for the tip on multi-parameter typeclass. Donn Cave, donn(a)drizzle.com

1 0

Help building HSQL...
by Martin Percossi 10 Jul '06

10 Jul '06

Hi, I'm trying to build HSQL, in order to use HaskellDb. The base directory (i.e. HSQL) builds ok, as per instructions, but the PostgreSQL directory fails with the error message: Setup.lhs:17:71: Couldn't match `PackageDescription' against `LocalBuildInfo' Expected type: Args -> ConfigFlags -> LocalBuildInfo -> IO ExitCode Inferred type: [String] -> ConfigFlags -> PackageDescription -> LocalBuildInfo -> IO ExitCode In the `postConf' field of a record In the record update: defaultUserHooks {preConf = preConf, postConf = postConf} My version of ghc is 6.4.2. My installed packages are (using "ghc-pkg list"): Cabal-1.0, (Cabal-1.1.4), GLUT-2.0, HUnit-1.1, MissingH-0.14.2, OpenGL-2.0, QuickCheck-1.0, base-1.0, (concurrent-1.0), (data-1.0), fgl-5.2, haskell-src-1.0, haskell98-1.0, hsql-1.7, (hssource-1.0), (lang-1.0), mtl-1.0, (net-1.0), network-1.0, parsec-1.0, (posix-1.0), readline-1.0, rts-1.0, stm-1.0, template-haskell-1.0, (text-1.0), unix-1.0, (util-1.0) Note that I have installed all of these packages, and ghc into my ~/opt directory, as I don't have root. Has anyone seen the above error message before? Am I using the incorrect version of Cabal? Any help appreciated. TIA Martin

2 1

lists as instances of a class?
by David Roundy 10 Jul '06

10 Jul '06

(This email is a literate haskell program that fails to compile without -fglasgow-exts.) I'm sure I'm missing something lame here, but can someone tell me why we apparently can't declare a list to be an instance of a class in Haskell 98? Or is there perhaps some other syntax by which I'd declare this instance? If so, is this slated for fixing in Haskell'? $ ghc Test.lhs Test.lhs:6:1: Illegal instance declaration for `Vec [Double]' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `Vec [Double]' > module Vec where > class Vec v where > (.+.) :: v -> v -> v > instance Vec [Double] where > xs .+. ys = zipWith (+) xs ys > instance Vec Double where > x .+. y = x + y feeling very stupid, David P.S. This is with ghc 6.4.1. And oddly enough, if you make the instance instance Num a => Vec [a] where xs .+. ys = zipWith (+) xs ys it works fine, but this strikes me as quite an ugly hack. I really want only Doubles to be instances of this class (which I've abbreviated for this email).

7 6

question about haskell wiki copy-rights
by Bulat Ziganshin 10 Jul '06

10 Jul '06

Hello haskell-cafe, i plan to write sometimes a Haskell performance tutorial. am i correctly understand that i can include contents of existing haskell wiki pages as long as tutorial will be published only on haskell wiki? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 2

Packages and modules
by Brian Hulley 10 Jul '06

10 Jul '06

Hi - At the moment there is a problem in that two packages P and Q could contain the same hierarchical module eg Data.Foo, and the only way for user code to ensure the "right" Data.Foo is used is to ensure that packages P and Q are searched in the right order. However suppose P and Q also contain another module with the same name, eg Data.Bar. And suppose a user module wants to use Data.Foo from P but Data.Bar from Q!!! I'm wondering: would it not be easier to just make it that the package name is prepended to the hierarchical module name, so the modules would instead be called by the names P.Data.Foo and Q.Data.Bar? As I see it, this would have at least these advantages: 1) A package author would only have to ensure that the name of the package (eg Edison, FPS, Base) is globally unique, and would then be free to name the modules in the package without having to worry about conflicts with other packages 2) Users of packages could specify exactly which modules they want to use, which would also make it easier to switch between different implementations of the same data type provided by different people etc 3) When you read the program text, you could immediately see which packages the modules came from, so you would know which packages you need to download if you don't currently have that module on your system. (At the moment, if I come across "import Data.Foldable" I've got no idea where to get it from.) It seems to me that the only reason this wasn't done in the first place was that originally there was just a flat module namespace, whereas with hierarchical modules it seems obvious to put the package name at the beginning (eg in Java the modules are called java.xyz, com.company.xyz etc to ensure there are no namespace conflicts) (On the Haskell' wiki there is http://hackage.haskell.org/trac/haskell-prime/wiki/SolveThePackageAbstracti… but this doesn't appear to consider the above solution.) Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com

16 37

Trace parser
by Andy Georges 10 Jul '06

10 Jul '06

Hello, I'm looking for a bit of help (ok, a lot) the speed up my program which I use to build a calltree out of an annotated program execution trace. To give you an idea about the sluggishness at the moment, for a trace containing 70MB, it has been running for about 10 hours straight (AMD Athlon XP (Barton) 2600+). The trace contains lines made up of a number of fields: C 4 1000 1000000 C 4 1001 1000200 R 4 1001 1003045 R 4 1000 1003060 C indicates a function entrypoint (call), R indicates a function exitpoint (return). The second field indicates which thread is executing the function, the third field denotes the function id, the last field contains a performance counter value. As you can see, numbering each line with a pre-order and a post-order number yields a list that can be transformed easily into a tree, which can then be manipulated. The first goal is to build the tree. This is done in the following code: data ParserState = ParserState { methodStack :: !ThreadMap , methodQueue :: !ThreadMap , pre :: !Integer , post :: !Integer , methodMap :: !MethodMap , currentThread :: !Integer } deriving (Show) initialParserState :: ParserState initialParserState = ParserState e e 0 0 e 0 where e = M.empty :: Map Integer a readInteger :: B.ByteString -> Integer readInteger = fromIntegral . fst . fromJust . B.readInt parseTraceMonadic :: [B.ByteString] -> ParserState parseTraceMonadic ss = state { methodQueue = M.map reverse (methodQueue state) } where state = execState (mapM_ (\x -> modify (updateState x) >> get >>= (`seq` return ())) ss) initialParserState updateState :: B.ByteString -> ParserState -> ParserState updateState s state = case (B.unpack $ head fields) of "M" -> updateStateMethod fields state "E" -> updateStateException fields state "C" -> updateStateEntry fields state "R" -> updateStateExit fields state where fields = B.splitWith (== ' ') s updateStateMethod :: [B.ByteString] -> ParserState -> ParserState updateStateMethod (_:methodId:methodName:_) state = state { methodMap = M.insert (readInteger methodId) methodName (methodMap state) } updateStateException :: [B.ByteString] -> ParserState -> ParserState updateStateException _ state = state updateStateEntry :: [B.ByteString] -> ParserState -> ParserState updateStateEntry (_:ss) state = {-Debug.Trace.trace ("before: " ++ (show state) ++ "\nafter: " ++ (show newstate)) $-} newstate where newstate = state { methodStack = updateMap thread (methodStack state) (\x y -> Just (x:y)) (pre state, 0, method) , pre = ((+1) $! (pre state)) } method = mkMethod (Prelude.map B.unpack ss) thread = Method.thread method updateStateExit :: [B.ByteString] -> ParserState -> ParserState updateStateExit (_:ss) state = {-Debug.Trace.trace ("before: " ++ (show state)) $-} case updateMethod m (Prelude.map B.unpack ss) of Just um -> state { methodStack = M.update (\x -> Just (tail x)) thread (methodStack state) , methodQueue = updateMap thread (methodQueue state) (\x y -> Just (x:y)) (pre_, post state, um) , post = ((+1) $! (post state)) } Nothing -> error $ "Top of the stack is mismatching! Expected " ++ (show m) ++ " yet got " ++ (show ss) ++ "\n" ++ (show state) where method = mkMethod (Prelude.map B.unpack ss) thread = Method.thread method (pre_, _, m) = case M.lookup thread (methodStack state) of Just stack -> head stack Nothing -> error $ "Method stack has not been found for thread " ++ (show thread) ++ " -> fields: " ++ (show ss) updateMap key map f value = case M.member key map of True -> M.update (f value) key map False -> M.insert key [value] map As you can see, the state is updated for each entry, a stack being maintained with methods we've seen up to now, and a list with methods that have received both pre and post order numbers, and of which both the entry and exit point have been parsed. I am using a ByteString, because using a plain String is causing the program to grab far too much heap. The mkMethod yields a Method like this: data Method = Method { mid :: Integer , thread :: Integer , instruction_entry :: Integer , instruction_exit :: Integer } deriving (Eq, Show) eM = Method 0 0 0 0 mkMethod :: [String] -> Method mkMethod s = let [_thread, _id, _entry] = take 3 $ map (read :: String -> Integer) s in [_thread, _id, _entry] `seq` Method { mid = _id , thread = _thread , instruction_entry = _entry , instruction_exit = 0 } updateMethod :: Method -> [String] -> Maybe Method updateMethod (Method mid thread instruction_entry instruction_exit ) s | thread == _thread && mid == _id = _exit `seq` Just Method { mid = mid , thread = thread , instruction_entry = instruction_entry , instruction_exit = _exit } | otherwise = Nothing where [_thread, _id, _exit] = take 3 $ map (read :: String -> Integer) s Any suggestions for improving this code? Thanks, Andy

2 2

help with creating a DAG?
by David Roundy 09 Jul '06

09 Jul '06

Hi all, I'm wanting to create a data structure to hold a directed acyclic graph (which will have patches represented by edges), and haven't yet been able to figure out a nice representation. I'd like one that can be reasoned with recursively, or as closely to recursively as possible. The problem is one of dependency relations between darcs patches, and "normally" reduces to a simple tree, with conflict resolution patches bringing branches of the tree back together. Trees I know how to handle intuitively and elegantly, but DAGs are a whole different question. I looked for papers, and there was one on "an initial-algebra approach to DAGs" that looked promising, but I'm afraid I wasn't able to fully understand it, and it is able to describe more complicated DAGs than I'd like to support. Anyhow, any suggestions from persons with experience with this sort of thing would be great. These are getting to be data structures that are more complicated than anything I'm comfortable with. :( -- David Roundy

4 4

Strictness in do block
by John Goerzen 08 Jul '06

08 Jul '06

Hi, One thing that seems to keep biting me is strictness in do blocks. What I want to know is the generic way to force an entire String (or other list, perhaps from hGetContents) to be evaluated (read into RAM, I guess) so the underlying file can be closed.... and do it right now. One quick hack that works is hPutStrLn on it, right where I want it to be evaluated. But ugly and not always appropriate. Passing it to some other IO-based functions also works, but again, that doesn't "feel" right. I can always stumble upon things that work, but I'm never sure if I've got 'em right. So, what is the idiomatic way to do this? Most of the documents I see out there on this topic are for usage outside the I/O monad, and I'm not seeing how they apply here. Thanks, -- John

6 6

WxHaskell Question: How to get mouse or context menu events for wxGrid
by Jason Dagit 07 Jul '06

07 Jul '06

Hello, Not sure where to ask this question but maybe here is a good place. I'm trying to use wxHaskell and I need a table with a right-click context menu. So far it seems that I can get some events on a wxGrid but not the context menu event or the mouse right click event. To get grid events I've followed the example in the wxHaskell source which grabs grid events. Using this technique I can get mouse right-clicks if they happen in a cell. I was hoping to get the events when the click happens in the wxGrid control but not over a cell (for example, you might click below the last row and the menu would have an option to create a new row). I tried the following but the events never seem to fire: windowOnMouse myGrid True (_ -> logMessage "mouse event" >> propagateEvent) windowOnContextMenu myGrid (logMessage "context menu") I have logMessage set to use stderr for output and I know it works great. Any ideas on how to do this? Thanks, Jason

1 0

Prefix/Infix operators
by Sara Kenedy 07 Jul '06

07 Jul '06

Hello everybody, I checked the topics in Haskell-Cafe about prefix/infix operators but I did not find them. Now I bring my questions to here to ask you. 1) I have a Common-Lisp code representing an expression result as follows ((MPLUS SIMP) ((MTIMES SIMP) ((RAT SIMP) 1 2) ((MEXPT SIMP) $X 2)) ((MTIMES SIMP) ((RAT SIMP) 1 3) ((MEXPT SIMP) $X 3))) 2) I attempted to change it to mathematics operators, replacing MPLUS SIMP -> + MEQUAL SIMP -> = RAT SIMP -> / MEXPT SIMP -> ^ translate :: String -> String translate [] = [] translate ('(':'M':'P':'L':'U':'S':' ':'S':'I':'M':'P':')':xs) = "(+)" ++ translate xs translate ('(':'M':'T':'I':'M':'E':'S':' ' :'S':'I':'M':'P':')':xs) = "(*)" ++ translate xs translate ('(':'M':'E':'Q':'U':'A':'L':' ' :'S':'I':'M':'P':')':xs) = "(=)" ++ translate xs translate ('(':'R':'A':'T':' ':'S':'I':'M':'P':')':xs) = "(/)" ++ translate xs translate ('(':'M':'L':'I':'S':'T':' ':'S':'I':'M':'P':')':xs) = "([])" ++ translate xs translate ('(':'M':'E':'X':'P':'T':' ':'S':'I':'M':'P':')':xs) = "(^)" ++ translate xs translate ('$':'X':xs) = "x" ++ translate xs translate ('$':'Y':xs) = "y" ++ translate xs translate (x:xs) = x:translate xs 3) And NOW I want to transfer from prefix operator into infix operator, for example: From ((+) ((*) ((/) 1 2) ((^) x 2)) ((*) ((/) 1 3) ((^) x 3))) in to the expression: 1/2*x^2+1/3*x^3 I try to figure out it, but this time it is not successfully. If you are familiar with that, please share with me. Many thanks to all. S.

2 1

Re: Packages and modules
by Chris Kuklewicz 07 Jul '06

07 Jul '06

seth(a)cql.com wrote: >> "Simon Peyton-Jones" <simonpj(a)microsoft.com> writes: >> >>> Brian Hulley wrote: >>> | import A.B.C( T1 ) from "foo" >>> | import A.B.C( T2 ) from "bar" >>> | type S = A.B.C.T1 -> A.B.C.T2 >>> | I'd suggest that the above should give a compiler error that A.B.C is >>> | ambiguous (as a qualifier), rather than allowing T1 to disambiguate >>> it, >>> But that's inconsistent with Haskell 98. >> FWIW, I agree with Brian that this is not good practice. If it can't >> be forbidden, I would suggest that compilers emit a warning about it. > > Is there really a case where someone would use that pattern intentionally? > I'd vote for making it an error by default. Perhaps then a flag would be > available that says "accept dangerous constructs that are legal according > to Haskell 98". > The Haskell 98 behavior compensates for the case where the module you used to import Old (foo,bar) has been split into two new modules, A(foo) and B(bar). You can import A as Old and B as Old so that Old.foo and Old.bar now resolve to A.foo and B.bar. I expect the pattern for the above would actually be closer to > import Old(T1,T2) from "original" > > mine :: Old.T1 -> Old.T2 becoming > import qualified A.B.C(T1) as Old from "foo" > import qualified D.E.F(T2) as Old from "bar" > > mine :: Old.T1 -> Old.T2 Which is a syntax that should be supported. -- Chris

1 0

Windows Haskell GUI
by Neil Mitchell 06 Jul '06

06 Jul '06

Hi, I want to develop a GUI using Haskell on Windows. As far as I can tell the options for a reasonably high level GUI toolkit are: * wxHaskell * Gtk2Hs Unfortunately I cannot find released packages for GHC 6.4.2 for either of them - Gtk supports only 6.4.1 and wx supports only 6.4.0. Does anyone have builds of either of these that work with 6.4.2? Thanks Neil

4 6

Haskell as embedded DSL
by Joel Reymont 06 Jul '06

06 Jul '06

Folks, Do you have examples of using Haskell as a DSL in an environment NOT targeted at people who know it already? I'm thinking of using Haskell to build my Mac trading app but I'm very concerned about dumping Haskell on the trading systems developers. It seems that using, say, Ruby as the trading systems DSL would give me a leg up since it's simple and syntax and generally warm and fuzzy. What do you think? Thanks, Joel P.S. Yes, I'm a big fan of "Composing Financial Contracts" -- http://wagerlabs.com/

4 4

Re: [Haskell-cafe] New Benchmark Under Review: Magic Squares
by Daniel Fischer 05 Jul '06

05 Jul '06

Am Mittwoch, 5. Juli 2006 21:28 schrieben Sie: > Hi Daniel, > > In the paragraph below it looks like you improved the performance of > 5x5 from one and one half hours to one second. Is that a typo or > should I be very, very impressed. :-) > > Cheers, David Err, neither, really. Apparently, I haven't expressed myself immaculately clearly, so let me try again. Josh Goldfoot's original code produced a 5x5 magic square on the benchmarking computer in 8063.01s, on my computer, I hit ctrl-C after about 4 1/2 hours. My first version produced a 5x5 square in a little over 4 seconds (or was it a little over 5s, I'm not sure), and a 6x6 square in 86.5s, but since I used better bounds for the possible moves - e.g., if we regard a 5x5 square with two entries, 1 at (1,1) and 2 at (1,2), JG's code would give [3 .. 25] as the list of possible moves for (1,3), whereas I took into account that the sum of (1,4) and (1,5) is at most 24 + 25 = 49 (and at least 3+4, but that doesn't help here), thus finding that (1,3) must be at leat 65 - (1+2) - 49 = 13 and [13 .. 25] as the list of possible moves. So I avoided a lot of dead ends, but produced a different magic square. This code I have pushed down to 1s for the 5x5 square and 5.4s for the 6x6 square (simply by replacing "intersect [a .. b]" with "takeWhile (<= b) : dropWhile (< a)"). I have then tuned Josh Goldfoot's code (throwing out the List <-> Set conversions, keeping a list of unused numbers and not much else), so that it produced a 5x5 square in 1 1/2 hours on my computer, giving the same list of possible moves as the original and hence the same magic square. That's not bad, but not really awe-inspiring. However, I've also combined the algorithms, using my better bounds, thus avoiding many dead ends, but calculating the priorities as if I used the original bounds, so exploring the branches in the same order and producing the same square as the original. This took about 12 minutes for a 5x5 square and impressed me - I expected it to be significantly slower than the fast code, but a factor of 720 was much more than I dreamed of. Cheers, Daniel > > On Jul 4, 2006, at 6:48 AM, Daniel Fischer wrote: > > Hi, > > I have now tuned Josh Goldfoot's code without changing the order in > > which the > > magic squares are produced, for a 5x5 magic square, my machine took > > about 1 > > 1/2 hours and used 2Mb memory (considering that the original code > > did not > > finish within 4 1/2 hours here, that should push time on the > > benchmarking > > machine under 3000s and put us in the lead, I hope). > > However, with the improved bounds for the possibilities, I can now > > get a 5x5 > > square in 1s, a 6x6 square in 5.5s (replacing intersect by takeWhile & > > dropWhile), so it's still sloooowwww. > > > > Brent, can I informally submit the code thus, or what formalities > > would I have > > to perform to submit my code? > > > > ---------------------------------------------------------------------- > > ----------------------------- > > {- The Computer Language Shootout > > http://shootout.alioth.debian.org/ > > > > benchmark implementation > > contributed by Josh Goldfoot > > modified by Daniel Fischer to improve performance -} > > > > {- An implementation using Data.Graph would be much faster. This > > implementation > > is designed to demonstrate the benchmark algorithm. -} > > > > import Data.Array > > import Data.List > > import System (getArgs) > > > > main = do > > n <- getArgs >>= return . read . head > > let mn = (n * (1 + n * n)) `div` 2 -- the magic number > > initialNode = makeSquare n mn (listArray ((1,1),(n,n)) > > (repeat 0), [1 > > .. n^2]) > > allSquares = bestFirst (successorNodes n mn) (initialNode:[]) > > putStrLn $ printMatrix n $ grid $ head allSquares > > where > > printMatrix n grid = unlines [ (rowlist grid n y) | y <- > > [1..n]] > > where > > rowlist grid n y = unwords [show $ grid ! (x,y) | x > > <- [1..n]] > > > > data Square = Square { grid :: Array (Int,Int) Int, > > ffm :: ([Int], Int, Int), > > unused :: [Int], > > priority :: !Int } > > > > {- bestFirst: Given a queue with one initial node and a function, > > successors, > > that takes a node and returns a list of nodes that are created > > by making > > all possible moves in a single cell, implements the Best-First > > algorithm, > > and returns a list of all nodes that end up with priority > > zero. In this > > implementation we only ever use the first node. > > -} > > bestFirst _ [] = [] > > bestFirst successors (frontnode:priorityq) > > > > | priority frontnode == 0 = frontnode:bestFirst successors > > > > priorityq > > > > | otherwise = bestFirst successors $ foldr (insertBy > > > > compSquare) priorityq > > (successors frontnode) > > where > > {- The priority queue is sorted first by > > the node's calculated priority; then, if the priorities > > are equal, by whichever node has the lowest numbers > > in the top-left of the array (or the next cell over, > > and so on). -} > > compSquare a b = case compare (priority a) (priority b) of > > EQ -> compare (grid a) (grid b) > > ot -> ot > > > > {- successorNodes: Find the cell with the fewest > > possible moves left, and then creates a new node for each > > possible move > > in that cell. > > -} > > successorNodes n mn squarenode = > > map (makeSquare n mn) [(thegrid//[((x, y), i)], delete i un) | > > i <- > > possibilities] > > where > > thegrid = grid squarenode > > un = unused squarenode > > (possibilities, x, y) = ffm squarenode > > > > {- makeSquare: Creates a node for the priority queue. In the > > process, this > > calculates the cell with the fewest possible moves, and also > > calculates > > this node's priority. The priority function is: > > (number of zeros in the grid) > > plus > > (number of possible moves in the cell with the fewest > > possible moves) > > the lower the priority, the sooner the node will be popped from > > the queue. > > -} > > makeSquare n mn (thegrid,un) = > > Square { grid = thegrid, ffm = moveChoices, unused = un, > > priority = > > calcPriority } > > where > > moveChoices@(poss,_,_) = findFewestMoves n mn thegrid un > > calcPriority = length un + length poss > > > > {- findFewestMoves: Go through the grid (starting at the top-left, > > and moving > > right and down), checking all 0 cells to find the cell with > > the fewest > > possible moves. > > -} > > findFewestMoves n mn grid un > > > > | null un = ([],0,0) > > | otherwise = (movelist, mx, my) > > > > where > > openSquares = [ (x,y) | y <- [1..n], x <- [1..n], (grid ! > > (x,y)) == 0] > > pm = possibleMoves n mn grid un > > openMap = map (\(x,y) -> (pm (x,y), (x,y))) openSquares > > mycompare f g = compare ((length . fst) f) ((length . fst) g) > > (movelist, (mx, my)) = minimumBy mycompare openMap > > > > {- possibleMoves: Return all moves that can go in the cell x,y for > > a given > > grid. A move is possible if the move (number) is not already > > in the grid, and if, after making that move, it is still > > possible to > > satisfy the magic square conditions (all rows, columns, > > diagonals adding > > up to mn, the magic number) > > -} > > possibleMoves n mn grid un (x,y) > > > > | grid ! (x,y) /= 0 = [] > > | null oneZeroGroups = takeWhile (<= highest) un -- [1 .. highest] > > > > `intersect` un > > > > | otherwise = case onePossible of > > > > [p] | p `elem` un -> [p] > > _ -> [] > > where > > cellGroups > > > > | x + y == n + 1 && x == y = [diag1 grid n, diag2 grid > > > > n, theRow, > > theCol] > > > > | x == y = [diag1 grid n, theRow, theCol] > > | x + y == n + 1 = [diag2 grid n, theRow, theCol ] > > | otherwise = [theRow, theCol] > > > > theRow = gridRow grid n x y > > theCol = gridCol grid n x y > > oneZeroGroups = filter (\x -> count 0 x == 1) cellGroups > > onePossible = nub ( [mn - (sum g) | g <- oneZeroGroups ] ) > > highest = minimum ( (n*n):[mn - (sum g) | g <- cellGroups] ) > > > > {- Utility functions to extract a single row, column, or diagonal. -} > > gridRow grid n _ y = [grid ! (xx, y) | xx <- [1..n]] > > gridCol grid n x _ = [grid ! (x, yy) | yy <- [1..n]] > > diag1 grid n = [grid ! (i, i) | i <- [1..n]] > > diag2 grid n = [grid ! (i, n - i + 1) | i <- [1..n]] > > > > {- Returns the number of times n appears n list xs -} > > count n xs = length $ filter ((==) n) xs > > > > ---------------------------------------------------------------------- > > ----------------------------- > > > > Am Sonntag, 2. Juli 2006 01:58 schrieb Brent Fulgham: > >> We recently began considering another benchmark for the shootout, > >> namely a Magic Square via best-first search. This is fairly > >> inefficient, and we may need to shift to another approach due to the > >> extremely large times required to find a solution for larger squares. > >> > >> I thought the Haskell community might be interested in the > >> performance we have measured so far (see "http:// > >> shootout.alioth.debian.org/sandbox/fulldata.php? > >> test=magicsquares&p1=java-0&p2=javaclient-0&p3=ghc-0&p4=psyco-0" > >> > >> Interestingly, Java actually beats the tar out of GHC and Python for > >> N=5x5 (and I assume higher, though this already takes on the order of > >> 2 hours to solve on the benchmark machine). Memory use in GHC stays > >> nice and low, but the time to find the result rapidly grows. > >> > >> I was hoping for an order of magnitude increase with each increase in > >> N, but discovered that it is more like an exponential... > >> > >> Thanks, > >> > >> -Brent > > > > Cheers, > > Daniel > > > > -- > > > > "In My Egotistical Opinion, most people's C programs should be > > indented six feet downward and covered with dirt." > > -- Blair P. Houghton > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -------------------------------- > David F. Place > mailto:d@vidplace.com -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton

1 0

Trading with Haskell
by Joel Reymont 05 Jul '06

05 Jul '06

Is there anyone trading with Haskell or interested in doing it? Thanks, Joel -- http://wagerlabs.com/

3 3

Re: Comments from Brent Fulgham on Haskell and the shootout
by Simon Marlow 05 Jul '06

05 Jul '06

John Meacham wrote: > On Tue, Jun 27, 2006 at 02:58:05PM +0100, Simon Marlow wrote: > >>>.. (and jhc already generates native C code, so it will have at least >>>one substantial advantage over GHC) ... >> >>Compiling via C is a dead end. We realised this about 5 years ago, and >>yet we still haven't managed to shake off the C backend from GHC, but I >>remain hopeful that one day we will. /me heads for the cafe... > > Out of curiosity, compiling via C as opposed to what? c--? Parrot? JVM? C-- ultimately, but in the meantime GHC's built in native-code generator. Our NCG is quite reasonable, and we plan to push it forward in various ways to improve the generated code. There's a wiki page with some ideas: http://hackage.haskell.org/trac/ghc/wiki/BackEndNotes Cheers, Simon

6 13