Re: Strafunski/overlapping instances in ghc-6.5
Christopher Brown wrote: Christian, Did you try the switch -fallow-overlapping-instances when compiling? Yes, but it doesn't seem to make much difference. Maybe a couple of more library files have not been translated with the above flag. http://article.gmane.org/gmane.comp.lang.haskell.glasgow.bugs/3625 In fact I became a problem with a Show instance and ghc-6.5.20060211 Christian OMDoc/HetsDefs.hs:649:0: Overlapping instances for Show AllMaps arising from use of `GHC.Show.$dmshowList' at OMDoc/HetsDefs.hs:649:0 Matching instances: instance (Show a, Show b, Show c, Show d, Show e, Show f) = Show (a, b, c, d, e, f) -- Imported from GHC.Show instance [overlap ok] Show AllMaps -- Defined at OMDoc/HetsDefs.hs:649:0 In the expression: GHC.Show.$dmshowList In the definition of `showList': showList = GHC.Show.$dmshowList In the definition for method `showList' ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Dumb guy needs help
Davey == Davey dude [EMAIL PROTECTED] writes: Davey Im new to Haskell, hugs in particular, and was hoping you could Davey help me solve a problem. It should be pretty easy. I have to Davey use hugs to create an expression data Exp = Plus Exp Exp| Sub Davey Exp Exp| Mult Exp Exp| Power Exp Exp | Number [Int] to define Davey a constant ex1 :: Exp that represents the function ((3*4) + Davey (2*(12^2))) - 2. Exp is an expression where numbers are Davey represented by a list of digits (540 is [5,4,0]). Got any Davey ideas. Any help is greatly needed! Expression ((3*4) + (2*(12^2))) - 2 consists of 2 subexpressions: ((3*4) + (2*(12^2))) and 2 connected by the `-' operator, so ex1 = Sub ex1_2 2 where ex1_2 is an Exp representing ((3*4) + (2*(12^2))) which is a sum (Plus .). -- WBR, Max Vasin. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
readChan and unGetChan?
Suppose the following happens: (1) Thread A calls readChan on an empty channel and waits (2) Thread B puts something to the read-end of the channel using unGetChan When a GHC program does this, both threads are blocked! Is it the behaviour we really want for unGetChan, or should we fix the implementation for Control.Concurrent.Chan? Thanks, Peng ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell] Strafunski
Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: [Haskell-cafe] Strafunski
Hi Chris, Changes in the libraries of GHC have broken Strafunski compatibility in the past. I have not upgraded to GHC 6.5 myself so I'm not sure if this is the case again. Which versions of DrIFT and Strafunski are you using? Based on what you write, it seems new instances for Typeable have been added to the libs (possibly using deriving), which means some of your own instances are now redundant. You'll have to remove them (which will then break compatibility of your code with 6.4.1, sigh). Alternatively, you may consider to switch from the drift-default mode of Strafunski to the deriving mode. This means that you will be relying on the Typeable+Data classes rather than on the Typeable +Term classes. You make the switch simply by changing the search path, all your strategic functions should work like before. I guess GHC 6.5 supports deriving both for Typeable and Data (personally, I prefer to use DriFT rather than the deriving clause, because it gives me a bit more control over visibility of instances). For details, see the section Supported models of functional strategies in the README file of StrategyLib. Regards, Joost -- Dr. ir. Joost Visser | Departamento de Informática phone +351-253-604461 | Universidade do Minho fax+351-253-604471 | mailto:[EMAIL PROTECTED] mobile +351-91-6253618 | http://www.di.uminho.pt/~joost.visser On Apr 3, 2006, at 3:41 PM, Christopher Brown wrote: Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: [Haskell-cafe] Strafunski
Joost, Thanks very much - this solved my problem! Cheers Chris. On 3 Apr 2006, at 17:03, Joost Visser wrote: Hi Chris, Changes in the libraries of GHC have broken Strafunski compatibility in the past. I have not upgraded to GHC 6.5 myself so I'm not sure if this is the case again. Which versions of DrIFT and Strafunski are you using? Based on what you write, it seems new instances for Typeable have been added to the libs (possibly using deriving), which means some of your own instances are now redundant. You'll have to remove them (which will then break compatibility of your code with 6.4.1, sigh). Alternatively, you may consider to switch from the drift-default mode of Strafunski to the deriving mode. This means that you will be relying on the Typeable+Data classes rather than on the Typeable +Term classes. You make the switch simply by changing the search path, all your strategic functions should work like before. I guess GHC 6.5 supports deriving both for Typeable and Data (personally, I prefer to use DriFT rather than the deriving clause, because it gives me a bit more control over visibility of instances). For details, see the section Supported models of functional strategies in the README file of StrategyLib. Regards, Joost -- Dr. ir. Joost Visser | Departamento de Informática phone +351-253-604461 | Universidade do Minho fax+351-253-604471 | mailto:[EMAIL PROTECTED] mobile +351-91-6253618 | http://www.di.uminho.pt/~joost.visser On Apr 3, 2006, at 3:41 PM, Christopher Brown wrote: Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] haskell@ archives, 1990-2000
I managed, with the help of some custom hacks, to convert Simon's tarball of the haskell@ archives from 1990-2000 into html. I've hosted the lot here: http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/threads.html I'm not sure these archives are available anywhere else, other than the tarball on SPJs page, here http://research.microsoft.com/~simonpj/haskell/haskell-email-11Sep1990-27Oct2000.gz Enjoy reading about the problems of n+k and why Haskell needs a binary IO class, way back in 1990 :) -- Don P.S. if you find oddities in the conversion, let me know. ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] haskell@ archives, 1990-2000
dons: I managed, with the help of some custom hacks, to convert Simon's tarball of the haskell@ archives from 1990-2000 into html. By the way, this was in the context of writing up the HWN-style news over that decade, here: http://haskell.org/haskellwiki/Old_news -- Don ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
state threads
In case anyone was wondering what this state-threads thing I keep talking about is, here is a sample implementation (in C) as well as a lot of documentation and FAQs that apply to haskell as well. http://state-threads.sourceforge.net/ it should be noted that the chief disadvantage of state threads in C is not an issue for haskell (requiring an alternate IO library) A form of state threads can be implemented in pure haskell using the Poor Man's Concurrency monad described here: http://citeseer.ist.psu.edu/claessen99functional.html assuming you have the ability to use an 'epoll' or 'select' mechanism. However, this is probably not a suitable implementation method for high performance haskell implementations and does not address foreign concurrent calls. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: Concurrency
On 31 March 2006 13:41, John Meacham wrote: I have tried to summarize the current thinking into a proposal on the wiki. http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/Concurrenc y I split it into 3 parts. the standard - all haskell' compilers must implement optional preemption - ability to preempt pure code, fairness guarentees, interleaved evaluation operators (merge, nmerge) optional OS threads - bound threads, SMP, reentrant concurrent FFI calls supported. comment or modify it at will. Great. Apart from my misgivings about allowing cooperative scheduling at all, here's a few comments on the proposal: - I wouldn't include threadWaitRead, threadWaitWrite, or threadDelay at all. These can all be implemented using FFI, so don't belong in the concurrency library. Their presence is largely historical. - yield bothers me a little. If it weren't for cooperative systems, yield would be semantically a no-op, because the no-starvation guarantee means you never need it for correctness. I think it's ok, just a bit unsettling. - In the optional OS threads section it says allows multiple haskell threads to run at once - actually you can provide all that without allowing multiple haskell threads to run at once, eg. ghc-6.4.1 with -threaded. I'll modify it. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
On Sat, Apr 01, 2006 at 02:30:30PM +0400, Bulat Ziganshin wrote: new stacks can be allocated by alloca() calls. all these alloca-allocated stack segments can be used as pool of stacks assigned to the forked threads. although i don't tried this, my own library also used processor-specific method. so you alloca new big areas and then use 'longjmp' to jump back and forth within the same stack simulating many stacks? that is a neat trick. will confuse the hell out of the bohem garbage collector but I don't want to rely on that much longer anyway :) however, it would be a good thing to fall back to if no processor specific stack creation routine is available. this minimal threads library http://www.cs.uiowa.edu/%7Ejones/opsys/threads/ uses an interesting trick where it probes the setjmp structure to find the SP reasonably portably on any stack-based architecture. pretty clever. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Concurrency
On Fri, Mar 31, 2006 at 01:15:03PM -0800, John Meacham wrote: On Fri, Mar 31, 2006 at 04:21:26PM +0100, Simon Marlow wrote: Great. Apart from my misgivings about allowing cooperative scheduling at all, here's a few comments on the proposal: much much preferable to a standard that not everyone can implement. :) Are there potential users for the compromise interface? I had the impressions that those wanting concurrency needed the fairness guarantees. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re[2]: FFI, safe vs unsafe
Hello John, Monday, April 3, 2006, 12:53:05 PM, you wrote: new stacks can be allocated by alloca() calls. all these alloca-allocated stack segments can be used as pool of stacks assigned to the forked threads. although i don't tried this, my own library also used processor-specific method. so you alloca new big areas and then use 'longjmp' to jump back and forth within the same stack simulating many stacks? yes that is a neat trick. will confuse the hell out of the bohem garbage collector but I don't want to rely on that much longer anyway :) setjmp/longjmp is not compatible with C++ exception handling (because stack unwinding will be confused :) ). may be this GC also don't compatible with setjmp/longjmp in any case? it will be cool to extend jhc with multi-threading -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
terminating instances
GHC 6.4 has rather conservative constraints on instances to guarantee
termination. GHC 6.5 has more liberal constraints; see
http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/FlexibleInstances
Unfortunately instances generated by newtype-deriving need not satisfy
either of these constraints (but the newtypes are required to be
non-recursive). I can't construct a problem example for the 6.4 rules
(but nor is there an obvious termination ordering). However the following
is non-terminating (caught by the depth limit) for GHC 6.5:
class C a where foo :: a - Bool
-- instance C (f (Maybe a) a a) = C (Bar f a)
newtype Bar f a = Bar (f (Maybe a) a a) deriving C
instance C (Bar (,,) a) = C (a,b,c) where
foo (a,b,c) = foo (Bar (Just a,a,a))
f = foo ('a', 'b', 'c')
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Concurrency
On Mon, Apr 03, 2006 at 11:38:08AM +0100, Ross Paterson wrote: On Fri, Mar 31, 2006 at 01:15:03PM -0800, John Meacham wrote: On Fri, Mar 31, 2006 at 04:21:26PM +0100, Simon Marlow wrote: Great. Apart from my misgivings about allowing cooperative scheduling at all, here's a few comments on the proposal: much much preferable to a standard that not everyone can implement. :) Are there potential users for the compromise interface? I had the impressions that those wanting concurrency needed the fairness guarantees. quite the opposite IMHO. I think for most uses cooperative implementations will be not just just fine, but preferable. We really shouldn't call it a compromise interface, cooperative threading is often considered superior to pthreads/pre-emptive threading for a wide variety of tasks. After a lot of experience writing pthreads code from both the OS and application side, I find I agree. cooperative state-threads should always be the way to go by default when writing new code unless you absolutely need one of the features of pre-emptive threading. the tasks for which state-threads work well for are IO bound multiplexing tasks, pthreads are better for CPU-bound tasks. However, most uses of concurrency are for programs that interact with the user or the external world, as in they wait for an event from a variety of sources and respond to it quickly. The limiting factor isn't processing power, but how fast the events come, how fast you can redraw the screen, your network speed, etc. exactly what state-threading is best at. Most CPU bound tasks tend to be batch processing type things like compilers, which don't need concurrency to begin with. some info on the advantages and tradeoffs http://state-threads.sourceforge.net/docs/st.html although written from the point of view of network servers, a lot is relevant to other fields. Ideally, I'd like to provide both in jhc. But cooperative is a whole lot of bang for the buck. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
John Meacham wrote (... but I've reordered things):
My only real 'must-have' is that the 4 modes all can be explicitly and
unambiguously specified. I have opinions on the syntax/hints but
that is
more flexable.
I basically agree (the syntax discussion will take place in the years
after the semantics discussion), but...
I want programmers to have a way of saying this function might spend
a lot of time in foreign lands. These calls should be concurrent on
all implementations that support it (because some separately
developed/maintained piece of Haskell code might expect to run a
computation in the background), but if there are implementations that
don't support it shouldn't flag an error, because that would
encourage library writers to specify nonconcurrent when they can't
prove that it's safe, or make code needlessly nonportable.
Another way to look at it: You cannot decide whether the call
actually has to be done concurrently by just looking at the call site
- you'd need to look at the entire program, and asking people
(especially library writers) to state and guarantee global properties
of a program that might not even be finished yet is a Bad Thing.
Therefore, the concurrency annotation on the foreign import can only
be a hint on whether the foreign function is guaranteed to return
quickly or not; the actual requirement for the call to be
concurrent is hidden in the other code that expects to run at the
same time. Therefore, it would be wrong for an implementation that
doesn't support concurrent calls (reentrant or nonreentrant, I don't
care) to flag an error; the foreign import declaration correctly
refuses to give a guarantee that the function will return quickly.
The error is in the code that expects to run concurrently with a
foreign import on an implementation that doesn't support that (but of
course, a compiler can't detect such an error).
Another nice minor thing would be if haskell implementations were
required to ignore annotations starting with 'x-' for implementation
specific hints.
Sounds good. Syntax discussion postponed again ('x-' looks so mime-
typish. Could we add a meaningless 'application/' to the front? Just
kidding).
In my survey of when 'reentrant concurrent' was needed, I looked at
all
the standard libraries and didn't find anywhere it was actually
needed.
Are there some compelling examples of when it is really needed in a
setting that doesn't have OS threads to begin with? (I am not
asserting
they don't exist, I just want to see some example uses of this feature
to get a better handle on the implementation cost)
In my experience, reentrant calls are rare in non-GUI code, but they
become quite common in GUI code (OK, in some GUI libraries, there is
only one, called something like RunMainEventLoop, but then it runs
almost all of the time and is absolutely crucial). And with most GUI
libraries, the GUI's main event loop will refuse to cooperate well
with a Haskell's implementation's scheduler, so it will need to be
called as a concurrent foreign import if your application is to do
any background processing while waiting for events.
Other libraries that rely on callbacks would include the GLU
Tesselator that I already mentioned, as well as several packages for
solving optimisation problems. For those, concurrency would probably
only become an issue when they are used with a GUI (even if it's only
to display a progress bar).
Another reason why you don't see them in Haskell standard library
code might be that everyone prefers Data.List.sort to foreign import
ccall qsort.
Any particular reason hugs and GHC didn't use the state-threads
approach
out of curiosity? did it conflict with the push-enter model? (jhc
uses
the eval-apply model so I am more familier with that)
It was before my time. I guess it's because GHC uses a separate heap-
allocated Haskell thread, so it made sense not to bother to allocate
a separate C stack for every one of them. Don't know about Hugs.
It also implys that a function call will run on the same OS thread as
the OS thread the current haskell thread is running on.
This shouldn't be put into a standard, as the bound threads proposal
already gives a different guarantee about that, and both guarantees
taken together probably guarantee too much - taken together, they
probably mean every Haskell thread has to be an OS thread. It might
be an implementation-specific guarantee, unless the bound threads
become a part of the standard in their entirety.
'OS thread the current haskell
thread is running on' (GHC already doesn't when bound threads arn't
used
I am led to believe?)
There should be no such thing as the 'OS thread the current haskell
thread is running on' in any standard; OS thread identity is only
observed through the FFI.
this means that things like 'log' and 'sin' and
every basic operation goes through the FFI
Re: [Haskell-cafe] Haskell on Pocket PC?
Hi Neil, Thanks for your reply. Starting from YHC porting pages the only source for Win32 port I found is WinHaskell. [http://www-users.cs.york.ac.uk/~ndm/projects/winhaskell.php] I have not yet found which port it is: Hugs, YHc, ...? Also there is a thing called WinHugs at http://www-users.cs.york.ac.uk/~ndm/projects/winhugs.php but I could not find source download for this one. Speaking about YHC: 1) So far I found only a development source for GCC which for the complete build needs not only GMP, but GHC as well. The last one is needed, correct me if I am wrong, for building YHC, but not for YHi. Correct? Is porting Hugs harder then YHC? What do you think? I have successfuly compiled and run Hugs on NetBSD. Hugs compilation does not require GHC. So may be (at least for intepreter) Hugs is easier to port then YHC/YHi? cheers, Dima On 3/31/06, Neil Mitchell [EMAIL PROTECTED] wrote: Hi, If I was doing a Haskell port to PPC Windows Mobile, I'd start with Yhc. If you port a small, portably written runtime (Yhi) in C, then you get everything else for free. There was some talk of a palm port of Yhi, and the only issues that came up were: * GMP is a dependancy, so you'll need to get GMP on Windows mobile. * Palm doesn't have a real file system, this isn't true on Windows Mobile. Yhc also compiles natively with Visual Studio, which should make this even easier for you. 1) Haskell learning tool, so small code snipets could be entered and run directly on hand-held (REPL). See Yhe, which does this (its not finished yet, but finishing it shouldn't be much work) 2) Running on PPC Haskell applications cross-compiled on host PC. Yhc has portable bytecode, hence any program is already cross-compiled to every platform. b) Porting/compiling to .NET CLR? Yhc can already compile to .NET CLR if that helps. c) Porting/compiling source code Yhc is pure Haskell, and at some point will be able to be run by Yhc, then you'll have all these things for free. 4) And finally, do any projects already exist in this area? There have been various projects to port nhc and then Yhc to PalmOS, which is probably a harder challenge than Windows Mobile. I used an older version of Windows CE and the porting required for Visual Studio projects was minimal. If you need any Yhc specific help with the changes, feel free to email the Yhc mailing list (yhc -at- haskell.org) view the documentation (http://www.haskell.org/haskellwiki/Yhc), or ask on the Haskell IRC (I'm ndm). Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Distributing monadic(?) functions across dyadic functions
On Sun, 02 Apr 2006, Jared Updike [EMAIL PROTECTED] wrote: Something like distribute fst (==) where distribute f op x y = f x `op` f y A function like this has been suggested for the standard libraries a couple of times before. Someone suggested the name on, which I quite like: (*) `on` f = \x y - f x * f y unionBy (distribute fst (==)) listOfPairs1 listOfPairs2 unionBy ((==) `on` fst) xs ys I think on makes the code rather readable: union by equality on first. -- /NAD ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
I've revised my thinking about printing (total, finite) functions: I should have respected the notion that a printed representation can be cut-and-pasted back in at the prompt for evaluation to something equal to the original. I've also revised my implementation to this effect, so that functions (over suitable classes of types) are now instances of the classes Bounded, Enum, Eq, Ord and Show, with the desired printing, as demonstrated by this session transcript: not == not True not == id False id == (not . not) True fromEnum not 1 not == toEnum 1 True not (\x - case x of False - True; True - False) not == (\x - case x of False - True; True - False) True id :: Bool - Bool (\x - case x of False - False; True - True) const True :: Bool - Bool (\x - case x of False - True; True - True) () == () True () == (||) False fromEnum () 8 () == toEnum 8 True () (\x - case x of False - (\x - case x of False - False; True - False); True - (\x - case x of False - False; True - True)) The printing is a bit ugly, but it would be somewhat improved in Haskell' if the LambdaCase suggestion is accepted (see http://hackage.haskell.org/trac/haskell-prime/wiki/LambdaCase), i.e., without the arbitrary choice of variable, and slightly shorter representations. Printing of properly higher-order functions doesn't have the nice read-back property, but only because Haskell doesn't support patterns over (suitably finite, total) functions. (One can paste back in the printed rep. for (), for example, and successfully compare it to the original, but not something of type (Bool-Bool)-Bool.) I can't imagine I'm the first to play around with this sort of thing, but I wonder why instances like these ought not be included in the Prelude. The functions are treated in a fully extensional manner, so I think it's all quite kosher. The ideas break down for partial functions, of course, but then so do the usual instances for enumerated data types (we can't successfully compare True with undefined, for example). And although the Ord and Enum instances are somewhat arbitrary, they are coherent with each other, generated in a principled fashion and agree with common practices (Ord and Enum for enumerated data types are themselves somewhat arbitrary). I suppose there's an argument from an efficiency perspective, but we don't prevent derivation of Eq for recursive types on the grounds that someone might compare huge trees. Here are the instances used above (well, the headers anyway), including products for good measure: instance (Enum a, Bounded a, Enum b, Bounded b) = Bounded (a-b) where ... instance (Enum a, Bounded a, Enum b, Bounded b) = Enum (a - b) where ... instance (Enum a, Bounded a, Eq b) = Eq (a-b) where ... instance (Enum a, Bounded a, Enum b, Bounded b, Eq b) = Ord (a - b) where ... instance (Enum a, Bounded a, Show a, Show b) = Show (a-b) where ... instance (Bounded a, Bounded b) = Bounded (a,b) where ... instance (Enum a, Bounded a, Enum b, Bounded b) = Enum (a,b) where ... -- Fritz On Apr 1, 2006, at 2:01 AM, Fritz Ruehr wrote: You can use type classes to implement this for *finite* functions, i.e., total functions over types which are Enum and Bounded (and Show-able), using for example a tabular format for the show: putStr (show (uncurry ())) (False,False) False (False,True)False (True,False)False (True,True) True ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Breaking up long lines
Neil Mitchell wrote: The indentation rules are quite complex, but just type your code sensibly indented and it will probably just work. My biggest problem in this area was following haskell-mode's defaults too strictly. I found that things ended up indented more than was necessary for clear layout, so wasting a lot of the space I had available. Pete ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on Pocket PC?
Hi, Starting from YHC porting pages the only source for Win32 port I found is WinHaskell. [http://www-users.cs.york.ac.uk/~ndm/projects/winhaskell.php] That's an entirely separate project, it just uses Yhc/GHC/Hugs. Thats the things about the Yhc port to Windows - its not a port, Yhc just natively supports Windows. Get the standard source: darcs get http://www.cs.york.ac.uk/fp/darcs/yhc-devel src/runtime/BCKernel/msvc and you'll find MSVC (Microsoft Visual C) projects for 2003 and 2005. From the root of the darcs tree, if you have either MSVC installed, makefile yhi and it will get built. See [http://www.haskell.org/haskellwiki/Yhc/Building] for details of how to build on Windows. Also there is a thing called WinHugs at http://www-users.cs.york.ac.uk/~ndm/projects/winhugs.php but I could not find source download for this one. Thats part of Hugs, just check out Hugs from CVS and You'll have that. Entirely unrelated to Yhc. 1) So far I found only a development source for GCC which for the complete build needs not only GMP, but GHC as well. The last one is needed, correct me if I am wrong, for building YHC, but not for YHi. Correct? Yhi is the runtime, that requires a C compiler and GMP (GMP could be massaged out relatively easily) Yhc is the compiler, that requires a Haskell 98 compiler. Hugs or GHC can be used. Give us a month or so, and Yhc will support Yhc. At that point you'll be able to compile Yhc using Yhc, and run the result using Yhi. This is an easy cross-compile, since all compiles are done to a portable bytecode. Is porting Hugs harder then YHC? What do you think? We have had a lot of success and getting some really weird Yhc ports done in under an hour, so I'd day Yhc is very portable. I'd be shocked if you couldn't port Yhi in a single day. Never tried with Hugs. I have successfuly compiled and run Hugs on NetBSD. Hugs compilation does not require GHC. So may be (at least for intepreter) Hugs is easier to port then YHC/YHi? Today, yes, Hugs is easier. Once Yhc can compile Yhc (something we're working on, and won't be long, a few months tops), a port of Yhi gives you Yhc for free. Yhc has one of its stated aims as being the most portable compiler. The one thing that might make it harder for Hugs is that the make system for Hugs is based on having Cygwin installed. There are Visual Studio project files for the actual main .exe, but the rest is built inside Cygwin. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Efficient Sets for Small Enumerations
Often when writing algorithms which involve set operations on small enumerations, I start off using Data.Set. I soon find performance requires rewriting that code to use bitwise operations. I miss the nice interface of Data.Set and the type checking of using a proper data type. So, as an exercise in writing a library, I wrote out an implementation of bitwise set operations using the interface of Data.Set with a couple of extensions. It provides an abstract interface and type checking. Using GHC -O3, code compiles right down to the primitive bit-twiddling operators. My example program (a sudoku solver) runs several times faster. I'll be grateful for any feedback on this. Perhaps something like it would be useful included in the standard libraries. Cheers, David EnumSet.hs Description: Binary data David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] generics question 2
Hi Ralf, I'm looking for a function like extT but with more general type: (t a - s a) - (t b - s b) - (t a - s a) Is there such a thing in the generics library? Thanks, Frederik -- http://ofb.net/~frederik/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Efficient Sets for Small Enumerations
David F. Place d at vidplace.com writes: I'm currently writing and evolution to the standard collection package that can be found here: http://darcs.haskell.org/packages/collections/ We integrate your module there. What would you say? Cheers, JP. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Strafunski
Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Strafunski
Christopher Brown wrote: Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Did you try the switch -fallow-overlapping-instances when compiling? Cheers Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Strafunski
Christian, Did you try the switch -fallow-overlapping-instances when compiling? Yes, but it doesn't seem to make much difference. Cheers, Chris. Cheers Christian Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Efficient Sets for Small Enumerations
On Apr 3, 2006, at 10:02 AM, Jean-Philippe Bernardy wrote: I'm currently writing and evolution to the standard collection package that can be found here: http://darcs.haskell.org/packages/collections/ We integrate your module there. What would you say? Sure. I'd be honored. David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strafunski
Hi Chris, Changes in the libraries of GHC have broken Strafunski compatibility in the past. I have not upgraded to GHC 6.5 myself so I'm not sure if this is the case again. Which versions of DrIFT and Strafunski are you using? Based on what you write, it seems new instances for Typeable have been added to the libs (possibly using deriving), which means some of your own instances are now redundant. You'll have to remove them (which will then break compatibility of your code with 6.4.1, sigh). Alternatively, you may consider to switch from the drift-default mode of Strafunski to the deriving mode. This means that you will be relying on the Typeable+Data classes rather than on the Typeable +Term classes. You make the switch simply by changing the search path, all your strategic functions should work like before. I guess GHC 6.5 supports deriving both for Typeable and Data (personally, I prefer to use DriFT rather than the deriving clause, because it gives me a bit more control over visibility of instances). For details, see the section Supported models of functional strategies in the README file of StrategyLib. Regards, Joost -- Dr. ir. Joost Visser | Departamento de Informática phone +351-253-604461 | Universidade do Minho fax+351-253-604471 | mailto:[EMAIL PROTECTED] mobile +351-91-6253618 | http://www.di.uminho.pt/~joost.visser On Apr 3, 2006, at 3:41 PM, Christopher Brown wrote: Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
It solves sudoku puzzles. (What pleasure do people get by doing these in their heads?!?) probably the same you get from writing programs?-) figuring out the rules, not getting lost in complexity, making something difficult work.. They are probably asking the same question: why take hours to write a program to do it when with my mad sudoku solving skills I can solve it in X seconds? My roommate is like this. if we just throw raw computing power at the problem (in-place array updates, bitvectors, multiprocessors, ..), wouldn't they be justified? but as soon as we try to take their skills and encode them in our programs, things become more interesting (do computers really play chess?-). I would say because they have chosen the wrong language for this problem :-) Solving Sudoku is a typical finite domain constraint problem. Thus, a language with constraint solving facilities like Curry (a combination of Haskell and constraint logic programming) is much better suited. Actually, I wrote a Sudoku solver in Curry and the actual code for the solver is 10 lines of code which is compact and well readable (if you are familiar with Haskell), see http://www.informatik.uni-kiel.de/~curry/examples/CLP/sudoku.curry interesting. I haven't yet got round to installing Curry and trying this, but I assume that this declarative specification, under a finite domain constraint solver, is not just an effective implementation, but an efficient one, right? if yes, it is really impressive how constraint propagation has managed to make essentially the same code that, as a mere functional logic program, would be effective, but hardly useable, so much more efficient, just by imposing a different evaluation strategy on it. and the factoring into constraint generation and constraint propagation under some strategy is nice as well. my own Sudoku solver (yes, me too - see attached, but only after you've written your own!-) uses simple hand-coded constraint propagation to limit the space for exhaustive search - some puzzles are solved by constraint propagation only, and even where guesses are used, each guess is immediately followed by propagation, to weed out useless branches early, and to deduce consequences of each guess before asking for the next one. the good old game, start with generatetest, then move the tests forward, into the generator. I've only coded the two most useful groups of constraints (when there's only a single number left for a position, or when there is only a single position left for a number). there are other deductions one does in by-hand solving, and I'm not an experienced sudoku solver myself, so I don't even know more than a few such rules yet, but these particular two seem sufficient to get acceptable performance even under ghci/hugs, so why do more?-) (*) [by acceptable, I mean that my sequence of 5 test puzzles is solved in less than 20 seconds on a 2GHz Pentium M; no idea how that compares to the most efficient solvers] since I haven't factored out the constraint propagation into a general module, the core of my code is a lot longer than the Curry version (about 60 additional lines, though I'm sure one could reduce that;-). the only negative point I can find about the Curry example is that it isn't obvious what tricks the FD-constraint solver is using (ie., it would be nice to have a concise language for expressing propagation techniques, and then explicitly to apply a strategy to the declarative specification, instead of the implicit, fixed strategy of the built-in solver). for instance, I assume that Michael's declarative specification implicitly allows the built-in solver to use the first group of constraints I mentioned (only a single possible number left for a position), but does it use the second group (only a single position left to place a number in a particular line/column/block)? my guess is that no, it doesn't, although it wouldn't be difficult to change that - just have the declarative specification express the dual puzzle as well (assigning positions to numbers instead of numbers to positions). is this correct, or is that dual reading already implied? perhaps Haskell should have Control.Constraint.* libraries for generalized constraint propagation (and presumably for constraint handling rules as well, as they are so popular nowadays for specifying Haskell's type classes)? cheers, claus (*) actually, that was a bit disappointing!-( I was hoping for some fun while trying to encode more and more clever rules, but not much of that seems to be required. Sudoku.hs Description: Binary data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
Claus Reinke wrote: It solves sudoku puzzles. (What pleasure do people get by doing these in their heads?!?) probably the same you get from writing programs?-) figuring out the rules, not getting lost in complexity, making something difficult work.. From a human standpoint, there are some puzzles that are much harder than others. This also applies to the few programs that I have seen. It is this variety of complexity that makes it interesting. They are probably asking the same question: why take hours to write a program to do it when with my mad sudoku solving skills I can solve it in X seconds? My roommate is like this. if we just throw raw computing power at the problem (in-place array updates, bitvectors, multiprocessors, ..), wouldn't they be justified? but as soon as we try to take their skills and encode them in our programs, things become more interesting (do computers really play chess?-). You can go get the 36,628 distict minimal puzzles from http://www.csse.uwa.edu.au/~gordon/sudokumin.php that have only 17 clues. Then you can run all of them through your program to locate the most evil ones, and use them on your associates. :) This also gave me a way to statistically measure if a new deductive step made much of a difference (or if it made no difference). Histograms and gnuplot helped. [snip Curry language example] my own Sudoku solver (yes, me too - see attached, but only after you've written your own!-) uses simple hand-coded constraint propagation to limit the space for exhaustive search - some puzzles are solved by constraint propagation only, and even where guesses are used, each guess is immediately followed by propagation, to weed out useless branches early, and to deduce consequences of each guess before asking for the next one. the good old game, start with generatetest, then move the tests forward, into the generator. I've only coded the two most useful groups of constraints (when there's only a single number left for a position, or when there is only a single position left for a number). there are other deductions one does in by-hand solving, and I'm not an experienced sudoku solver myself, so I don't even know more than a few such rules yet, but these particular two seem sufficient to get acceptable performance even under ghci/hugs, so why do more?-) (*) I have two versions of a solver. The first is a re-write of GDANCE bu Knuth to solve Sudoku efficiently as a binary cover problem. (see http://www-cs-faculty.stanford.edu/~knuth/programs.html ) This uses the Dancing Links algorithm implemented with STRef's and is very fast. The second uses a different encoding to look for clever deductions. This alone solves some easy problems and comes very close before getting stuck on most. There are few though that start with 17 hints and only discover one or two more by logic before getting stuck. These are the most evil of all. You might be interested in the deductions described at http://www.sudokusolver.co.uk/ [by acceptable, I mean that my sequence of 5 test puzzles is solved in less than 20 seconds on a 2GHz Pentium M; no idea how that compares to the most efficient solvers] I could run ~20,000 puzzles in a couple of hours. (The collection was smaller then). perhaps Haskell should have Control.Constraint.* libraries for generalized constraint propagation (and presumably for constraint handling rules as well, as they are so popular nowadays for specifying Haskell's type classes)? Did you see the monad at http://haskell.org/hawiki/SudokuSolver ? Perhaps you could generalize that. cheers, claus (*) actually, that was a bit disappointing!-( I was hopingfor some fun while trying to encode more and more clever rules, but not much of that seems to be required. You need more than 5 examples. The truly evil puzzles are rarer than that. Go get the set of minimal puzzles and see how far your logic takes you. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
Chris wrote: You need more than 5 examples. The truly evil puzzles are rarer than that. Go get the set of minimal puzzles and see how far your logic takes you. Chris elucidated some of my questions before I finished writing my email... Claus wrote: (*) actually, that was a bit disappointing!-( How much harder is the problem of generating (hard/medium/easy) (solvable) Sudoku puzzles? Are all puzzles solvable (that don't break the rules at any point)? I imagine a simple way is to start with a correctly saturated grid of numbers and then start randomly shooting holes in it and testing if it is still solvable (either unambiguously or ambiguously) with your Sudoku solver? A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles? Is this a more interesting problem to try to solve (generating) rather than solving puzzles? I haven't investigated it much but I thought about it when I was writing YASS (Yet Another Sudoku Solver) of my own. What makes a Sudoku puzzle fiendish? Just the amount of missing information, the amount of lookahed required? Jared. P.S. Another interesting problem could be trying other number arrangements besides 9x9, e.g. hexadecimal puzzles... I wrote my solver to handle these but I never saw other than 9x9 puzzles to try it on (hence the idea of generating puzzles)... Is that because most people want puzzles to solve by hand instead of computer? -- http://www.updike.org/~jared/ reverse )-: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Strafunski/overlapping instances in ghc-6.5
Christopher Brown wrote: Christian, Did you try the switch -fallow-overlapping-instances when compiling? Yes, but it doesn't seem to make much difference. Maybe a couple of more library files have not been translated with the above flag. http://article.gmane.org/gmane.comp.lang.haskell.glasgow.bugs/3625 In fact I became a problem with a Show instance and ghc-6.5.20060211 Christian OMDoc/HetsDefs.hs:649:0: Overlapping instances for Show AllMaps arising from use of `GHC.Show.$dmshowList' at OMDoc/HetsDefs.hs:649:0 Matching instances: instance (Show a, Show b, Show c, Show d, Show e, Show f) = Show (a, b, c, d, e, f) -- Imported from GHC.Show instance [overlap ok] Show AllMaps -- Defined at OMDoc/HetsDefs.hs:649:0 In the expression: GHC.Show.$dmshowList In the definition of `showList': showList = GHC.Show.$dmshowList In the definition for method `showList' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient Sets for Small Enumerations
On Monday 03 April 2006 14:19, David F. Place wrote: Often when writing algorithms which involve set operations on small enumerations, I start off using Data.Set. I soon find performance requires rewriting that code to use bitwise operations. I miss the nice interface of Data.Set and the type checking of using a proper data type. So, as an exercise in writing a library, I wrote out an implementation of bitwise set operations using the interface of Data.Set with a couple of extensions. It provides an abstract interface and type checking. Using GHC -O3, code compiles right down to the primitive bit-twiddling operators. My example program (a sudoku solver) runs several times faster. I'll be grateful for any feedback on this. Perhaps something like it would be useful included in the standard libraries. I wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations? Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
since I haven't factored out the constraint propagation into a general module, the core of my code is a lot longer than the Curry version (about 60 additional lines, though I'm sure one could reduce that;-). the only negative point I can find about the Curry example is that it isn't obvious what tricks the FD-constraint solver is using Curry does not have a constraint solver of its own. It simply delegates all constraints to the FD solver of SICStus Prolog. The all_different constraint subsumes the rules that you describe, depending on the consistency algorithm used. FD solvers implement general but efficient algorithms that are much more complex than a few simple rules. See http://www.sics.se/sicstus/docs/latest/html/sicstus/Combinatorial-Constraints.html#Combinatorial%20Constraints for the SICStus FD all_different documentation. (ie., it would be nice to have a concise language for expressing propagation techniques, and then explicitly to apply a strategy to the declarative specification, instead of the implicit, fixed strategy of the built-in solver). CHR is meant as a highlevel language for expressing propagation. It (currently) does not include a strategy language though. Cheers, Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
Jared Updike wrote: Chris wrote: You need more than 5 examples. The truly evil puzzles are rarer than that. Go get the set of minimal puzzles and see how far your logic takes you. Chris elucidated some of my questions before I finished writing my email... Claus wrote: (*) actually, that was a bit disappointing!-( How much harder is the problem of generating (hard/medium/easy) (solvable) Sudoku puzzles? I pursued this line of attack as well. I could not generate the hardest puzzles, though I was working without studying other's approaches. Are all puzzles solvable (that don't break the rules at any point)? All well formed problems have exactly one solution. It is always solvable by, at worst, brute force. I imagine a simple way is to start with a correctly saturated grid of numbers and then start randomly shooting holes in it and testing if it is still solvable (either unambiguously or ambiguously) with your Sudoku solver? That method works poorly. A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles? Proper puzzle have exactly one solution, accept no substitute. A problem is minimal (a partial order) if removing any single hint creates additional solutions. So the goal is build a minimal problem with as few hints as possible. The smallest number of hints achieved to date is 17, but there is no proof that a 16 hint puzzle is impossible. Is this a more interesting problem to try to solve (generating) rather than solving puzzles? I haven't investigated it much but I thought about it when I was writing YASS (Yet Another Sudoku Solver) of my own. What makes a Sudoku puzzle fiendish? Just the amount of missing information, the amount of lookahed required? A measure of difficulty is more subjective. Different programs will make luckier guesses on any specific problem. So I consider how many blanks are left when the pure logic program gets stuck to be my favorite difficulty metric. These were the worst from the list of 17's (left to right, top to bottom) : - - - - - 6..8..2.1...71.25...3..442.1...3..7..6.5. ...8...17.6.35...26..4..7...21.4...7.3...8..1 .9..25..36.3.6...4..81...7.8..9..23...67. 1...2..6.7.58.15.3.474..7..2.5...6..1 5...8.2..74..2.5...678..4..6.7...1...5.3.4... My puzzle generator worked like this: Start with an empty grid and randomly add allowed hints until the number of solutions falls to 1. Now try and remove hints while keeping the number of solutions exactly 1. The performance of this was erratic, but occasionally produced puzzles with as few as 20 to 22 hints. There was a few fairly evil spawn of my generator: .2.|...|58. 6..|9..|..1 3..|.7.|6.. ---+---+--- ...|.65|... ...|...|1.. ...|.32|.97 ---+---+--- ...|...|.38 .59|...|... ..4|...|2.. .5.|1..|... 6..|7..|... 4.8|.63|... ---+---+--- .1.|...|98. .6.|...|... 97.|.28|... ---+---+--- ...|..5|..1 ...|93.|.4. ...|...|2.7 1.6|...|..5 ...|.7.|.21 3..|...|.8. ---+---+--- ...|8..|1.6 ...|.1.|9.. ...|..9|.7. ---+---+--- ...|4.6|... ..2|..3|... 857|...|... I like that they have two 3x3 sections which are without any hints. Jared. P.S. Another interesting problem could be trying other number arrangements besides 9x9, e.g. hexadecimal puzzles... I wrote my solver to handle these but I never saw other than 9x9 puzzles to try it on (hence the idea of generating puzzles)... Is that because most people want puzzles to solve by hand instead of computer? Yes -- http://www.updike.org/~jared/ reverse )-: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Strafunski
Hello Christopher, the trick is that there is another approach to generics, largely based on the Strafunski. it's named scrap your boilerplate! (SYB) and it's implementation is included in ghc. you can find 3 SYB papers and it seems better to just learn and use this approach to generic programming instead of Strafunski. in this case you will got automatic Typeable derivation, among other things -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient Sets for Small Enumerations
On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote: wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations? I thought about that some. Since the set representation is based completely on the enumeration, it would be possible for the type being collected to have a different implementation of Ord. For instance: newtype LowerCaseAlpha = LCA Char deriving (Eq, Show) instance Enum LowerCaseAlpha where fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') toEnum x = LCA $ toEnum $ x + (fromEnum 'a') instance Ord LowerCaseAlpha where compare (LCA a) (LCA b) | a == b = EQ | a b = LT | a b = GT Perverted, but possible. David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Code Review: Sudoku solver
Hello it seems that sudoku solver may be a good candidate for nofib suite / language comparison shootout -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient Sets for Small Enumerations
On 4/3/06, David F. Place [EMAIL PROTECTED] wrote: On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote: wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations? I thought about that some. Since the set representation is based completely on the enumeration, it would be possible for the type being collected to have a different implementation of Ord. For instance: newtype LowerCaseAlpha = LCA Char deriving (Eq, Show) instance Enum LowerCaseAlpha where fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') toEnum x = LCA $ toEnum $ x + (fromEnum 'a') instance Ord LowerCaseAlpha where compare (LCA a) (LCA b) | a == b = EQ | a b = LT | a b = GT Perverted, but possible. I don't think there is a requirement for the Ord class to be equal to compare a b = compare (toAscList a) (toAscList b). I'd say it's safe to simply compare the bits representation. Besides, I've integrated your module to the package I'm busy setting up. http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs (I'm accepting patches -- most notably if someone wishes to complete the haddock documentation) FWIW, it passed the standard regression testsuite for Sets flawlessly. I'm thinking of removing the UniverseSet class though. It seems to me that Bounded serves the purpose just right. Cheers, JP. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Distributing monadic(?) functions across dyadic functions
Nils Anders Danielsson wrote: A function like this has been suggested for the standard libraries a couple of times before. Someone suggested the name on, which I quite like: (*) `on` f = \x y - f x * f y Thanks! I always wanted to be someone. :-) Here's the link. http://www.haskell.org//pipermail/haskell-cafe/2004-December/007917.html - Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient Sets for Small Enumerations
On Apr 3, 2006, at 5:38 PM, Jean-Philippe Bernardy wrote: I don't think there is a requirement for the Ord class to be equal to compare a b = compare (toAscList a) (toAscList b). I'd say it's safe to simply compare the bits representation. Hmm. OK. Besides, I've integrated your module to the package I'm busy setting up. http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs Cool. (I'm accepting patches -- most notably if someone wishes to complete the haddock documentation) I'll look into it. FWIW, it passed the standard regression testsuite for Sets flawlessly. I do quality work. I'm thinking of removing the UniverseSet class though. It seems to me that Bounded serves the purpose just right. Does that mean we lose the unary `complement` function? I am rather fond of that. David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
bulat.ziganshin: Hello it seems that sudoku solver may be a good candidate for nofib suite / language comparison shootout It would also be nice to see some example sudoku solvers posted on an `Idioms' page on haskell.org: http://www.haskell.org/haskellwiki/Category:Idioms someone could just create a new page 'Sudoku' and add the phrase [Category:Idioms]] to the text, and it will be indexed. Seeing 4 or 5 solutions would be a useful tutorial, I'd imagine. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
Am Montag, 3. April 2006 18:52 schrieb Chris Kuklewicz:
Claus Reinke wrote:
It solves sudoku puzzles. (What pleasure do people get by doing
these in their heads?!?)
probably the same you get from writing programs?-) figuring out the
rules, not getting lost in complexity, making something difficult work..
Exactly, and I wrote a solver with a relatively elaborate strategy last year
(it was written incrementally, so the code is horrible, I always wanted to
rewrite it properly but never got to do it, hence I will not post it unless
asked to), to have both kinds of pleasure, figure out a strategy and teach it
to my computer.
From a human standpoint, there are some puzzles that are much harder than
others. This also applies to the few programs that I have seen. It is
this variety of complexity that makes it interesting.
They are probably asking the same question: why take hours to write a
program to do it when with my mad sudoku solving skills I can solve it
in X seconds? My roommate is like this.
if we just throw raw computing power at the problem (in-place array
updates, bitvectors, multiprocessors, ..), wouldn't they be justified?
but as soon as we try to take their skills and encode them in our
programs, things become more interesting (do computers really play
chess?-).
You can go get the 36,628 distict minimal puzzles from
http://www.csse.uwa.edu.au/~gordon/sudokumin.php that have only 17 clues.
Then you can run all of them through your program to locate the most evil
ones, and use them on your associates. :)
Well, I loaded them down and let my solver determine whether all of them have
a unique solution (they do), took 76 min 14.260 sec user time, hence roughly
0.125 secs per puzzle, so I dare say there are no evil ones among them
(However, Alson Kemp's solver from the HaWiki-page -- which, I don't know
why, is much faster than Cale Gibbard's -- took over 20 minutes to solve the
second
0 0 0 0 0 0 0 1 0
4 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0
0 0 0 0 5 0 6 0 4
0 0 8 0 0 0 3 0 0
0 0 1 0 9 0 0 0 0
3 0 0 4 0 0 2 0 0
0 5 0 1 0 0 0 0 0
0 0 0 8 0 7 0 0 0,
so these puzzles may be evil after all).
My solver needed to guess on 5,309 of the 36,628 17-hint puzzles, which I find
a bit disappointing -- the big disappointment was when neither I nor my
solver were able to solve the example from the hawiki-page without guessing
:-( --
does anybody know whether in a uniquly solvable sudoku-puzzle guessing is
never necessary, i.e. by proper reasoning ('if I put 6 here, then there must
be a 3 and thus the 4 must go there...' is what I call guessing) there is
always at least one entry determined?
This also gave me a way to statistically measure if a new deductive step
made much of a difference (or if it made no difference). Histograms and
gnuplot helped.
[snip Curry language example]
my own Sudoku solver (yes, me too - see attached, but only after
you've written your own!-) uses simple hand-coded constraint propagation
to limit the space for exhaustive search - some puzzles are solved by
constraint propagation only, and even where guesses are used, each guess
is immediately followed by propagation, to weed out useless branches
early, and to deduce consequences of each guess before asking for the
next one. the good old game, start with generatetest, then move the
tests forward, into the
generator.
I've only coded the two most useful groups of constraints (when
there's only a single number left for a position, or when there is
only a single position left for a number). there are other deductions
one does in by-hand solving, and I'm not an experienced sudoku solver
myself, so I don't even know more than a few such rules yet, but these
particular two seem sufficient to get acceptable performance even under
ghci/hugs, so why do more?-) (*)
I have two versions of a solver. The first is a re-write of GDANCE bu
Knuth to solve Sudoku efficiently as a binary cover problem. (see
http://www-cs-faculty.stanford.edu/~knuth/programs.html ) This uses the
Dancing Links algorithm implemented with STRef's and is very fast.
The second uses a different encoding to look for clever deductions. This
alone solves some easy problems and comes very close before getting stuck
on most. There are few though that start with 17 hints and only discover
one or two more by logic before getting stuck. These are the most evil of
all.
You might be interested in the deductions described at
http://www.sudokusolver.co.uk/
[by acceptable, I mean that my sequence of 5 test puzzles is solved in
less than 20 seconds on a 2GHz Pentium M; no idea how that compares to
the most efficient solvers]
I could run ~20,000 puzzles in a couple of hours. (The collection was
smaller then).
As stated above, I ran the 36,628 in 76 minutes on a 1200MHz Duron.
But I must confess that my solver takes about 25 secs for the empty puzzle,
guessing is
Re: [Haskell-cafe] Strafunski
Joost, Thanks very much - this solved my problem! Cheers Chris. On 3 Apr 2006, at 17:03, Joost Visser wrote: Hi Chris, Changes in the libraries of GHC have broken Strafunski compatibility in the past. I have not upgraded to GHC 6.5 myself so I'm not sure if this is the case again. Which versions of DrIFT and Strafunski are you using? Based on what you write, it seems new instances for Typeable have been added to the libs (possibly using deriving), which means some of your own instances are now redundant. You'll have to remove them (which will then break compatibility of your code with 6.4.1, sigh). Alternatively, you may consider to switch from the drift-default mode of Strafunski to the deriving mode. This means that you will be relying on the Typeable+Data classes rather than on the Typeable +Term classes. You make the switch simply by changing the search path, all your strategic functions should work like before. I guess GHC 6.5 supports deriving both for Typeable and Data (personally, I prefer to use DriFT rather than the deriving clause, because it gives me a bit more control over visibility of instances). For details, see the section Supported models of functional strategies in the README file of StrategyLib. Regards, Joost -- Dr. ir. Joost Visser | Departamento de Informática phone +351-253-604461 | Universidade do Minho fax+351-253-604471 | mailto:[EMAIL PROTECTED] mobile +351-91-6253618 | http://www.di.uminho.pt/~joost.visser On Apr 3, 2006, at 3:41 PM, Christopher Brown wrote: Hi, I am trying to use Strafunski with GHC 6.5 and was wondering if someone could help me. I have all the instances for Term and Typeable defined for my data types, but when I try to compile with GHC 6.5 I get lots of overlapping instance errors. In particular, it seems the instances I am using (generated by DrIFT) are clashing with the ones in Data.Typeable. Is there a way I can fix this? Also I have heard that it is possible to add deriving Typeable to each data type and I don't need to use the instances I have created. However, now it complains that it can't find instances for Term - but I can't derive from Term. Does anyone have any ideas how I can get Strafunski working with GHC 6.5? Thanks. Chris. Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Christopher Brown PhD Student, University of Kent. http://www.cs.kent.ac.uk/people/rpg/cmb21/ [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RE: generics question 2
Hi Ralf, I'm looking for a function like extT but with more general type: (t a - s a) - (t b - s b) - (t a - s a) Is there such a thing in the generics library? Hi Frederik, Not sure how you are exactly going to use such an operation ... But here is its implementation anyhow. Thanks for the riddle. Ralf import Data.Generics -- Frederik's weird ext operation :-) ext' :: (Data (t a), Data (s a), Data (t b), Data (s b)) = (t a - s a) - (t b - s b) - (t a - s a) ext' f g ta = case cast g of Just g' - g' ta Nothing - f ta -- A generic default f (Just x) = [x] f Nothing = [] -- A type-specific case g (Just True) = [True] g (Just False) = [] g Nothing = [] -- A composition using our new type-extension operator test :: Data a = Maybe a - [a] test = ext' f g -- Let's see whether it works ... main = do print $ test (Just (1::Int)) print $ test (Just False) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
