Re: [Haskell-cafe] Question about instance
John Velman [EMAIL PROTECTED] writes:
data Relation a i b = Rel {name::RN, arity::Int, members::(Set [EN])}
Why do you parametrize the data type when you don't use the
parameters? Either do
data Relation = Rel {name::RN, arity::Int, members::Set [EN]}
or
data Relation a i b = {name::a, arity::i, members::Set b}
(or whatever you intended).
instance (Show a, Show i, Show b) = Show (Relation a i b)
where
show (Rel a i b) =
a ++ / ++ (show i) ++
++ (show b)
It doesn't matter whether a,i,b are in Show, as you don't use them
(they are completely unrelated to the a,i,b in (Rel a i b), the former
are types, the latter are variables)
-kzm
PS: Please don't quote the entire thread in each message. Although I
haven't seen Andreas' message on the list (yet).
--
If I haven't seen further, it is by standing in the footprints of giants
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Linear shuffle
Hi, I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: shuffle :: [a] - IO [a] shuffle [] = return [] shuffle x = do r - randomRIO (0::Int,length x - 1) s - shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak [EMAIL PROTECTED] writes: shuffle :: [a] - IO [a] shuffle [] = return [] shuffle x = do r - randomRIO (0::Int,length x - 1) s - shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? The length seems to me to be constant, so you could presumably calculate it once, and pass it as a parameter. Then, given the index 'r' you could use 'splitAt r' to split the string, and join the first part to the tail of the second, prepending the head of the second. More precisely (I hope this is not a homework excercise :-): : (s1,s2) = splitAt r return (head s2 : s1 ++ tail s2) This reduces the three (four if you include length) traversals to one. -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? Here is an algorithm known as a perfect-shuffle... I am not too sure of the efficiency compared to the example you gave, but it builds a tree to enable faster lookup. Keean module Lib.MetaSearch.Shuffle(shuffle) where import Random import Int import GHC.IOBase (unsafeInterleaveIO) data Tree a = Leaf a | Node !Int (Tree a) (Tree a) deriving Show buildTree :: [a] - Tree a buildTree = growLevel . (map Leaf) where growLevel :: [Tree a] - Tree a growLevel [node] = node growLevel l = growLevel (inner l) inner :: [Tree a] - [Tree a] inner [] = [] inner [e] = [e] inner (e1:e2:rest) = join e1 e2 : inner rest join :: Tree a - Tree a - Tree a join l@(Leaf _) r@(Leaf _) = Node 2 l r join l@(Node i _ _) r@(Leaf _) = Node (i+1) l r join l@(Leaf _) r@(Node i _ _) = Node (i+1) l r join l@(Node i _ _) r@(Node j _ _) = Node (i+j) l r shuffle1 :: [a] - [Int] - [a] shuffle1 elements rseq = shuffle' (buildTree elements) rseq where shuffle' :: Tree a - [Int] - [a] shuffle' (Leaf e) [] = [e] shuffle' tree (r0:rs) = case extractTree r0 tree of (b0,bs) - b0 : shuffle' bs rs extractTree :: Int - Tree a - (a,Tree a) extractTree 0 (Node _ (Leaf e) r) = (e,r) extractTree 1 (Node 2 (Leaf l) (Leaf r)) = (r,Leaf l) extractTree n (Node c (Leaf l) r) = case extractTree (n-1) r of (e,r') - (e,Node (c-1) (Leaf l) r') extractTree n (Node c l (Leaf e)) | n+1 == c = (e,l) extractTree n (Node c l@(Node c1 _ _) r) | n c1 = case extractTree n l of (e,l') - (e,Node (c-1) l' r) | otherwise = case extractTree (n-c1) r of (e,r') - (e,Node (c-1) l r') randList :: Int - IO [Int] randList 1 = return [] randList n = do a0 - getStdRandom $ randomR (0,n-1) as - unsafeInterleaveIO $ randList (n-1) return (a0:as) shuffle :: [a] - IO [a] shuffle s = do a - randList $ length s return $ shuffle1 s a ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Tomasz Zielonka [EMAIL PROTECTED] writes: On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? You can use mutable arrays (modules Data.Array.MArray, Data.Array.IO). But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle. -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, Jan 14, 2005 at 10:17:27AM +0100, Ketil Malde wrote: Tomasz Zielonka [EMAIL PROTECTED] writes: On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? You can use mutable arrays (modules Data.Array.MArray, Data.Array.IO). But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle. Perhaps I don't know this particular algorithm, but you can shuffle the array with linear number of swaps. No need to shift elements. Best regards, Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, 14 Jan 2005, Gracjan Polak wrote: I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: shuffle :: [a] - IO [a] shuffle [] = return [] shuffle x = do r - randomRIO (0::Int,length x - 1) s - shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? Is it a good idea to use IO monad for this plain computation? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt For an explanation of the algorithm. Keean. Ketil Malde wrote: Tomasz Zielonka [EMAIL PROTECTED] writes: On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? You can use mutable arrays (modules Data.Array.MArray, Data.Array.IO). But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle. -kzm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? Oleg wrote a great article on implementing the perfect shuffle. with some sample code. http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Tomasz Zielonka [EMAIL PROTECTED] writes: But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle. Perhaps I don't know this particular algorithm, but you can shuffle the array with linear number of swaps. No need to shift elements. Right - this implementation picked an arbitrary element, placed it in front, and repeated, if I understood it correctly. Slightly different from moving each element to a random position (e.g. after k shuffles, elements (k+1..n) will be in the original order), but perhaps this too can be easily emulated with an array-based (direct) shuffle? -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Introducing me
Hi, my name is Fabian Otto. I'm doing my master in computer science at the technical university of Berlin (Germany). I have choosen advanced functional programming (FTFP) [1] as one of my subjects. In this course we use opal[2] with some unimplemented features. e.g: * optional laziness * parametic types * theories / typeclasses Some topics in this course are: * monads * fixpoint algorithmes / cpos * parser generatoren * optimized datastructures ( e.g. queues) * reference counting To deepen my understanding in these topics I have choosen Haskell and I am really looking forward participating in this mailinglist Thanks for reading. Otto [1]: http://uebb.cs.tu-berlin.de/lehre/2004SVftfp/ [2]: http://www.cs.nott.ac.uk/~gmh//faq.html#opal -- bookmarks: http://del.icio.us/sigsegv jabber: [EMAIL PROTECTED] wiki/blog: http://jotpee.de/blog ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Keean Schupke [EMAIL PROTECTED] writes: Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt For an explanation of the algorithm. Right. I was commenting based on the source posted by Gracjan. (And http://c2.com/cgi/wiki?LinearShuffle contains a variety of shuffling algorithms). -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Henning Thielemann wrote: Is it a good idea to use IO monad for this plain computation? It is needed as random number supply. -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
John Meacham wrote: Oleg wrote a great article on implementing the perfect shuffle. with some sample code. http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle Thats the kind of answer I was hoping to get :) Thanks. shuffle could be useful in standard library. At least Python has it. I was translating some small Python program, the hardest part was the missing shuffle function. What do you think? -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Am Freitag, 14. Januar 2005 09:50 schrieb Ketil Malde: Gracjan Polak [EMAIL PROTECTED] writes: shuffle :: [a] - IO [a] shuffle [] = return [] shuffle x = do r - randomRIO (0::Int,length x - 1) s - shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? The length seems to me to be constant, so you could presumably calculate it once, and pass it as a parameter. Whether the length is constant depends on how you interpret this statement, passing it as a parameter is absolutely the thing to do, say shuffle :: [a] - IO [a] shuffle as = do let len = length as lenShuffle as len lenShuffle :: [a] - Int - IO [a] lenShuffle _ 0 = return [] lenShuffle as n = do r - randomRIO (0,n-1) let (xs, h:ys) = splitAt r as s - lenShuffle (xs++ys) (n-1) return (h:s) This reduces the three (four if you include length) traversals to one. and apparently is of linear behaviour. BTW, if splitAt were implemented as stated in the report, it wouldn't be any better than using take and drop, even as is, it saves only about 25% of the work. The real villains in the original code are the repeated evaluation of length and (!!), both leading to O(n^2) complexity (I think, I didn't properly analyze it). -kzm all the best, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: I/O interface
First of all, I don't think any OS shares file pointers between processes. Otherwise it would be practically impossible to safely use an inherited filehandle via any API. Different threads using the same filehandle do share a file pointer (which is a major nuisance in my experience, because of the lack of an atomic seek-read/write), but a Posix fork duplicates the file pointer along with all other state. I can't believe I'm wrong about this, but someone please correct me if I am. I'm afraid you _are_ wrong :-(... POSIX quite clearly states that the file descriptors are duplicated by fork(), but the open file descriptions (your file pointers) are shared. This is obvious by observing what happens when you write to the same fd in parent and child after a fork: you don't end up overwriting, you end up interleaving. --KW 8-) -- Keith Wansbrough [EMAIL PROTECTED] http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Introducing me
Hi, my name is Fabian Otto. Welcome! Feel free to join in the discussion. --KW 8-) -- Keith Wansbrough [EMAIL PROTECTED] http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, 14 Jan 2005, Scott Turner wrote: The shuffling algorithms mentioned so far are comparable to insertion/selection sort. I had come up with a shuffler that relates to quicksort, in that it partitions the input randomly into lists and works recursively from there. It looks efficient and works out well in Haskell. I did some shuffling based on mergesort, that is a list is randomly split (unzipped) into two lists and the parts are concatenated afterwards. You must repeat this some times. It even works for infinite lists. It doesn't need IO. randomPermute :: RandomGen g = [a] - g - ([a],g) randomPermute x g0 = let (choices,g1) = runState (mapM (const (State (randomR (False,True x) g0 xc = zip x choices in (map fst (filter snd xc ++ filter (not . snd) xc), g1) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Matroids in Haskell
Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? It would save me some time figuring out if this part of mathematics is useful for my work ... Thanks in advance, Gerhard Gerhard Navratil Teaching- And Research-Assistant Technical University Vienna, Austria Institute of Geoinformation and Cartography Gusshausstr. 27-29, 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12712 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Henning Thielemann [EMAIL PROTECTED] writes: I did some shuffling based on mergesort, that is a list is randomly split (unzipped) into two lists and the parts are concatenated afterwards. You must repeat this some times. It even works for infinite lists. I think it doesn't guarantee equal probabilities of all permutations. -- __( Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Introducing me
Hi, my name is Fabian Otto. Heya. Some other fixtures of the Haskell Community are covered on this page, http://haskell.org/hawiki/HaskellCommunities. Two noteworthy ones are the wiki (http://haskell.org/hawiki/) obviously, and the #haskell IRC channel on irc.freenode.net (http://haskell.org/hawiki/HaskellIrcChannel) which has about a hundred or so people on it at a time. Many of the quotes on* http://haskell.org/hawiki/QuotesPage are from the IRC channel, so that may give you an idea of what it's like, at least at the more humorous moments. * For others who haven't looked at it, it is quite entertaining. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Matroids in Haskell
On Fri, 14 Jan 2005, Gerhard Navratil wrote: Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? Do you mean a Matroid type class? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Matroids in Haskell
Hello! Gerhard Navratil wrote: Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? What is a matroid? Thanks Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak [EMAIL PROTECTED] wrote: John Meacham wrote: Oleg wrote a great article on implementing the perfect shuffle. with some sample code. http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle Thats the kind of answer I was hoping to get :) Thanks. shuffle could be useful in standard library. At least Python has it. I was translating some small Python program, the hardest part was the missing shuffle function. What do you think? Also, note that, in a lazy language, the algorithm's complexity will be dependent on the number of cards drawn from the deck, are possibly sub-linear in the number of cards in the deck. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugs vs GHC (again)was: Re: Somerandomnewbiequestions
On Wed, Jan 12, 2005 at 12:21:25AM +, Aaron Denney wrote: On 2005-01-11, Simon Marlow [EMAIL PROTECTED] wrote: On 11 January 2005 14:15, Gracjan Polak wrote: Simon Marlow wrote: There's a big lock on File. If you want to do truly concurrent reading, you can make multiple FileInputStreams, each of which has its own file descriptor (the Unix implementation uses dup(2)). Original and descriptor returned by dup or dup2 share file pointer. *blink* You're right! Serves me right for assuming that POSIX would have sensible semantics. Perhaps this API isn't implementable, in its current state. Others have pointed out pread() and pwrite(); Perhaps we can stick this function in an extension package. (Though it is required for Unix 98 conformance, so anything reasonable will have it. Hmm. Does open(/dev/fd/n) or (/proc/self/fd/n) act as dup() or a fresh open() to underlying file?) Actually, If I were writing new haskell libraries, I would use mmap whenever I could for accessing files. not only does it make the file pointer problem go away, but it can be drastically more efficient. of course, this can only be done on a limited type of file on some architectures, so it should be an optimization under the hood rather than an exposed interface. John -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
