Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). -Alex- Donald Bruce Stewart wrote: alex: This implementation of calculating 1 primes (compiled with GHC -O2) is 25% slower than the naive python implementation. Shouldn't it be faster? Am I doing something obviously stupid? Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) That's super naive, and seems to be around 5x faster than the code you were trying. (So make sure you're doing the same thing as the python version) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Thought perhaps the problem is that modcount is just a slower algorithm. ... nevermind. Thanks. -Alex- Alex Jacobson wrote: The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). -Alex- Donald Bruce Stewart wrote: alex: This implementation of calculating 1 primes (compiled with GHC -O2) is 25% slower than the naive python implementation. Shouldn't it be faster? Am I doing something obviously stupid? Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) That's super naive, and seems to be around 5x faster than the code you were trying. (So make sure you're doing the same thing as the python version) -- Don ___ 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] how to make haskell faster than python at finding primes?
Alex: The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). Can you show us the Python code? Paulo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: creating graphics the functional way
Frank Buss wrote: I've created a small program to compose images with combinators: http://www.frank-buss.de/haskell/OlympicRings.hs.txt Finally, what do you think about using this concept for generating images? It has some advantages, e.g. it is possible to scale the image without quality loss. But it needs some improvement, e.g. the anti-aliasing doesn't look very smooth. And it is very slow, it needs about 40 seconds on my computer to calculate the image. The idea of representing images simply by a function Int - Int - RGB is great :) You may want to look at Pan and its various offsprings, in particular Pancito http://www.haskell.org/haskellwiki/Applications_and_libraries/Graphics#Pan Unfortunately, there's not much you can do about the speed. Pan is faster, but it creates the illusion that you're programming in Haskell while internally, it compiles the image generation code to C++. Very clever, but hard to maintain and one of the reasons why it only works on Windows. There are many functions like circle1Center, circle2Center, ... Is it possible to rewrite the program that it will be shorter, maybe using lists or an interpreter for a language for this kind of combinator programming style? Well, you have lists for that type Point = (Int,Int) positions :: [Point] positions = zip [0.5 + fromIntegral n * dx | n - [-2..2]] (cycle [y1,y2]) where dx = 0.125 y1 = 0.15 y2 = 0.25 colors :: [RGB] colors = [blue, yellow, black, green, red] type Image = Point - RGB circles :: RGB - [Image] circles background = map circle (zip positions colors) where circle (p,c) = fillMask (translate p ringCenter) c $ fillMask (translate p ringOutline) white background Is it possible to write functions with an arbitrary number of arguments? Would be nice if the average function would accept any number of pixel values. Lists are the natural choice here. Is there a PNG writer library for Haskell? I've seen a zlib interface, should be not too difficult to implement it in Haskell itself. Not that I know of. But gtk2hs has a Cairo-binding and I guess this one supports PNG. Note that this is vector graphics though, your approach is more general. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Navigating Haddock
Marc Weber wrote: On Sun, Aug 05, 2007 at 03:19:25PM -0700, David Pollak wrote: Howdy, As I'm starting to learn the Haskell libraries, I'm having a less than fun time trying to figure out what functions operate on what types. For example, in the documentation for HaXml, there's a description of Document: [1]http://www.cs.york.ac.uk/fp/HaXml/HaXml/Text-XML-HaXml-Types.html#4 However, I can't find any links to what functions accept document as a parameter. Am I missing some magic? There might be better answers. Some ways to achieve what you want: a) use hoogle (haskell.org/hoogle). You can use hoogle to find functions by types. But I don't know haw to create a query such as ... - Document - ... Hoogle unfortunately doesn't do that very well, although that would be a great feature. But I think that Text.XML.HaXml isn't indexed by Hoogle anyway? A couple of other questions... Can ByteStrings be substituted anywhere that takes a String (e.g., HaXml xmlParse)? In general yes, you should be able to use ByteStrings wherever a String is used.. But remember that a String has some syntactic suggar becuase it's treated as list. Thus the : operator won't work with ByteStrings (I'm sure the module does define functions providing the same functionality) Eh? These two are different types, you have to pack and unpack to convert between. But note that this most likely voids the performance gains from ByteString . In other words, if a library function needs a String , there's not much you can do. However, Henning Thielemann reported that his use of HaXml (I think) for the parallel web (see http://haskell.org/haskellwiki/Monad#Fun) works well with Strings. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: creating graphics the functional way
On 05/08/07, Frank Buss [EMAIL PROTECTED] wrote: Is it possible to write functions with an arbitrary number of arguments? Would be nice if the average function would accept any number of pixel values. You may be interested to see Oleg Kiselyov's discussion on polyvariadic functions in Haskell: http://okmij.org/ftp/Haskell/types.html#polyvar-fn sincerely, Shin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Now. It has to remove 6, based on the fact that it was a multiple of 2 ... (or 3? Which one comes first?) This happens in a different order than what would be expected generally in a sieve :-) So, the question is, does this improve efficiency? -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Perfect example
There's a neat Haskell solution to the knapsack problem which runs very fast. I'm not 100% sure that it runs faster than an optimal solution in other GC'd imperative languages, but it's very concise and not (too) convoluted. Have a search for the thread with xkcd in the title. Chung-chieh Shan wrote: Here's my solution to the xkcd problem (yay infinite lists): xkcd_c287' = foldr (\cost without - let (poor, rich) = splitAt cost without with = poor ++ zipWith (++) rich (map (map (cost:)) with) in with) ([[]] : repeat []) [215, 275, 335, 355, 420, 580] -- [2, 4, 150001] !! 1505 -- 150005 Replacing the two lines with comments by the comments solves your case quickly. Explication of how it works from [EMAIL PROTECTED]: I will jump in and explain, using a more finely named version: xkcd_c287' = foldr (\cost without - let (poor, rich) = splitAt cost without with = poor ++ zipWith (++) rich using_cost using cost = (map (add_cost) with) where add_cost xs = cost:xs in with) ([[]] : repeat []) [215, 275, 335, 355, 420, 580] -- [2, 4, 150001] !! 1505 -- 150005 At the top level it uses (!!) to pick the 1505th element of the list produced by the use of foldr. foldr function to combine new value with previous result seed result list of new values Here the list of new values is the list of item prices (in pennies) from the menu. The seed result is the answer in the absence of anything on the menu. The seed is ([[]] : repeat []) which is a list of (list of prices). The n th member of the outer list holds the solution for a price of n pennies. Thus the (!! 1505) selects the answer for a target price of $15.05. The seed result has an empty list in the 0th position since ordering nothing is a solution to a target price of $0.00. The function works as follows: (\cost without - The 'cost' is the price of the new item on the menu. The 'without' is the answer taking into account all previously processed items on the menu (before the 'cost' item). The result will be a new answer taking into account 'cost' as well. let (poor, rich) = splitAt cost without The items in the old answer 'without' before the index 'cost' are solutions for a target price cheaper than 'cost' and these are in the 'poor' list. These answers are unchanged by the addition of the 'cost' item. The items in the 'rich' part of the answer may get new solutions that include ordering the new 'cost' item. with = poor ++ zipWith (++) rich using_cost using cost = (map add_cost with) where add_cost xs = cost:xs in with) The new answer will be 'with' which is defined recursively. The first elements of 'with' are the 'poor' parts of the old answer 'without' that are obviously unchanged. The 'zipWith (++) rich using_cost' combines the previous 'rich' answers without 'cost' with a new list that uses the 'cost' item. This is: using cost = (map add_cost with) where add_cost xs = cost:xs The using_cost list is made from taking the list of answers and prepending the 'cost' item to all the solutions. If this were applied to 'without' instead of 'with'... using cost = (map add_cost without) where add_cost xs = cost:xs ...then the definition of 'with' would not be recursive and would allow for solutions that only order each menu item 0 or 1 times. Since the definition of using_cost does apply the map to 'with' it can add_cost to answers that already have has add_cost applied to them. Thus it finds all answers that order the menu items 0,1,2,3.. arbitrarily many times. The n th item in 'with' or 'without' has total price of n, and after add_cost it has a total price of cost+n, and must be in the (cost+n)th position in the answer 'with'. This is achieve by the using_cost items being after the (poor ++) which means they have been shifted by (length poor) positions which, by the definition of (splitN cost), is equal to 'cost'. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
On 8/6/07, Vimal [EMAIL PROTECTED] wrote: I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Isn't it how it runs ? : 2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45, 47,49,... ] then 2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ] then 2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ] then 2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ] then 2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ] etc... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Isn't it how it runs ? : 2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45, 47,49,... ] then 2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ] then 2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ] then 2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ] then 2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ] etc... Well well, see how the values are requested for: print (take 1000 primes) So, after sieve completes its action, the first 1000 elements are taken. Since Haskell is lazy, it doesnt do beyond 1000. I would expect your argument to hold good for something like this: primes n = sieve (take n [2..]) sieve (p:xs) = p : sieve [x | x - xs, x `mod` p 0] print (primes 1000) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
primes n = sieve (take n [2..]) sieve (p:xs) = p : sieve [x | x - xs, x `mod` p 0] print (primes 1000) -- Vimal But as we can see, this obviously doesn't *take* 1000 primes, :-) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] c2hs and structs?
On Sat, 2007-08-04 at 23:59 +0100, Magnus Therning wrote: I can't seem to find any information on how to deal with C functions that return a (pointer to a) struct. C2hs tells me there's no automatic support for marshalling structs (I'm using version 0.14.5). If I'm to do it by hand, is there a preferred way? (E.g. make the type adhere to the type Storable.) Yes, you want to make it an instance of Storable. You can use c2hs's get and set hooks to help with this. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Navigating Haddock
Hi a) use hoogle (haskell.org/hoogle). You can use hoogle to find functions by types. But I don't know haw to create a query such as ... - Document - ... Hoogle unfortunately doesn't do that very well, although that would be a great feature. Wait for version 4 :-) - I've added _ 's for wildcard types, _ - Document - _ would give you what you want. I've also made it so a search for Document can give you all the types which involve document in any way. But I think that Text.XML.HaXml isn't indexed by Hoogle anyway? Version 4 will be capable of indexing all of hackage, so hopefully that can be done. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Vimal wrote: Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Now. It has to remove 6, based on the fact that it was a multiple of 2 ... (or 3? Which one comes first?) This happens in a different order than what would be expected generally in a sieve :-) To get a grip on the order in which things are sieved, try the following little experiment (should also work for other sieves): The original sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] is equivalent (by desugaring the list comprehension) to sieve (p : xs) = p : sieve (filter (\x - x `mod` p 0) xs) To see the non-primes as well, replace the filter with a map, where the result type is an Either, with Left for primes and Right for non-primes. To keep track of which modules have been tested for each given number, let the element type of the Either-alternatives be a pair consisting of the number and the list of checked modules. This gives: sieve (Left l@(p,_) : xs) = Left l : sieve (map (either (\(x,e) - (if x `mod` p 0 then Left else Right) (x,p:e)) Right) xs) sieve (r : xs) = r : sieve xs Now try: sieve [Left (i,[]) | i -[2..]] [Left (2,[]),Left (3,[2]),Right (4,[2]),Left (5,[3,2]),Right (6,[2]),Left (7,[5,3,2]),Right (8,[2]),Right (9,[3,2]),Right (10,[2]),Left (11,[7,5,3,2]),... The Left-entries are primes, the Right-entries are non-primes, and the second element of each pair shows against which modules the first pair element has been checked (in reverse order). Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Paulo Tanimoto wrote:
The challenge was the implement the modcount algorithm not to calculate
primes per se.
(see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html).
Can you show us the Python code?
Note this is python for the naive, accumulate and do modulus version.
Not for modcount. See below for ocaml version of modcount.
Having slept a few hours, I still think the modcount version should be
faster than the naive version because you don't have to recalculate a
full modulues operator for each new value. You just increment and check
equality. So would love to get short fast haskell modcount.
-Alex-
---
#!/usr/bin/env python -OO
Find prime numbers. See usage() for more information.
Author: JJ Behrens
Date: Sun Dec 30 03:36:58 PST 2001
Copyright: (c) JJ Behrens
Description:
Find prime numbers. See usage() for more information. The algorithm used
to determine if a given number, n, is prime is to keep a list of prime
numbers, p's, less than n and check if any p is a factor of n.
import sys
Output usage information to the user.
mesg -- If this is not NULL, it will be output first as an error message.
def usage(mesg):
if mesg: sys.stderr.write(Error: %s\n % mesg)
sys.stderr.write(Usage: %s NUMBER_OF_PRIMES\n % sys.argv[0])
sys.stderr.write(Print out the first NUMBER_OF_PRIMES primes.\n)
if mesg: sys.exit(1)
else: sys.exit(0)
Output a prime number in a nice manner.
def printPrime(p): print p
Is numCurr prime?
primeRecList -- This is the list of primes less than num_curr.
def isPrime(numCurr, primeRecList):
for p in primeRecList:
if not numCurr % p: return 0
else: return 1
Print out the first numPrimes primes.
numPrimes must be positive, of course.
FIRST_PRIME = 2
def findPrimes(numPrimes):
numCurr = FIRST_PRIME - 1
primeRecList = []
while numPrimes 0:
numCurr += 1
if isPrime(numCurr, primeRecList):
numPrimes -= 1
printPrime(numCurr)
primeRecList.append(numCurr)
if len(sys.argv) != 2: usage(missing NUMBER_OF_PRIMES)
try:
numPrimes = int(sys.argv[1])
if numPrimes 1: raise ValueError
except ValueError: usage(NUMBER_OF_PRIMES must be a positive integer)
findPrimes(numPrimes)
(* Author: JJ Behrens
Date: Sun Nov 4 02:42:42 PST 2001
Copyright: (c) JJ Behrens
Description:
Find prime numbers. See usage() for more information. The algorithm
used to determine if a given number, n, is prime is to keep a list of
tuples (p, mc) where each p is a prime less than n and each mc is
n % p. If n is prime, then no mc is 0. The effeciency of this
algorithm is wholly determined by how efficiently one can maintain this
list. mc does not need to be recalculated using a full % operation
when moving from n to n + 1 (increment and then reset to 0 if mc = p).
Furthermore, another performance enhancement is to use lazy evaluation
of mc (i.e. collect multiple increments into one addition and one
modulo--this avoids a traversal of the entire list for values of n that
are easy to factor). As far as I know, I'm the inventor of this
algorithm. *)
(* We'll contain a list of [prime_rec]'s that replace the simple list of
primes that are used in simple algorithms.
[prime] This is the prime, as before.
[count] Given [n], [count] = [n] % [prime].
[updated] One way to keep [count] up to date is to update it for each
new [n]. However, this would traversing the entire list of
[prime_rec]'s for each new value of [n]. Hence, we'll only update
[count] each time that [prime] is considered as a possible factor
of [n]. When we do update [count], we'll set [updated] to [n].
E.g., if [count] has not been updated since [n1] and [n] is now [n2],
then [updated] will be [n1]. If [prime] is now considered as a
factor of [n2], then we'll set [updated] to [n2] and [count] to
[count] + [n2] - [n1] % [prime]. If [count] is now 0, [prime] is
indeed a factor of [n2].
*)
type prime_rec =
{ prime : int;
mutable count: int;
mutable updated: int }
(* Output usage information to the user. If [mesg] is provided, it will
be output first as an error message. *)
let usage ?(mesg = ) () =
if not (mesg = ) then Printf.fprintf stderr Error: %s\n mesg;
Printf.fprintf stderr Usage: %s NUMBER_OF_PRIMES\n Sys.argv.(0);
prerr_string Print out the first NUMBER_OF_PRIMES primes.\n;
if mesg = then exit 0 else exit 1
(* Output a prime number in a nice manner. *)
let print_prime p =
Printf.printf %d\n p
(* Find [numerator] % [divisor] quickly by assuming that [numerator] will
usually be less than [opt_tries] * [divisor]. Just leave [opt_tries]
to its default value unless you plan on doing some tuning. *)
let rec fast_mod ?(opt_tries = 2) numerator divisor =
match opt_tries with
0 - numerator mod divisor
| _ - begin
if numerator divisor then numerator
else fast_mod ~opt_tries:(opt_tries - 1)
[Haskell-cafe] Sudoku Solver
-BEGIN PGP SIGNED MESSAGE- Hash: RIPEMD160 Hi, I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out the first solution it finds. Why is it, that [0,0,0,7,0,6,9,0,0] [9,0,0,0,0,4,7,0,0] [7,0,0,0,0,0,4,0,0] [0,2,7,0,3,5,8,0,0] [6,9,5,8,2,0,0,0,0] [0,8,0,0,0,0,5,0,0] [0,3,0,0,0,0,0,0,0] [8,7,0,9,0,0,0,0,0] [0,0,0,0,0,0,0,0,0] is solved instantly, but when I remove just one number my program takes forever? === import Array import List import System type Field = Array Int (Array Int Int) isEmpty :: Int - Bool isEmpty = (==) 0 done :: Field - Bool done a = isFull a checkField a isFull::Field - Bool isFull a = notElem (0) $ (concat.(map elems).elems) a readField :: [[Int]]-Field readField = (listArray (1,9).map (listArray (1,9))) checkField :: Field - Bool checkField a = check (rows a) check (columns a) check (squares a) where check b = and $ ((map ((==1).length)).concat.(map group).clean) b clean = map (dropWhile isEmpty.sort) columns::Field - [[Int]] columns a = [[a!i!j|i-[1..9]]|j-[1..9]] rows :: Field - [[Int]] rows a = [[a!i!j|j-[1..9]]|i-[1..9]] squares :: Field - [[Int]] squares a = [[a!(i+n)!(j+m)|i-[1..3],j-[1..3]] |n-[0,3,6],m-[0,3,6]] - -- creates a list of all allowed entries genMoves :: Field - [Field] genMoves a = concat [update a i j|i-[1..9],j-[1..9],isEmpty (a!i!j)] where update b i j= [b //[(i,b!i //[(j,x)])]|x-[1..9], checkField (b //[(i,b!i //[(j,x)])])] play :: [Field] - Maybe Field play (f:a) | done f= Just f | isFull f= play a | otherwise = play ((genMoves f)++a) play [] = Nothing main :: IO () main = do x - getArgs let field = read (x!!0) :: [[Int]] let erg=play [readField field] case erg of Just a - putStrLn $ concat $ map ((++\n).show) (rows a) Nothing - putStrLn Es gibt keine Loesung -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGtx0r11V8mqIQMRsRA7P5AJ9lG3mF3fHpUiyOqCeRVOOEGozp1wCeI80C RfD/U5y+yEgF0fe+kRwDbUI= =Ngss -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Zippers, Random Numbers Terrain
Thomas Conway wrote: On 8/2/07, apfelmus [EMAIL PROTECTED] wrote: That concludes the infinite terrain generation for one dimension. For higher dimension, one just needs to use 2D objects instead of intervals to split into two or more pieces. For instance, one can divide equilateral triangles into 4 smaller ones. In fact, it doesn't matter whether the starting triangle is equilateral or not when using the midpoints of the three sides to split it into four smaller triangles. Nice. The issue of the RNG running backwards was what made me realize that rather than using StdGen in the nodes, if you simply number them (Hmmm - the nodes are countably infinite :-)), you can then [e.g.] use a cryptographic hash or similar to turn them into random numbers. You can seed the hash to generate different terrains. Yes. The number of a node in the tree should be (related to) the path from the top to the tree in binary representation. I.e. if node = zoomInLeft . zoomInLeft . zoomInRight $ top then, number node = 112 in binary with digits 1 and 2 In contrast, breadth first numbering is a bad idea, since that would mean numbering lots of nodes that aren't required when zooming in. It's probably easiest to first create an infinite tree filled with random numbers type Tree a = Branch (Tree a) a (Tree a) type Random = Double mkRandom :: Seed - Tree Random and then convert that to a landscape afterwards terrain :: Tree Random - Tree (Height, Height) Yet another option is available if you only use the zipper-operations to navigate in the tree, i.e. data TreeRandom -- abstract and a zipper zoomInLeft, zoomInRight, zoomOut :: TreeRandom - TreeRandom top :: TreeRandom - Random In that case, you can represent it by type TreeRandom = (StdGen, Zipper (Maybe Random)) Everytime you visit a node that has not been visited yet (= Nothing), it gets a new random number from the generator. When it's already been visited (= Just r), well then the random number associated to it won't change. The resulting zipper may only be used in a single-threaded fashion, however. You may be interested that in some of the code I wrote for the right angle isosceles triangle case, I got into precision problems. It turns out that all the vertices lie on positions with coordinates that are precisely sums of 2^-k (e.g. 0.5, 0.125, 0.625), yet each time you subdivide, the scaling factor on the side length is sqrt 2/2. The resultant rounding meant that instead of getting 0.5, I got 0.53, or some such. After pondering on this for a while, I realized instead of representing the scale of the triangle as a Double, I could use (Either Double Double), with Left x representing the scale x, and Right x representing the scale x * sqrt 2 / 2. That way, all the rounding problems can be made to go away. Cool :) Of course, the representation with Either requires the knowledge that a scale factor cannot contain both Double-multiples of 1 and Double-multiples of sqrt 2 at the same time. While this is clearly the case, you can avoid thinking about it by operating in the field Q[sqrt 2]: data QSqrt2 = !Double :+ !Double deriving (Eq,Read,Show) instance Nume QSqrt2 where (a :+ b) + (c :+ d) = (a+c) :+ (b+d) (a :+ b) * (c :+ d) = (a*c + 2*b*d) :+ (a*d + b*c) negate (a :+ b) = negate a :+ negate b abs (a :+ b)= (a + sqrt 2 * b) :+ 0 fromInteger n = fromInteger n :+ 0 sqrt2 = 0 :+ 1 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ICFP07 Call for Participation
= Call for Participation The 12th ACM SIGPLAN International Conference on Functional Programming (ICFP 2007) http://www.informatik.uni-bonn.de/~ralf/icfp07.html Freiburg, Germany, 1-3 October 2007 = ICFP 2007 provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. The conference covers the entire spectrum of work, from practice to theory, including its peripheries. Preliminary program: * http://www.informatik.uni-bonn.de/~ralf/schedule.html * Invited speakers: + John Hughes (Chalmers University of Technology) + Frank Pfenning (Carnegie Mellon University) + John Lloyd (Australian National University) * The Program committee has *deliberately* created extra breaks so as to give participants more time to talk with colleagues. Schedule including related workshops: * 30 Sep: ACM SIGPLAN Haskell Workshop * 30 Sep: ACM SIGPLAN Workshop on Scheme and Functional Programming * 1-3 Oct: ICFP07 * 4 Oct: ACM SIGPLAN Commercial Users of Functional Programming * 4 Oct: ACM SIGPLAN Workshop on Mechanizing Metatheory * 5 Oct: ACM SIGPLAN Erlang Workshop * 5 Oct: ACM SIGPLAN Workshop on ML * 5 Oct: ACM SIGPLAN Programming Languages meets Program Verification Registration information: * http://proglang.informatik.uni-freiburg.de/ICFP2007/registration.shtml * Early registration deadline: September 7, 2007 Accommodations information: * http://proglang.informatik.uni-freiburg.de/ICFP2007/accommodation.shtml * Conference reservation/rate deadline: September 1, 2007 * September/October is Freiburg's main tourist season; participants are advised to book rooms as early as possible. Conference organizers: * General Chair: Ralf Hinze (Universität Bonn) * Program Chair: Norman Ramsey (Harvard University) * Local Arrangements Chair: Peter Thiemann (Universität Freiburg) * Workshop Co-Chairs: Graham Hutton (University of Nottingham) and Matthias Blume (Toyota Technological Institute at Chicago) * Programming Contest Chair: Johan Jeuring (Universiteit Utrecht) * Publicity Chair: Matthew Fluet (Toyota Technological Institute at Chicago) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie question: multi-methods in Haskell
In de book Modern C++ design, Andrei Alexandrescu writes that Haskell supports “multi-methods” http://books.google.com/books?id=aJ1av7UFBPwCpg=PA3ots=YPiJ_nWi6Ydq=moder n+C%2B%2Bsig=FWO6SVfIrgtCWifj9yYHj3bnplQ#PPA263,M1 How is this actually done in Haskell? Maybe this is just a basic feature of Haskell which I don't grasp yet because of my object-oriented background? A good example is collision between pairs of objects of type (a,b). In object oriented languages this cannot be handled in a nice way, because neither a.Collide(b) or b.Collide(a) is the correct approach; one would like to write (a,b).Collide() A specific example might be better here. Assume the following class hierarchy: Solid | +-- Asteroid | +-- Planet | + -- Earth | + -- Jupiter Using multi-methods, I could write (in pseudo code) collide (Asteroid, Planet) = an asteroid hit a planet collide (Asteroid, Earth) = the end of the dinos collide (Solid,Solid) = solids collided collide (Planet, Asteroid) = collide (Asteroid, Planet) collide (Earth, Asteroid) = collide (Earth, Asteroid) So basically, the best collide function is picked, depending on the type of the arguments. How should I write Haskell code for something like this in general, in the sense that this hierarchy is typically huge and the matrix (of collide functions for each pair of types) is very sparse. Thanks, Peter No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.11.6/938 - Release Date: 05/08/2007 16:16 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [Fwd: PADL 2008: Call for Papers]
Original Message Subject:PADL 2008: Call for Papers Date: Sat, 4 Aug 2007 19:25:58 -0500 (CDT) From: Gopal Gupta [EMAIL PROTECTED] [ Colleagues, note that this will be the 10th PADL; We strongly urge you to submit papers, the deadline is only 3 weeks way] CALL FOR PAPERS!!! Tenth International Symposium on Practical Aspects of Declarative Languages 2008 (PADL '08) http://www.ist.unomaha.edu/padl2008/ San Francisco, USA January 7-8, 2008 Co-located with ACM POPL'08 Declarative languages build on sound theoretical bases to provide attractive frameworks for application development. These languages have been successfully applied to vastly different real-world situations, ranging from data base management to active networks to software engineering to decision support systems. New developments in theory and implementation have opened up new application areas. At the same time, applications of declarative languages to novel problems raises numerous interesting research issues. Well-known questions include designing for scalability, language extensions for application deployment, and programming environments. Thus, applications drive the progress in the theory and implementation of declarative systems, and benefit from this progress as well. PADL is a forum for researchers and practitioners to present original work emphasizing novel applications and implementation techniques for all forms of declarative concepts, including, functional, logic, constraints, etc. Topics of interest include: * innovative applications of declarative languages; * declarative domain-specific languages and applications; * practical applications of theoretical results; * new language developments their impact on applications; * evaluation of implementation techniques on practical applications; * novel uses of declarative languages in the classroom; and * practical experiences PADL 08 welcomes new ideas and approaches pertaining to applications and implementation of declarative languages. PADL 08 will be co-located with the ACM POPL. IMPORTANT DATES AND SUBMISSION GUIDELINES Paper Submission: August 24, 2007 Notification: September 27, 2007 Camera-ready: October 23, 2007 Symposium: January 7-8, 2008 Authors should submit an electronic copy of the full paper (written in English) in Postscript (Level 2) or PDF. Papers must be no longer than 15 pages, written in 11-point font and with single spacing. Since the final proceedings will be published as Lecture Notes in Computer Science by Springer Verlag, authors are strongly encouraged to use the LNCS paper formatting guidelines for their submission. Each submission must include on its first page the paper title; authors and their affiliations; contact author's email and postal addresses, telephone and fax numbers, abstract, and three to four keywords. The keywords will be used to assist us in selecting appropriate reviewers for the paper. If electronic submission is impossible, please contact the program chair for information on how to submit hard copies. MOST PRACTICAL PAPER AWARD The Most Practical Paper award will be given to the submission that is judged by the program committee to be the best in terms of practicality, originality, and clarity of presentation. The program committee may choose not to make an award, or to make multiple awards. Contacts: For information about papers and submissions, please contact the Program Chair: Paul Hudak PC co-Chair - PADL 2008 Department of Computer Science Yale University P.O. Box 208285 New Haven, CT 06520 - 8285 Email: [EMAIL PROTECTED] David S. Warren PC co-Chair - PADL 2008 Department of Computer Science Stony Brook University Stony Brook, NY Email: [EMAIL PROTECTED] For other information about the conference, please contact: Hai-Feng Guo General Chair - PADL 2008 Department of Computer Science College of Information Science Technology University of Nebraska at Omaha Omaha, NE, U.S.A. Email: [EMAIL PROTECTED] Sponsored by: COMPULOG Americas (http://www.cs.nmsu.edu/~complog) and University of Nebraska at Omaha ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: multi-methods in Haskell
peterv wrote:
In de book Modern C++ design, Andrei Alexandrescu writes that Haskell
supports “multi-methods”
Using multi-methods, I could write (in pseudo code)
collide (Asteroid, Planet) = an asteroid hit a planet
collide (Asteroid, Earth) = the end of the dinos
...
collide (Planet, Asteroid) = collide (Asteroid, Planet)
collide (Earth, Asteroid) = collide (Earth, Asteroid)
Hi, In Haskell you can use multi parameter type classes to solve this
problem:
{-# OPTIONS_GHC -fglasgow-exts
-fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
class Collide a b where
collide :: (a,b) - String
data Solid = Solid
data Asteroid = Asteroid
data Planet = Planet
data Jupiter = Jupiter
data Earth = Earth
instance Collide Asteroid Planet where
collide (Asteroid, Planet) = an asteroid hit a planet
instance Collide Asteroid Earth where
collide (Asteroid, Earth) = the end of the dinos
-- Needs overlapping and undecidable instances
instance Collide a b = Collide b a where
collide (a,b) = collide (b, a)
-- ghci output
*Collide collide (Asteroid, Earth)
the end of the dinos
*Collide collide (Earth, Asteroid)
the end of the dinos
Best regards, Brian.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: multi-methods in Haskell
Remember that type classes do not provide object-oriented functionality.
The dispatch is static, not dynamic. Although OOP can be simulated in
Haskell, it is not a natural idiom. If you need dynamic dispatch
(including multiple dispatch), you may want to reconsider your solution.
Dan Weston
Brian Hulley wrote:
peterv wrote:
In de book Modern C++ design, Andrei Alexandrescu writes that Haskell
supports “multi-methods”
Using multi-methods, I could write (in pseudo code)
collide (Asteroid, Planet) = an asteroid hit a planet
collide (Asteroid, Earth) = the end of the dinos
...
collide (Planet, Asteroid) = collide (Asteroid, Planet)
collide (Earth, Asteroid) = collide (Earth, Asteroid)
Hi, In Haskell you can use multi parameter type classes to solve this
problem:
{-# OPTIONS_GHC -fglasgow-exts
-fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
class Collide a b where
collide :: (a,b) - String
data Solid = Solid
data Asteroid = Asteroid
data Planet = Planet
data Jupiter = Jupiter
data Earth = Earth
instance Collide Asteroid Planet where
collide (Asteroid, Planet) = an asteroid hit a planet
instance Collide Asteroid Earth where
collide (Asteroid, Earth) = the end of the dinos
-- Needs overlapping and undecidable instances
instance Collide a b = Collide b a where
collide (a,b) = collide (b, a)
-- ghci output
*Collide collide (Asteroid, Earth)
the end of the dinos
*Collide collide (Earth, Asteroid)
the end of the dinos
Best regards, Brian.
___
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] Newbie question: multi-methods in Haskell
peterv schrieb: In de book Modern C++ design, Andrei Alexandrescu writes that Haskell supports “multi-methods” http://books.google.com/books?id=aJ1av7UFBPwCpg=PA3ots=YPiJ_nWi6Ydq=moder n+C%2B%2Bsig=FWO6SVfIrgtCWifj9yYHj3bnplQ#PPA263,M1 Chapter 11, Page 263 of this books: The C++ virtual function mechanism allows dispatching of a call depending on the dynamic type of one object. The multimethods feature allows dispatching of a function call depending on the types of multiple objects. A universally good implementation requires language support, wich is the route that languages such as CLOS, ML, Haskell, and Dylan have taken. C++ lacks such support, so it's emulation is left to library writers. I do not see why the author of this book included Haskell in this list. (But from what I know, CLOS is more like a combinator library then like a language, so I don't understand the point of this list at all). Since Haskell has no language support for subtype polymorphism or dynamic dispatch of method calls, there are no dynamic multimethods either. But with multi-parameter typeclasses, we have statically dispatched multimethods, of course. (See Brian's answer). But the author speaks specifically about dynamic dispatch. Sometimes, class hierarchies from an OO design are naturally represented by algebraic data types. Then OO methods become ordinary haskell function, and dynamic dispatch becomes pattern matching, wich is of course possible on all argument positions: data Solid = Asteroid | Planet Planet data Planet = Earth | Jupiter collide :: Solid - Solid - String collide Asteroid (Planet Earth) = the end of the dinos collide Asteroid (Planet _) = an asteroid hit a planet collide p@(Planet _) Asteroid = collide Asteroid p collide _ _ = solids collided But you have to sort the definitons for collide yourself, because there is no selection of the most specific automatically. While this is a sometimes sensible translation of an OO design into an FP design, it is not the same thing as having objects and subtypes and dynamic dispatch. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: multi-methods in Haskell
Dan Weston wrote:
Remember that type classes do not provide object-oriented
functionality. The dispatch is static, not dynamic. Although OOP can
be simulated in Haskell, it is not a natural idiom. If you need
dynamic dispatch (including multiple dispatch), you may want to
reconsider your solution.
Dynamic dispatch is easily added to Haskell code by using an existential
to represent any collision:
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
-- Changed to a single param to make life easier...
class Collide a where
collide :: a - String
data Solid = Solid
data Asteroid = Asteroid
data Planet = Planet
data Jupiter = Jupiter
data Earth = Earth
instance Collide (Asteroid, Planet) where
collide (Asteroid, Planet) = an asteroid hit a planet
instance Collide (Asteroid, Earth) where
collide (Asteroid, Earth) = the end of the dinos
-- Needs overlapping and undecidable instances
instance Collide (a, b) = Collide (b, a) where
collide (a,b) = collide (b, a)
-- This is how you get dynamic dispatch in Haskell
data Collision = forall a. Collide a = Collision a
instance Collide Collision where
collide (Collision a) = collide a
-- ghci output
*Collide let ae = Collision (Asteroid, Earth)
*Collide let pa = Collision (Planet, Asteroid)
*Collide collide ae
the end of the dinos
*Collide collide pa
an asteroid hit a planet
*Collide map collide [ae, pa]
[the end of the dinos,an asteroid hit a planet]
Best regards, Brian.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Newbie question: multi-methods in Haskell
Remember that type classes do not provide object-oriented functionality. The dispatch is static, not dynamic. I beg to disagree. map (\n. n + n) calls different (+) operations depending on the (type of the) argument list. That's why dictionaries are passed around (they are called vtables in many OO languages) by several Haskell implementations. Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] creating graphics the functional way
Am Montag, 6. August 2007 00:48 schrieb Frank Buss:
I've created a small program to compose images with combinators:
http://www.frank-buss.de/haskell/OlympicRings.hs.txt
...
look very smooth. And it is very slow, it needs about 40 seconds on my
computer to calculate the image. Using parametrized combinators sounds like
...
in that source file, you define Size and Pixel as structs of Integers. that
are neither unsigned chars (8_bit) nor ints (32-64_bit) nor floats (32_bit) but
an artificial oo_bit int (1 int + list of bytes).
i'm sure you will gain a speedup by redefining these structs. i.e. use Float or
Int instead of Integer; see Data.Int and Data.Word for more alternatives.
- marc
[code snippet from source file]
-- image size
data Size = Size { width :: Integer, height :: Integer }
deriving (Eq, Ord, Show, Read)
-- RGB components for an image pixel
data Pixel = Pixel { r :: Integer, g :: Integer, b :: Integer }
deriving (Eq, Ord, Show, Read)
-- helper functions for saving bytes
writeByte byte = putWord8 (fromIntegral byte)
writeBytes bytes = mapM_ putWord8 bytes
-- binary instance for saving Pixels
instance Binary Pixel where
put (Pixel r g b) = do
writeByte b
writeByte g
writeByte r
get = error Pixel get not supported
[/code]
pgpFEOkZiYO8o.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Using haskell with emacs
Hi all, I'm starting to learn haskell by my own, being currently mostly a Common Lisp, Scheme, C++ programmer... I've got the haskell emacs mode but can't find a manual. Moreover, I've found some keybindings on the net but nothing that allows me to start an interpreter in emacs and send definitions, one by one to the interpreter. Is this possible? Is there any good reference of the emacs keybindings for haskell mode? Cheers, -- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Using haskell with emacs
On 6 aug 2007, at 22.11, Paulo J. Matos wrote: Hi all, I'm starting to learn haskell by my own, being currently mostly a Common Lisp, Scheme, C++ programmer... I've got the haskell emacs mode but can't find a manual. Moreover, I've found some keybindings on the net but nothing that allows me to start an interpreter in emacs and send definitions, one by one to the interpreter. Is this possible? Is there any good reference of the emacs keybindings for haskell mode? If you're used to Slime+Paredit, then there isn't something really comparable, but you get some basic interactive programming with the standard key-bindings: C-c C-b ... when pressed for the first time this will start an interpreter (ghci or hugs most of the time), when pressed with a running interpreter it'll switch to that buffer. C-c C-l ... Load the current file into the editor. There is no function-wise compilation. With the latest Haskell mode, you get clickable error messages, too. Then there is shim[1], which is a start of a Slime-like emacs mode, it can: - compile and show compile errors directly in the source (C-c C-k) - insert the type of a function (C-c C-t) The big problem with shim is, that it is only really useful as long as your code compiles. To have anything more useful you need to have good (incremental) parsing facilities, which Emacs isn't particularly good at. Every once in a while I do some hacking towards this goal, but it's rather low-priority (and I'm no particular Emacs guru either, though with (require 'cl) it get's somewhat more fun.) Many Haskell hackers also prefer Vim, so that doesn't help, either ;) Oh, and there's hoogle.el, which is pretty similar to Hyperspec lookup (actually, I think it's better; more like Lisp-doc lookup). Regards, / Thomas [1] .. http://shim.haskellco.de/trac/shim ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Newbie question: multi-methods in Haskell
This is very nice, but it does not really solve the original problem.
In your code, evaluating
collide (Jupiter, Asteroid)
will result in an endless loop. This is expected in your code, because no
inheritance relation is present between e.g Jupiter and Planet. With
multi-dispatch, it should pick the best matching collide function based on
inheritance, or raise an error when ambiguous types.
I could fix that be just keeping the leafs (Earth, Jupiter, Asteroid) as
datatypes, and adding type classes for the super classes (Planet, Solid),
like the code below, but I could not check Asteroid-Asteroid collision with
that, GHCi gives an error.
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
class Collide a where
collide :: a - String
data Asteroid = Asteroid
data Jupiter = Jupiter
data Earth = Earth
class IsSolid a
class IsSolid a = IsPlanet a
instance IsSolid Asteroid
instance IsSolid Jupiter
instance IsSolid Earth
instance IsPlanet Earth
instance IsPlanet Jupiter
instance (IsSolid a, IsSolid b) = Collide (a, b) where
collide (x,y) = generic collision
instance (IsPlanet a) = Collide (Asteroid, a) where
collide (x,y) = an asteroid hit a planet
instance (IsPlanet a) = Collide (a, Asteroid) where
collide (x, y) = an asteroid hit a planet
instance Collide (Asteroid, Earth) where
collide (_,_) = the end of the dinos
instance Collide (Earth, Asteroid) where
collide (_,_) = the end of the dinos
-- This is how you get dynamic dispatch in Haskell
data Collision = forall a. Collide a = Collision a
instance Collide Collision where
collide (Collision a) = collide a
ae = collide (Asteroid, Earth)
ea = collide (Earth, Asteroid)
ja = collide (Jupiter, Asteroid)
aj = collide (Asteroid, Jupiter)
-- However, this one gives an error?
--aa = collide (Asteroid, Asteroid)
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Brian Hulley
Sent: Monday, August 06, 2007 9:15 PM
To: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Newbie question: multi-methods in Haskell
Dan Weston wrote:
Remember that type classes do not provide object-oriented
functionality. The dispatch is static, not dynamic. Although OOP can
be simulated in Haskell, it is not a natural idiom. If you need
dynamic dispatch (including multiple dispatch), you may want to
reconsider your solution.
Dynamic dispatch is easily added to Haskell code by using an existential
to represent any collision:
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
-- Changed to a single param to make life easier...
class Collide a where
collide :: a - String
data Solid = Solid
data Asteroid = Asteroid
data Planet = Planet
data Jupiter = Jupiter
data Earth = Earth
instance Collide (Asteroid, Planet) where
collide (Asteroid, Planet) = an asteroid hit a planet
instance Collide (Asteroid, Earth) where
collide (Asteroid, Earth) = the end of the dinos
-- Needs overlapping and undecidable instances
instance Collide (a, b) = Collide (b, a) where
collide (a,b) = collide (b, a)
-- This is how you get dynamic dispatch in Haskell
data Collision = forall a. Collide a = Collision a
instance Collide Collision where
collide (Collision a) = collide a
-- ghci output
*Collide let ae = Collision (Asteroid, Earth)
*Collide let pa = Collision (Planet, Asteroid)
*Collide collide ae
the end of the dinos
*Collide collide pa
an asteroid hit a planet
*Collide map collide [ae, pa]
[the end of the dinos,an asteroid hit a planet]
Best regards, Brian.
___
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] Using haskell with emacs
C-c C-b ... when pressed for the first time this will start an interpreter (ghci or hugs most of the time), when pressed with a running interpreter it'll switch to that buffer. C-c C-l ... Load the current file into the editor. There is no function-wise compilation. Don't forget C-c C-r to reload the file in the buffer. To the OP: Here's the page I used when I set up emacs for haskell the other week: http://haskell.org/haskellwiki/Haskell_mode_for_Emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Using haskell with emacs
Thomas Schilling wrote: On 6 aug 2007, at 22.11, Paulo J. Matos wrote: If you're used to Slime+Paredit, then there isn't something really comparable, but you get some basic interactive programming with the standard key-bindings: (But paredit does work in haskell-mode, and I find it useful...) Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Java 1.5 parser in Haskell
Does anyone know of a fairly complete Java 1.5 parser and abstract syntax in Haskell? I've looked around quite a bit to no avail. Thanks, - Tim -- View this message in context: http://www.nabble.com/Java-1.5-parser-in-Haskell-tf4227017.html#a12025365 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
Note that the official way to solve sudoku is to use dancing links, but I guess you are creating a naive implementation precisely as a base-line against which to measure other implementations? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type without a data constructor?
Most examples for defining algebraic types include data constructors like so: data Tree a = Tip | Node a (Tree a) (Tree a) I by mistake defined a type which did not specify a data constructor : data SearchCondition = Term Bool | SearchCondition :||: (Term Bool) data Term a = Constant a sc :: SearchCondition sc = Term True is ok, but sc :: SearchCondition sc = Constant True is not (though this is what I intended to capture!). So the question is what are types with no constructors good for? A simple example would be appreciated. Rahul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type without a data constructor?
Hi I by mistake defined a type which did not specify a data constructor So the question is what are types with no constructors good for? A simple example would be appreciated. They are called phantom types, and can be used for ensuring properties at the type level. I wrote about them in a blog post: http://neilmitchell.blogspot.com/2007/04/phantom-types-for-real-problems.html There are probably better references, but that's the easiest for me to find ;-) Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type without a data constructor?
The answer would be phantom types, but your example doesn't use them. Each of your types has at least one constructor: Possibly you overlooked the infix constructor :||: ? Tree a has 2 constructors: Tip and Node SearchCondition has 2 constructors: Term and (:||:) Term a has 1 constructor : Constant *Prelude :t Tip Tip :: Tree a *Prelude :t Node Node :: a - Tree a - Tree a - Tree a *Prelude :t Term True Term True :: SearchCondition *Prelude :t (:||:) (:||:) :: SearchCondition - Term Bool - SearchCondition *Prelude :t Constant True Constant True :: Term Bool Dan Weston Rahul Kapoor wrote: Most examples for defining algebraic types include data constructors like so: data Tree a = Tip | Node a (Tree a) (Tree a) I by mistake defined a type which did not specify a data constructor : data SearchCondition = Term Bool | SearchCondition :||: (Term Bool) data Term a = Constant a sc :: SearchCondition sc = Term True is ok, but sc :: SearchCondition sc = Constant True is not (though this is what I intended to capture!). So the question is what are types with no constructors good for? A simple example would be appreciated. Rahul ___ 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] Type without a data constructor?
On Monday 06 August 2007 19:23, Rahul Kapoor wrote: Most examples for defining algebraic types include data constructors like so: data Tree a = Tip | Node a (Tree a) (Tree a) I by mistake defined a type which did not specify a data constructor : In this example, you have two different uses of the lexical name 'Term', and I think it is confusing you. One kind of use is as a data constructor; the other is as a type constructor. I've annotated the uses below: data SearchCondition = Term Bool-- data constructor | SearchCondition :||: (Term Bool)-- type constructor data Term a = Constant a -- defn of type constr 'Term' sc :: SearchCondition sc = Term True -- data constructor is ok, but sc :: SearchCondition sc = Constant True Now, here you have an expression of type 'Term Bool'. These can only appear on the right-hand side of :||: . This probably isn't what you want. Likely what you actually want is: data SearchCondition = SearchTerm (Term Bool) | SearchCondition :||: (Term Bool) Here, both uses of 'Term' refer to the type constructor. is not (though this is what I intended to capture!). So the question is what are types with no constructors good for? A simple example would be appreciated. There are some situations where an explicitly empty type is useful. Type-level programming voodoo is one. Other times the void type is nice because it can be used as a parameter to a type constructor. For example, if you use the nested datatype representation of de Bruijn lambda terms [1], you can use the void type to create the type of closed terms (terms with no free variables). Here's the short version: data Void data Succ a = Zero | Incr a data Term a = Var a | App (Term a) (Term a) | Lam (Term (Succ a)) type ClosedTerm = Term Void [1] Richard Bird and Ross Patterson, _de Brujin Notation as a Nested Datatype_, Journal of Functional Programming 9(1):77-91, January 1999. Rob Dockins ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type without a data constructor?
On 2007-08-06, Rahul Kapoor [EMAIL PROTECTED] wrote: I by mistake defined a type which did not specify a data constructor : No, you didn't. Both types have data constructors. data SearchCondition = Term Bool | SearchCondition :||: (Term Bool) data Term a = Constant a sc :: SearchCondition sc = Term True is ok, but sc :: SearchCondition sc = Constant True is not (though this is what I intended to capture!). The problem is that Constant True is of type Term Bool, rather than SearchCondition. Constructors and names of data types live in separate namespaces. So the question is what are types with no constructors good for? A simple example would be appreciated. See the phantom types answer that someone else gave. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type without a data constructor?
Constructors and names of data types live in separate namespaces. The above fact was the cause of all my confusion. It just slipped out of my mind. Cheers, Rahul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
Hi, Am Montag, 6. August 2007 15:07 schrieb Adrian Neumann: -BEGIN PGP SIGNED MESSAGE- Hash: RIPEMD160 Hi, I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out the first solution it finds. Why is it, that [0,0,0,7,0,6,9,0,0] [9,0,0,0,0,4,7,0,0] [7,0,0,0,0,0,4,0,0] [0,2,7,0,3,5,8,0,0] [6,9,5,8,2,0,0,0,0] [0,8,0,0,0,0,5,0,0] [0,3,0,0,0,0,0,0,0] [8,7,0,9,0,0,0,0,0] [0,0,0,0,0,0,0,0,0] is solved instantly, but when I remove just one number my program takes forever? Short answer: because of the enormous number of possibilities to check. You were just incredibly lucky: with the grid above, you needn't backtrack. The problem is genMoves, it produces too many Fields. Point 1: If for, say, the first empty cell, there are no possibilities, you still try out all possibilities for the other empty cells before you backtrack, that's bound to take very long. Point 2: Even if you take care of 1, you have to do it right. Say in one row you have three empty cells with only one or two possibilities altogether. Then it's futile and very time consuming to tinker with the later rows before backtracking. (To see what I mean, make play an IO-action and let it print out the field to be updated, like play :: [Field] - IO (Maybe Field) play (f:a) | done f = return $ Just f -- | isFull f= play a | otherwise = do printField f getLine play ((genMoves f)++a) play [] = return Nothing ) A solution is to only consider the first empty cell: genMoves a = concat $ take 1 [update a i j|i-[1..9],j-[1..9],isEmpty (a!i!j)] That'll be still slow, but should finish before the gnab gib[1]. - -- creates a list of all allowed entries genMoves :: Field - [Field] genMoves a = concat [update a i j|i-[1..9],j-[1..9],isEmpty (a!i!j)] where update b i j= [b //[(i,b!i //[(j,x)])]|x-[1..9], checkField (b //[(i,b!i //[(j,x)])])] Another thing, I think, it'd look better if You used type Field = Array (Int,Int) Int. Cheers, Daniel [1] Douglas Adams, The Restaurant at the end of the Universe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Java 1.5 parser in Haskell
I know this isn't quite what you asked, but java has a very clearly laid-out grammar in EBNF at http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html . Between that and Parsec, I would think it would be fairly simple to write a parser. Of course, adding semantics is another story. On 8/6/07, tim.b [EMAIL PROTECTED] wrote: Does anyone know of a fairly complete Java 1.5 parser and abstract syntax in Haskell? I've looked around quite a bit to no avail. Thanks, - Tim -- View this message in context: http://www.nabble.com/Java-1.5-parser-in-Haskell-tf4227017.html#a12025365 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ 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] Sudoku Solver
On 8/7/07, Hugh Perkins [EMAIL PROTECTED] wrote: Note that the official way to solve sudoku is to use dancing links, but I guess you are creating a naive implementation precisely as a base-line against which to measure other implementations? Well, Dancing Links (DLX) is just a data structure + few techniques to help with the backtrack, after modeling Sudoku as a contraint satisfaction problem. You can write a backtracking algorithm that is at least as fast as DLX :-) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
j.vimal: On 8/7/07, Hugh Perkins [EMAIL PROTECTED] wrote: Note that the official way to solve sudoku is to use dancing links, but I guess you are creating a naive implementation precisely as a base-line against which to measure other implementations? Well, Dancing Links (DLX) is just a data structure + few techniques to help with the backtrack, after modeling Sudoku as a contraint satisfaction problem. You can write a backtracking algorithm that is at least as fast as DLX :-) See also, http://haskell.org/haskellwiki/Sudoku -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Donald Bruce Stewart [EMAIL PROTECTED] wrote: See also, http://haskell.org/haskellwiki/Sudoku -- Don Just out of ... errr curiosity... which of those implementations is the fastest? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
hughperkins: On 8/7/07, Donald Bruce Stewart [EMAIL PROTECTED] wrote: See also, [2]http://haskell.org/haskellwiki/Sudoku -- Don Just out of ... errr curiosity... which of those implementations is the fastest? No idea. You could compile them all with -O2, run them on a set of puzzles, and produce a table of results :-) I'm a little surprised no one's tried a parallel solution yet, actually. We've got an SMP runtime for a reason, people! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] combinators for a simple grammar
I am having problems coming up with nice combinators for a simple DSEL. The abstract syntax is simply given by the types: data SearchCondition = SearchCondition BoolTerm | OpOr SearchCondition BoolTerm data BoolTerm = BoolTerm BoolFactor | OpAnd BoolTerm BoolFactor data BoolFactor = Constant Bool My current combinators are (.||.) :: SearchCondition - BoolTerm - SearchCondition (.||.) sc term = OpOr sc term (..) :: BoolTerm - BoolFactor - BoolTerm (..) term fact = OpAnd term fact which allow you to write expression of the form factTrue = Constant True termTrue = BoolTerm factTrue scTrue = SearchCondition termTrue sc = scTrue .||. termTrue .||. termTrue .. factTrue I am wondering it it is possible to define combinators to hide the structure of the grammar from the user to some extent, so that the user can simply write things like sc = True .||.True .||. True .. False or sc = const True .||. const True .||. const True .. const False That is the user does not have to worry about the distinction between terms and factors (which exists solely for precedence in this case). Or is it a better idea to just remove the precedence rules from the types and move it the part of the code that evaluates the expressions? Rahul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] combinators for a simple grammar
On Mon, Aug 06, 2007 at 10:33:01PM -0400, Rahul Kapoor wrote: I am having problems coming up with nice combinators for a simple DSEL. The abstract syntax is simply given by the types: data SearchCondition = SearchCondition BoolTerm | OpOr SearchCondition BoolTerm data BoolTerm = BoolTerm BoolFactor | OpAnd BoolTerm BoolFactor data BoolFactor = Constant Bool My current combinators are (.||.) :: SearchCondition - BoolTerm - SearchCondition (.||.) sc term = OpOr sc term (..) :: BoolTerm - BoolFactor - BoolTerm (..) term fact = OpAnd term fact which allow you to write expression of the form factTrue = Constant True termTrue = BoolTerm factTrue scTrue = SearchCondition termTrue sc = scTrue .||. termTrue .||. termTrue .. factTrue I am wondering it it is possible to define combinators to hide the structure of the grammar from the user to some extent, so that the user can simply write things like sc = True .||.True .||. True .. False or sc = const True .||. const True .||. const True .. const False That is the user does not have to worry about the distinction between terms and factors (which exists solely for precedence in this case). Or is it a better idea to just remove the precedence rules from the types and move it the part of the code that evaluates the expressions? I think it would be better still to remove it from both and rely on Haskell's built-in precedence parser. data SearchCondition = Constant Bool | SearchCondition :||: SearchCondition | SearchCondition :: SearchCondition infixr 3 :: infixr 2 :||: true = Constant True false = Constant False sc = true :||: true :||: true :: false eval (Constant k) = k eval (l :||: r) = eval l || eval r eval (l :: r) = eval l eval r You can still hide the constructors if you want, of course. Another idea is to directly represent search conditions as functions: type SearchCondition = Object - Bool -- could be just Bool to match your example, but I imagine you were -- simplifying, and making the leap from Bool to Object - Bool is -- not always obvious (.||.) sc1 sc2 x = sc1 x || sc2 x (..) sc1 sc2 x = sc1 x sc2 x true x = True false x = False infixr 3 .. infixl 2 .||. -- eval is not needed! You can just apply a search condition to an -- object. The downside of this is that applying is *all* you can do, -- you can't optimize or analyze like you can with the explicit -- approach. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] combinators for a simple grammar
On Monday 06 August 2007, Rahul Kapoor wrote: I am having problems coming up with nice combinators for a simple DSEL. The abstract syntax is simply given by the types: snip Or is it a better idea to just remove the precedence rules from the types and move it the part of the code that evaluates the expressions? Exactly thus. Say: data SearchCondition = Constant Bool | SearchCondition :||: SearchCondition | SearchCondition :: SearchCondition infixr 3 (::) infixr 2 (:||:) And you're set. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs pgpmmrE2Ge8iq.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: creating graphics the functional way
apfelmus wrote: The idea of representing images simply by a function Int - Int - RGB is great :) You may want to look at Pan and its various offsprings, in particular Pancito http://www.haskell.org/haskellwiki/Applications_and_libraries/ Graphics#Pan this looks interesting. The Java applets demonstrates that it is possible to implement this in realtime. I assume there are some clever optimizations implemented, which could be done with Haskell, too. positions :: [Point] positions = zip [0.5 + fromIntegral n * dx | n - [-2..2]] (cycle [y1,y2]) where dx = 0.125 y1 = 0.15 y2 = 0.25 Nice calculation for the positions, but at least for me it is more difficult to understand it than just writing the 5 points. But using lists is a good idea. I've updated the source: http://www.frank-buss.de/haskell/OlympicRings2.hs.txt http://www.frank-buss.de/haskell/OlympicRings2.png The anti-aliasing doesn't look good anyway, so I have removed it. Very cool for me was the foldr (.) id construct, which someone on #haskell suggested. Changing separate x/y coordinates to a list with 2 elements helped, too, to cleanup the source code. Maybe some more cleanups and the PNG save implementation, and then this code could be used as a small practical example for other Haskell newbies like me. BTW: Is there any coding standard for Haskell programs? I've seen different formattings, like how to indent where and the following parts of the code. Is there a common practice? -- Frank Buss, [EMAIL PROTECTED] http://www.frank-buss.de, http://www.it4-systems.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] creating graphics the functional way
Marc A. Ziegert wrote: in that source file, you define Size and Pixel as structs of Integers. that are neither unsigned chars (8_bit) nor ints (32-64_bit) nor floats (32_bit) but an artificial oo_bit int (1 int + list of bytes). i'm sure you will gain a speedup by redefining these structs. i.e. use Float or Int instead of Integer; see Data.Int and Data.Word for more alternatives. I've tried it, but it was not faster. Using Word8 for the RGB pixels even resulted in wrong colors with the anti-aliased version, maybe because of number overflows. -- Frank Buss, [EMAIL PROTECTED] http://www.frank-buss.de, http://www.it4-systems.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Monad for Set?
Hi,
I'm pondering, is it possible to define a Set monad analogous to the
List monad?
My thinking is as follows:
* fmap f x would apply f to each element in a set x
* return x would create a singleton set {x}
* join x, where x is a set of sets: x = {x1, x2, ... xn},
would form their union (x1 U x2 U ... U xn)
The advantage of Set over List is that duplicate elements would be
removed automatically.
There is just one /slight/ problem: In order to implement set
operations, I need to be able to test elements for equality; that is,
I need to impose the restriction (Eq a) = Set a. This is a problem
because return really needs to work for any type; I have no way to
guarantee (Eq a).
In my search for answers, I came across restricted monads. I don't
like the idea of restricting the types I can return, and here's why.
Suppose I had a way to impose (Eq a). Then I start to wonder:
* What happens when I use a monad transformer like StateT s Set a
or ContT r Set a, but the types s and r are not equatable?
* What happens when I want to define the monad transformer SetT
because I need to put the IO monad inside it?
In both cases, I feel I'm screwed if I really have to impose the
constraint (Eq a) = Set a.
This leads me think of a different solution: What if I could define a
Set monad that's smart enough to know, for any type a, whether or
not (Eq a) holds, and degenerate to a blind list if the elements can't
be equated. Ultimately, what I would need is a way to overload join
(or bind) with two different implementations, one for types that
satisfy (Eq a), and another implementation for all other types.
In my searching so far, I found ways to overload a function when all
overloads share a common typeclass, and I have found ways to overload
a function for disjoint types, provided that every type to be overload
is an instance of some typeclass. All of the methods I have found so
far are deficient in the sense that there is no way to provide a
default implementation for types that don't fit into any typeclass. I
have not been able to find a way to overload a function such that one
implementation works for a special class of types, and another
implementation works for *all* other types.
Question: Is it possible to define join :: [[a]] - [a], with
(1) a special implementation that requires (Eq a) and removes duplicate
elements, and
(2) a general implementation to fall back on for *any* type that fails
the constraint, and
(3) a way to make f fully generic, such that the correct
implementation is chosen automatically from the type variable a?
If I had a way to do this, then I could define a Set monad that
performs set operations when it can (i.e. when the elements are
equatable), but which automatically degenerates to a simple List when
it has to (i.e. when there's no equality test). I almost suspect that
I might need to use Haskell Templates (I currently know nothing about
Haskell Templates).
Even better, if this problem is solvable, then the next step would be to
overload again to use an efficient implementation when set elements are
comparable (Ord a).
Any ideas?
-- Ron
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Donald Bruce Stewart [EMAIL PROTECTED] wrote: No idea. You could compile them all with -O2, run them on a set of puzzles, and produce a table of results :-) Well I could, but I wont ;-) If you had to guess which one is fastest which one would you guess? I'm a little surprised no one's tried a parallel solution yet, actually. We've got an SMP runtime for a reason, people! Funny that you should mention that, this was actually one of the Topcoder marathon match contests for multithreading: http://www.topcoder.com/longcontest/?module=ViewProblemStatementcompid=5624rd=9892 (you'll need to login to see the problem statement, but basically it's Sudoku, on a 16-core Xeon (I think)) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad for Set?
Ronald Guida: I'm pondering, is it possible to define a Set monad analogous to the List monad? [snip] This leads me think of a different solution: What if I could define a Set monad that's smart enough to know, for any type a, whether or not (Eq a) holds, and degenerate to a blind list if the elements can't be equated. Ultimately, what I would need is a way to overload join (or bind) with two different implementations, one for types that satisfy (Eq a), and another implementation for all other types. You might find this interesting, in case you haven't yet seen it: http://article.gmane.org/gmane.comp.lang.haskell.cafe/18118 If you also read the rest of that thread, you'll see that with a recent GHC HEAD, you should be able to avoid the need for the Teq witness. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: multi-methods in Haskell
peterv wrote:
This is very nice, but it does not really solve the original problem.
To get Haskell to choose the best fit it's necessary to encode the
location of each element in the hierarchy, so that elements deeper in
the hierarchy are more instantiated than those at the top. Then instance
selection chooses the best fit by just choosing the most instantiated match.
Encoding can be done using phantom types, so a generic solid has the path
IsSolid s
a planet has
IsSolid (IsPlanet p)
and a specific planet eg Earth has path
IsSolid (IsPlanet Earth)
A newtype can be used to associate the path with the actual object:
newtype InH path body = InH body
so Earth is represented by
InH Earth :: InH (IsSolid (IsPlanet Earth)) Earth
A class with a functional dependency gives us the mapping between
concrete objects and the objects as viewed by the hierarchy:
class ToH body path | body - path where
toH :: body - InH path body
toH = InH
The functional dependency means that the path (location in the
hierarchy) is uniquely determined by the body, and instance decls then
define this relationship:
instance ToH Asteroid (IsSolid Asteroid)
instance ToH Jupiter (IsSolid (IsPlanet Jupiter))
instance ToH Earth (IsSolid (IsPlanet Earth))
The code is below but as you can see the OOP encoding in Haskell becomes
quite heavy and clunky so this style is probably not ideal for a real
program - Tillmann's suggestion to use algebraic datatypes instead is
more idiomatic - but anyway here goes:
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances
-fallow-overlapping-instances #-}
module Collide where
class Collide a where
collide :: a - String
data Asteroid = Asteroid
data Jupiter = Jupiter
data Earth = Earth
data IsSolid a
data IsPlanet a
newtype InH path body = InH body
class ToH body path | body - path where
toH :: body - InH path body
toH = InH
instance ToH Asteroid (IsSolid Asteroid)
instance ToH Jupiter (IsSolid (IsPlanet Jupiter))
instance ToH Earth (IsSolid (IsPlanet Earth))
data Collision = forall a. Collide a = Collision a
mkCollision
:: (ToH a pa, ToH b pb, Collide (InH pa a, InH pb b))
= a - b - Collision
mkCollision a b = Collision (toH a, toH b)
instance Collide (InH (IsSolid a) aa, InH (IsSolid b) bb) where
collide _ = generic collision
instance Collide (InH (IsSolid Asteroid) Asteroid, InH (IsSolid
(IsPlanet bb)) cc) where
collide _ = an asteroid hit a planet
instance Collide (InH (IsSolid (IsPlanet a)) aa, InH (IsSolid Asteroid)
Asteroid) where
collide _ = an asteroid hit a planet
instance Collide (InH (IsSolid Asteroid) Asteroid, InH (IsSolid
(IsPlanet Earth)) Earth) where
collide _ = the end of the dinos
instance Collide (InH (IsSolid (IsPlanet Earth)) Earth, InH (IsSolid
Asteroid) Asteroid) where
collide _ = the end of the dinos
instance Collide Collision where
collide (Collision a) = collide a
--- ghci output
*Collide mapM_ putStrLn (map collide
[ mkCollision Asteroid Earth
, mkCollision Earth Asteroid
, mkCollision Jupiter Asteroid
, mkCollision Asteroid Jupiter
, mkCollision Asteroid Asteroid
])
the end of the dinos
the end of the dinos
an asteroid hit a planet
an asteroid hit a planet
generic collision
*Collide
Best regards, Brian.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
