- Haskell-Cafe - Haskell.org

2-CNF Sat algorithm/haskell code
by Ron de Bruijn 17 Mar '04

17 Mar '04

Dear Haskellers, Today I searched over more than an hour on the web to find an implementation of an algorithm that was first written in the 1970's that solves 2-Conjuntive Normal Form logical sentences in polynomial time. The only thing I could find were some homework assignments for students of universities and I learned that there exist an algoritm for 2-CNF. Although I am a student, what I am doing is no homework. I believe the datastructure used was a strongly connected graph (perhaps this rings any bells). If you don't know any implementation in any imperative language or functional language (not to far off when compared to Haskell), a clear pseudo-code description, either written by yourself or a URL to a webpage/paper with that information would also be very welcome. Thanks in advance, Ron de Bruijn P.S. This is really offtopic, but I would like to hear some opinions about this project: http://www.supercompilers.com/ I don't know whether they are for real, but when this works it would greatly impacts the use of inefficient functional programs(when applied to it ofcourse). Like in Haskell, a lot of programs could be written like: [x|x<-someList, somePred x] Although they computationally seen would be very slow, without "supercompilation", with they would perform just as good as some smart way of doing it. __________________________________ Do you Yahoo!? Yahoo! Mail - More reliable, more storage, less spam http://mail.yahoo.com

2 1

Building Haddock on Windows
by Bayley, Alistair 16 Mar '04

16 Mar '04

Has anyone recently built Haddock on Windows? I'm invoking configure and make from Cygwin bash. Configure takes a couple of hours, and then make produces a load of errors (see below). If anyone has a ready-made .exe I'd be happy to use that. I just want to use Haddock, not modify it. Alistair. ---- output from make: [All appears ok up to this point] make[1]: Leaving directory `/cygdrive/h/haskell/haddock-0.6/glafp-utils' make[1]: Entering directory `/cygdrive/h/haskell/haddock-0.6/haddock' ------------------------------------------------------------------------ ===fptools== Recursively making `boot' in src html doc ... PWD = /cygdrive/h/haskell/haddock-0.6/haddock ------------------------------------------------------------------------ ------------------------------------------------------------------------ ==fptools== make boot - --unix -wr; in /cygdrive/h/haskell/haddock-0.6/haddock/src ------------------------------------------------------------------------ test: 504: unknown operand M -optdep-f -optdep.depend -osuf o -H16m -O -package data -package text -package util -package net -fglasgow-exts -cpp Binary.hs BlockTable.hs Digraph.lhs FastMutInt.hs HaddockDB.hs HaddockHH.hs HaddockHtml.hs HaddockLex.hs HaddockModuleTree.hs HaddockParse.hs HaddockRename.hs HaddockTypes.hs HaddockUtil.hs HaddockVersion.hs HsLexer.lhs HsParseMonad.lhs HsParseUtils.lhs HsParser.hs HsSyn.lhs Html.hs Main.hs M: not found make[2]: [depend] Error 127 (ignored) ------------------------------------------------------------------------ ==fptools== make boot - --unix -wr; in /cygdrive/h/haskell/haddock-0.6/haddock/html ------------------------------------------------------------------------ ------------------------------------------------------------------------ ==fptools== make boot - --unix -wr; in /cygdrive/h/haskell/haddock-0.6/haddock/doc ------------------------------------------------------------------------ ------------------------------------------------------------------------ ===fptools== Finished making `boot' in src html doc ... PWD = /cygdrive/h/haskell/haddock-0.6/haddock ------------------------------------------------------------------------ make[1]: Leaving directory `/cygdrive/h/haskell/haddock-0.6/haddock' make[1]: Entering directory `/cygdrive/h/haskell/haddock-0.6/haddock' ------------------------------------------------------------------------ ===fptools== Recursively making `all' in src html doc ... PWD = /cygdrive/h/haskell/haddock-0.6/haddock ------------------------------------------------------------------------ ------------------------------------------------------------------------ ==fptools== make all - --unix -wr; in /cygdrive/h/haskell/haddock-0.6/haddock/src ------------------------------------------------------------------------ test: 504: unknown operand make INSTALLING=0 BIN_DIST=0 - --unix - --no-print-directory -r all test: 504: unknown operand H16m -O -package data -package text -package util -package net -fglasgow-exts -cpp -c Binary.hs -o Binary.o -ohi Binary.hi H16m: not found make[3]: [Binary.o] Error 127 (ignored) H16m -O -package data -package text -package util -package net -fglasgow-exts -cpp -c BlockTable.hs -o BlockTable.o -ohi BlockTable.hi H16m: not found make[3]: [BlockTable.o] Error 127 (ignored) H16m -O -package data -package text -package util -package net -fglasgow-exts -cpp -c Digraph.lhs -o Digraph.o -ohi Digraph.hi H16m: not found make[3]: [Digraph.o] Error 127 (ignored) [and it continues like this for a while...] ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

3 2

Haskell on Rotor CLI
by s_＠id.ru 16 Mar '04

16 Mar '04

Hi, All! Is there any project for running Haskell on the Rotor CLI? zelych --- Professional hosting for everyone - http://www.host.ru

1 0

AW: [Haskell-cafe] Haskell overview
by Markus.Schnell＠infineon.com 12 Mar '04

12 Mar '04

and for some days now Markus Schnell > -----Ursprüngliche Nachricht----- > Von: haskell-cafe-bounces(a)haskell.org > [mailto:haskell-cafe-bounces@haskell.org] Im Auftrag von Gour > Gesendet: Freitag, 12. März 2004 14:53 > An: haskell-cafe(a)haskell.org > Betreff: Re: [Haskell-cafe] Haskell overview > > > MR K P SCHUPKE (k.schupke(a)imperial.ac.uk) wrote: > > > Is it just me or is "citeseer.nj.nec.com" down? > > Same here :-( > > Sincerely, > Gour > > -- > Gour > gour(a)mail.inet.hr > Registered Linux User #278493 > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

Re: Polymorphic lists...
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

Just running through the implementation of some of the functions I mentioned, with the newtyped tuple version. Thought the run-time indexed code looked neat so I thought i'd post it: First the definition: newtype RNil = RNil () newtype RCons attribute relation = RCons (attribute,relation) class Relation relation instance Relation (RNil ()) instance Relation relation => Relation (RCons attribute relation) emptyRM :: RNil emptyRM = RNil () now the code: class Relation r => IndexRM' r a where indexRM' :: r -> Int -> Maybe a instance IndexRM' RNil a where indexRM' _ _ = Nothing instance IndexRM' r a => IndexRM' (RCons a r) a where indexRM' (RCons (a,_)) 0 = Just a indexRM' (RCons (_,r)) n = indexRM' r (n-1) instance IndexRM' r a => IndexRM' (RCons b r) a where indexRM' (RCons (_,_)) 0 = Nothing indexRM' (RCons (_,r)) n = indexRM' r (n-1) This finds the Nth value where 'n' is a normal integer. The last block repeats twice because one matches the case where the return type is the same, and the other is for then the return type and indexed value differ. This is why the return type is Maybe. With the compile time natural number lookup, the program will fail to compile if the types differ, but with the runtime lookup the type and the success cannot be determined (hence no functional dependancy) and returning Maybe makes the most sense. Regards, Keean.

1 0

Re: [Haskell-cafe] Haskell overview
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

Is it just me or is "citeseer.nj.nec.com" down? Keean.

3 2

Re: [Haskell-cafe] Passing types as arguments
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

You can pattern match on types - as I have been having much fun with recently ... you use multi-parameter type classes (with optional functional dependancies) to match types. Regards, Keean.

1 0

RE: [Haskell-cafe] Passing types as arguments
by Simon Peyton-Jones 12 Mar '04

12 Mar '04

We pass values as proxies for types extensively in the "Scrap your boilerplate" scheme. The paper is on my home page. The 'typeOf' function is a good example. Part II coming up shortly. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | ajb(a)spamcop.net | Sent: 12 March 2004 03:50 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Passing types as arguments | | G'day everyone. | | Some time ago a suggestion came up about passing types as arguments | to functions: | | http://www.haskell.org/pipermail/haskell/2003-June/012184.html | | As a matter of curiosity, the topic has come up again on the wiki: | | http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 | | For this example, we don't just want to pass types, we also want to | pattern match on them. | | I'm curious if anyone else has put any thought to this idea. Is it just | a syntax issue, or are there bad interactions with other parts of the | type system? | | Cheers, | Andrew Bromage | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Passing types as arguments
by ajb＠spamcop.net 12 Mar '04

12 Mar '04

G'day everyone. Some time ago a suggestion came up about passing types as arguments to functions: http://www.haskell.org/pipermail/haskell/2003-June/012184.html As a matter of curiosity, the topic has come up again on the wiki: http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 For this example, we don't just want to pass types, we also want to pattern match on them. I'm curious if anyone else has put any thought to this idea. Is it just a syntax issue, or are there bad interactions with other parts of the type system? Cheers, Andrew Bromage

1 0

Haskell overview
by ATWOOD,JOHN (HP-Corvallis,ex1) 11 Mar '04

11 Mar '04

> A colleague with a mathematics and Lisp background is wanting to learn > more about Haskell. The books he's looked at concentrate more on building > up from the basics and getting the syntax right, etc., whereas really he's > looking more of a top-down view that makes Haskell's features and behavior > clear and relates them to category theory, etc. Would anyone be able to > suggest some good references? > >-- Mark For lispers, I like to point out this sentence of section 6.4 of the Haskell 98 Report: Haskell provides several kinds of numbers; the numeric types and the operations upon them have been heavily influenced by Common Lisp and Scheme. For mathematicians, I'd recommend the first 5 pages of: Calculating Functional Programs, Jeremy Gibbons, 2002 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# calculating Then I'd mention the Acid Rain Theorem, Fusion Theorem, Wadler's _Theorems for Free!_. When I'd show some exemplary fp programs: Bridging the Algorithm Gap: A Linear-Time Functional Program for Paragraph Formatting. Oege de Moor and Jeremy Gibbons, 1999 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# para Financial Contracts: An Adventure in Financial Engineering, 2000 Simon Peyton Jones, Jean-Marc Eber, and Julian Seward http://www.lexifi.com/resources.html#paper Functional Specification of JPEG Decompression, and an Implementation for Free, Jeroen Fokker, 1995 http://citeseer.nj.nec.com/72092.html Modeling Web Interactions, Paul Graunke, Robert Bruce Findler, Shriram Krishnamurthi, Matthias Felleisen, 2003 http://citeseer.nj.nec.com/graunke03modeling.html Haskell Server Pages Functional Programming and the Battle for the Middle Tier, Erik Meijer, Dannyy van Velzen, 2000 http://citeseer.nj.nec.com/318262.html Writing High-Performance Server Applications in Haskell, Case Study: A Haskell Web Server, Simon Marlow, 2000 http://www.haskell.org/~simonmar/bib.html (about the 4th one down) And then, the more introductory material: Why Functional Programming Matters, John Hughes http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html and here's a summary of the paper: http://www.cs.auckland.ac.nz/~j-hamer/360/why-fp-matters.html Section 3.1.3 of SICP: http://mitpress.mit.edu/sicp/ Why no one uses functional languages, Philip Wadler, 1998 http://citeseer.nj.nec.com/wadler98why.html here's an old, but still relevant summary of some issues keeping fp from taking over the world: http://www.cs.colorado.edu/~zorn/cs5535/Fall-1997/haskell-summary.html Some general links: http://haskell.readscheme.org/ http://www.haskell.org Hope this isn't too overwhelming, but it was an opportunity for me to gather my thoughts. Enjoy, John Atwood

1 0