Re[2]: [Haskell-cafe] foreach
Hello Michael, Thursday, September 14, 2006, 12:44:37 AM, you wrote: Or, what about using ListT to combine it with IO, eliminating the need for two separate `do' blocks? according to my experience, in most cases we need two do blocks just because outer one contains more code after inner one finishes up -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] program execution and laziness
Hello Tim, Thursday, September 14, 2006, 5:32:24 AM, you wrote: out - hGetContents o -- print out How can I force hGetContents to be strict (or at least to completely process the stream prior to the waitForProcess command)? return $! last out -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Numeric type classes
G'day all. Quoting Henning Thielemann [EMAIL PROTECTED]: A monoid operation is associative, isn't it? Duh. Yes. Sorry. Need caffeine. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optimization problem
splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] [snip] Furthermore it should work on infinite lists. It can't eat the whole list before producing any output. This doesn't seem to make sense? Only at the end of the list can you know that you've collected all the events for each channel. If you output anything before scanning to the end, you'd not know if there were perhaps more events on that channel? You could accumulate only over a window, which would produce values on an infinite input, though the output list could have multiple packets for each channel. splitterW 3 [(3,x),(1,y),(3,z),(2,w),(3,v)] [(3,[x,z]),(1,[y]),(2,[w]),(3,[v])] Or accumulate until either there are 'n' messages on a channel or the end of the list is reached? splitterN 3 [(3,x),(1,y),(3,z),(2,w),(3,v),(1,u),(3,t)] [(3,[x,z,v]),(1,[y,u]),(2,[w]),(3,[t])] Regards, Rohan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Numeric type classes
On Thu, Sep 14, 2006 at 01:11:56AM -0400, David Menendez wrote: Ross Paterson writes: I've collected some notes on these issues at http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/StandardClasses Coincidentally, I spent some time last week thinking about a replacement for the Num class. I think I managed to come up with something that's more flexible than Num, but still mostly comprehensible. The fact that the first part of your structure is much the same as the one on the web page (which is essentially that part of the revised numeric prelude plus a Haskell 98-compatible veneer) is evidence that it's pretty clear what to do with Num and Fractional. The only point of contention is whether to factor out monoid and semiring classes. Arguments against include: * There are lots of monoids, and (+) doesn't seem a reasonable symbol for some of them. * Having (+) work on lists, tuples and all the other monoids would make error messages more complicated. On the other hand, if we had a Natural type, it would be the standard example of a semiring. I'm not sure what the contract is for fromInteger. Perhaps something like, fromInteger 0 = zero fromInteger 1 = one fromInteger n | n 0 = negate (fromInteger (negate n)) fromInteger n = one + fromInteger (n-1) Which, actually, could also be a default definition. That is also the default definition in the revised numeric prelude, but we can do better using associativity: fromInteger n | n 0 = negate (fi (negate n)) | otherwise = fi n where fi 0= zero fi 1= one fi n | even n= fin + fin | otherwise = fin + fin + one where fin = fi (n `div` 2) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
On Wed, 13 Sep 2006, Magnus Jonsson wrote: When programming the other day I ran into this problem. What I want to do is a function that would work like this: splitStreams::Ord a=[(a,b)]-[(a,[b])] splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] Interestingly we use such a routine in Haskore for splitting a sequence of notes into sequences of notes of equal instruments. It's implemented rather the same way like your version. It's 'slice' in http://darcs.haskell.org/haskore/src/Haskore/Basic/TimeOrderedList.lhs but it is a bit more complicated because it has to manage time information. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Magnus Jonsson [EMAIL PROTECTED] writes: splitStreams::Ord a=[(a,b)]-[(a,[b])] splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] [...] But is there any way to write it such that each element is touched only once? Or at least an O(n*log(m)) algorithm? I guess it should be possible to use a quicksort-like algorithm, splitting the stream into three streams with keys less than, equal, and greater than the first element, and recurse on the less/equal streams? something like this, then? splitStreams :: Ord a = [(a, b)] - [(a, [b])] splitStreams [] = [] splitStreams ((a, b) : t) = (a, b : bs) : splitStreams t' where (bs, t') = foldr f ([], []) t f z@(a', b') (bs, t') = if a' == a then (b' : bs, t') else (bs, z : t') (i guess i should use a strictness '!' for (xs, ys), but i am still running ghc-6.5, and i don't like the case constructions that much. does this bite me here? i didn't check, really.) who can tune this any further? cheers, m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ambiguous partially defined type problem
Dear all, For a project involving I use some partially defined node (in this case a simple record, in my project state transformers) in which the defined part is common to all nodes, and the custom part is different for each node. They have to become anonymous so I can put them in a list of connections from each node to another. For some reason GHC complains of 'ambigous type variable' in the code below. The thing is, part of the code may be undefined, but since I'm (explicitly) not using that part, why would GHC care? Are there other solutions to this problem? Any pointers or comments appreciated. Thanks. Maarten (This code is just some dummy code that contains the essence of the problem. I posted the complete code with piggy bagged state transformers in active objects on haskell@haskell.org, but that is rather long and this seems to be the correct mailing list). -- data structure with custom and common part data Node cust = Node cust Common deriving (Show,Typeable) -- anonymous data structure to put use in list data AN = forall ar. (Show ar, Typeable ar) = AN ar instance Show AN where show (AN an) = AN ( ++ show an ++ ) -- common part data Common = Common Integer deriving (Show,Typeable) data Custom = Custom Integer deriving (Show,Typeable) data Custom2 = Custom2 Integer deriving (Show,Typeable) -- extract common part, ignoring type of custom part getCommon :: forall gc. (Node gc) - Common getCommon (Node cust com) = com main = do let a = AN (Node (Custom 5) (Common 10)) let b = case a of (AN a') - getCommon (case (cast a') of Just a'' - a'') putStrLn $ ok: ++ show b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] foreach
Hello Tim, Wednesday, September 13, 2006, 10:48:37 PM, you wrote: I would like to add to this. The previous loop runs the code once independantly for each item in the list. Sometimes you want to carry state through the loop: all this can be easily implemented by programmer himself. but we can't add our own syntax constructions. so it will be great to either add constructs that mimics existing imperative languages or a way to redefine syntax on-the-fly. second can be implemented by using Parsec-like parser in haskell compiler. i also seen a syntax macros for Haskell: http://www.cs.uu.nl/groups/ST/twiki/pub/Center/SyntaxMacros/sm_example.zip one project that adds syntax sugar for manipulating imperative arrays and hashes is http://www.isi.edu/~hdaume/STPP/stpp.tar.gz we can also develop some ideas that will allow user to extend language with imperative-friendly features. first, the problem is that Haskell requires to exactly specify order of evaluation. but in many cases it's not important - when we want to multiply values of two variables, it's no matter what variable will be read first. so, instead of a' - val a b' - val b c =: a' * b' we will prefer to write c =: a*b this involves a lot of problems with types and and need to redefine classes for every operation that can be used in such way second, we need to be able to define new keywords together with using layout statements in our constructs: for i in [1..n] while a[i]0 do may be it should be just syntax-level macro which generates code like this: foreachCond [1..n] (a]i]0) $ \i - do and last problem is what code to generate for break/continue (goto? :) operations -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Magnus Jonsson wrote: splitStreams::Ord a=[(a,b)]-[(a,[b])] splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] I'm afraid this algorithm is O(n*m) time in the worst case, where n is the length of the input list, and m is the number of unique channels. But is there any way to write it such that each element is touched only once? Or at least an O(n*log(m)) algorithm? This can be done. It's an interesting puzzle to make it work for infinite lists. For finite lists, sortBy + groupBy + map easily do the job. The problem is dealing with holes in data structures in Haskell, which are to be filled in later. This can be done by providing blueprints for them. Let's define a basic map: data Map k a = Node k a (Map k a) (Map k a) | Leaf We will use Map k () as blueprints - the () indicate where the holes are. Next we define a lookup function, which takes a blueprint and evaluates the correct hole in a second map: lookup :: Ord k = k - Map k () - Map k a - Maybe a lookup _ Leaf_ = Nothing lookup k (Node k' _ l r) ~(Node _ a' l' r') = case compare k k' of LT - lookup k l l' EQ - Just a' GT - lookup k r r' As you can see, the structure of the second argument is forced by the first argument. The lazy pattern assures that we don't look at the second argument too early. In a similar fashion, we can define an update function: update :: Ord k = k - (a - a) - Map k x - Map k a - Map k a update k f (Node k' _ l r) ~(Node _ a' l' r') = case compare k k' of LT - Node k' a' (update k f l l') r' EQ - Node k' (f a') l' r' GT - Node k' a' l' (update k f r r') Next comes insert. Insert takes a blueprint and inserts a key into it. It also takes a map and removes the corresponding hole from it. To simplify the code it does no balancing. [1] insert :: Ord k = k - Map k () - Map k a - (Map k (), Map k a) insert k Leaf_ = (Node k () Leaf Leaf, Leaf) insert k (Node k' _ l r) ~(Node _ a' l' r') = case compare k k' of LT - let (m, m') = insert k l l' in (Node k' () m r, Node k' a' m' r') EQ - error inserting existing element GT - let (m, m') = insert k r r' in (Node k' () l m, Node k' a' l' m') We also need a map, defined in the usual fashion, without the blueprint. A version with blueprint can also be defined, but it isn't necessary for our problem: map :: (a - b) - Map k a - Map k b map _ Leaf = Leaf map f (Node k a l r) = Node k (f a) (mapMap f l) (mapMap f r) We can now build the splitStream function, using the following helper function: splitSeq' :: Ord a = Map a () - [(a,b)] - ([(a,[b])], Map a [b]) splitSeq' bp [] = ([], map (const []) bp) splitSeq' bp ((a,b):xs) = case lookup a bp bp of Just _ - let (l, m) = splitSeq' bp xs in (l, update a (b:) bp m) _ - let (bp', m) = insert a bp m' (l, m') = splitSeq' bp' xs in ((a, b : (fromJust $ lookup a bp' m')) : l, m) splitSeq' takes a blueprint for a map with all keys seen so far, and a list tail. It returns the result list for all new keys, and a map (corresponding to the given blueprint) with the tails of the seen elements. The in the base case it just fills the blueprint with empty lists and returns to the caller. If a new element is seen, insert is used to create a new blueprint, including the new key a, which is passed to the recursive call of splitSeq'. The resulting map from that call is threaded back into insert, which gives us a new map without the a key which matches the structure of the original blueprint. Finally we can define splitSeq as follows: splitSeq :: Ord a = [(a,b)] - [(a,[b])] splitSeq = fst . splitSeq' Leaf A quick test: *Main let s = splitSeq ([(3,'x'),(1,'y'),(3,'z'),(2,'w')] ++ repeat (4,' ')) *Main s !! 0 (3,xzInterrupted. (I pressed ^C) *Main s !! 2 (2,wInterrupted. (ditto) *Main s !! 3 (4, ... Is there a simpler way to do this? I don't know. I'm also unsure whether it is a good idea - unless you use several threads to process the list the code will produce a lot of thunks, and eat a lot of memory. The code above provides a maximum amount of lazyness while using O(n log m) time. Depending on the circumstances processing the list in chunks and using techniques like the above to combine the result will be better. enjoy, Bertram [1] Balancing can be done with the information in the blueprint, and mapping back is easily done by doing the transformation on the tree in reverse. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ambiguous partially defined type problem
Maarten wrote: For a project involving I use some partially defined node (in this case a simple record, in my project state transformers) in which the defined part is common to all nodes, and the custom part is different for each node. They have to become anonymous so I can put them in a list of connections from each node to another. For some reason GHC complains of 'ambigous type variable' in the code below. The thing is, part of the code may be undefined, but since I'm (explicitly) not using that part, why would GHC care? Are there other solutions to this problem? Any pointers or comments appreciated. -- data structure with custom and common part data Node cust = Node cust Common deriving (Show,Typeable) -- anonymous data structure to put use in list data AN = forall ar. (Show ar, Typeable ar) = AN ar instance Show AN where show (AN an) = AN ( ++ show an ++ ) -- common part data Common = Common Integer deriving (Show,Typeable) data Custom = Custom Integer deriving (Show,Typeable) data Custom2 = Custom2 Integer deriving (Show,Typeable) -- extract common part, ignoring type of custom part getCommon :: forall gc. (Node gc) - Common getCommon (Node cust com) = com main = do let a = AN (Node (Custom 5) (Common 10)) let b = case a of (AN a') - getCommon (case (cast a') of Just a'' - a'') putStrLn $ ok: ++ show b Hi Maarten - The problem is that AN is far too general. The compiler can't tell that you've wrapped a Node, so the call to getCommon will fail to typecheck. Even if the compiler did know, by some other means, that a Node had been wrapped, Haskell doesn't support true existentials, so the type signature for getCommon doesn't do what I think you mean ie: getCommon :: forall gc. (Node gc) - Common is the same as writing: getCommon :: Node gc - Common whereas you'd really need an existential: getCommon :: (forall gc. Node gc) - Common The fact that gc is not used in the definition of getCommon doesn't matter, since the type system has to just use the same rules for type inference regardless of the content of the function. In other words, without true existentials, or some other extension to the type system, there is no way to propagate the fact that the actual binding for a type variable is never required. Also, AFAIK there is no guarantee that Node Int Common and Node String Common would always be laid out in memory in the same way - the compiler is allowed to use special optimized layouts for particular instantiations of cust (even though it probably won't be clever enough to do this at the moment in Haskell implementations). I suggest you wrap the custom part separately instead of wrapping the whole Node eg: data Custom = forall cust. ICusom cust = Custom cust data Node = Node Custom Common where the ICustom class is whatever class you need to be able to do anything useful with cust. Alternatively, you could wrap the custom part within the node as in: data Node = forall cust. ICustom cust = Node cust Custom getCommon :: Node - Common getCommon (Node cust com) = com Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Here's my attempt, also using the quicksort idea, but using two passes instead of tying the knot: import Data.Set hiding (map) First a binary search tree, with a lookup function: data Tree k v = Node (Tree k v) k v (Tree k v) get :: Ord a = a - Tree a b - b get a (Node l k v r) = case compare a k of LT - get a l EQ - v GT - get a r There's no empty case: we'll ensure that we only search for keys that are in the tree. Now to make a tree of lists from the list of pairs: mkTree :: Ord a = [(a,b)] - Tree a [b] mkTree [] = error unused mkTree ((a,b):abs) = Node l a (b:bs) r where l = mkTree [(a',b') | (a',b') - abs, a' a] r = mkTree [(a',b') | (a',b') - abs, a' a] bs = [b' | (a',b') - abs, a' == a] It remains to extract from this tree the list of second elements corresponding to the each distinct first element in the input list: splitStreams :: Ord a = [(a,b)] - [(a,[b])] splitStreams abs = [(a, get a t) | a - uniq (map fst abs)] where t = mkTree abs where uniq computes the list of unique elements of a list: uniq :: Ord a = [a] - [a] uniq = u empty where u s [] = [] u s (x:xs) | member x s = u s xs | otherwise = x : u (insert x s) xs There's no rebalancing, so it suffers from the same problems as quicksort. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] ambiguous partially defined type problem
Hello Brian, Thursday, September 14, 2006, 7:43:55 PM, you wrote: Even if the compiler did know, by some other means, that a Node had been wrapped, Haskell doesn't support true existentials whereas you'd really need an existential: getCommon :: (forall gc. Node gc) - Common they are supported in ghc 6.6 with name of impredicative polymorphism, section 7.4.9 or 7.4.10 of new user manual -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Optimization problem
I wrote: [1] Balancing can be done with the information in the blueprint, and mapping back is easily done by doing the transformation on the tree in reverse. I should add that this possibility was the main reason for dealing with blueprints at all. As Ross Paterson's solution shows, it's possible to get simpler code without balancing the tree. regards, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Hello, I think it is possible to do it in O(n) (if you change the representation of the output stream). Note that the solution is quite similar toTwan van Laarhoven, and it should be trivial use Map instead of Rel. Here is my take on it: The type of the output stream: type Rel a b = a - [b] Here are cons and nil: cons :: Eq a = (a,b) - Rel a b - Rel a b cons (x,y) l z | x == z= y : l x | otherwise = l z nil :: Rel a b nil _ = [] and a lookUp function: lookUp :: Rel a b - a - [b] lookUp = id Finally the splitStreams algorithm: splitStreams :: Eq a = [(a,b)] - Rel a b splitStreams = foldr cons nil Here is a test with finite lists: fin = splitStreams [(3,'x'),(1,'y'),(3,'z'),(2,'w')] and here are the console tests: *General7 lookUp fin 1 y *General7 lookUp fin 2 w *General7 lookUp fin 3 xz Now with infinite lists: inf = splitStreams (map (\x - (0, x)) [1..]) and here a case where it terminates with infinite lists: *General7 take 10 (lookUp inf 0) [1,2,3,4,5,6,7,8,9,10] Cheers, Bruno Oliveira ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimization problem
Thanks Bertran for your solution. I have difficulty understanding it so I can't comment on it right now but I'll try to have a look at it. Do you know of any article that explains this technique, starting from very simple examples? /Magnus On Thu, 14 Sep 2006, Bertram Felgenhauer wrote: I wrote: [1] Balancing can be done with the information in the blueprint, and mapping back is easily done by doing the transformation on the tree in reverse. I should add that this possibility was the main reason for dealing with blueprints at all. As Ross Paterson's solution shows, it's possible to get simpler code without balancing the tree. regards, Bertram ___ 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
[Haskell-cafe] Haskore microtonal support
On Thu, 14 Sep 2006, Henning Thielemann wrote: On Thu, 14 Sep 2006, Magnus Jonsson wrote: Now even more interestingly, my program also deals with music! :) I'm generating microtonal midi files. I use it for very much the same purpose as you do (although my program is not yet finished). Is it something we could and should add to Haskore? If Haskore could support microtones that would make this world a slightly better world for me. Here are the basic things you need to support microtonal music: - Pitch representations would have to be able to express any pitch. - One appealing approach is to represent a pitch directly as it's frequency. - Probably the most useful representation though is a base pitch, say one of C,D,E,F,G,A,B, followed by a list of accidentals that modify the pitch. The user should be able to define his own base pitches and accidentals, in terms of cents or frequency ratios or something similar. - Generating microtonal midi files requires that you add pitch-bend messages before all notes. That restricts each midi channel to only being able to play one note at a time. This is a big deficiency in the midi protocol imo. / Magnus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimization problem
Magnus Jonsson wrote: Thanks Bertran for your solution. I have difficulty understanding it so I can't comment on it right now but I'll try to have a look at it. Do you know of any article that explains this technique, starting from very simple examples? Not really. It's a result of thinking about lazy evaluation, and especially lazy patterns (and let bindings) for some time. A wiki article that helped me a lot to understand these is http://www.haskell.org/hawiki/TyingTheKnot I'd like to point out the trustList function there which uses the idea of encoding the structure of a term and its actual values in different arguments, i.e. a blueprint. HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Hello Magnus, You are right. Silly me. I was thinking of Rel as a kind of Hashtable. In this case, I think it should be possible to have O(n), since "cons" would only need constant time. Cheers, Bruno On Thu, 14 Sep 2006 13:11:05 -0400 (EDT), Magnus Jonsson wrote: Thanks Bruno. However I think this is still O(n*m). As far as I understand your code it is a longwinded way to say "[b | (a,b) - input, b == myChannelOfInterest]". This is fine if you are only interested in one channel, and for that case I agree it's O(n), but if you are interested in many different channels, it will take O(n*m). Here's why I think your code is equivalent to using a filter/list-comprehension: cons :: Eq a = (a,b) - Rel a b - Rel a b cons (x,y) l z | x == z= y : l x | otherwise = l z z is the channel that the user is interested in. x is the channel of the current message in the list. y is the message content. l is a function for searching the rest of the list. For each element of the list you create a function that compares the requested channel to a (in (a,b)). If it's the same, you return that element followed by a continued search down the list. If you don't find it, you forward the request to the next function down the list. That's exactly the same as what the filter function does. It is possible I made a mistake somewhere and if I did, let me know. / Magnus On Thu, 14 Sep 2006, Bruno Oliveira wrote: Hello, I think it is possible to do it in O(n) (if you change the representation of the output stream). Note that the solution is quite similar toTwan van Laarhoven, and it should be trivial use "Map" instead of "Rel". Here is my take on it: The type of the output stream: type Rel a b = a - [b] Here are cons and nil: nil :: Rel a b nil _ = [] and a lookUp function: lookUp :: Rel a b - a - [b] lookUp = id Finally the splitStreams algorithm: splitStreams :: Eq a = [(a,b)] - Rel a b splitStreams = foldr cons nil Here is a test with finite lists: fin = splitStreams [(3,'x'),(1,'y'),(3,'z'),(2,'w')] and here are the console tests: *General7 lookUp fin 1 "y" *General7 lookUp fin 2 "w" *General7 lookUp fin 3 "xz" Now with infinite lists: inf = splitStreams (map (\x - (0, x)) [1..]) and here a case where it terminates with infinite lists: *General7 take 10 (lookUp inf 0) [1,2,3,4,5,6,7,8,9,10] Cheers, Bruno Oliveira ___ 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] Re: Numeric type classes
Ross Paterson writes: On Thu, Sep 14, 2006 at 01:11:56AM -0400, David Menendez wrote: Coincidentally, I spent some time last week thinking about a replacement for the Num class. I think I managed to come up with something that's more flexible than Num, but still mostly comprehensible. The fact that the first part of your structure is much the same as the one on the web page (which is essentially that part of the revised numeric prelude plus a Haskell 98-compatible veneer) is evidence that it's pretty clear what to do with Num and Fractional. That being said, I don't expect anything to change. I've looked through the revised numeric prelude, but the qualified class names put me off. Everything shows up in Haddock as C. Also, it doesn't support naturals--which, admittedly, is not a big loss. The only point of contention is whether to factor out monoid and semiring classes. Arguments against include: * There are lots of monoids, and (+) doesn't seem a reasonable symbol for some of them. True enough. (At least it's more general than mappend.) I would expect all the more specific monoid operators, like (||) and (++), to stick around for readability when not writing non-monoid-generic code. Not to mention that (+) and (++) associate differently. * Having (+) work on lists, tuples and all the other monoids would make error messages more complicated. It gets worse than that. Imagine trying to explain to someone why 1 + sin is actually \a - const 1 a + sin a. On the other hand, tuples could be made an instance of Num right now. -- David Menendez [EMAIL PROTECTED] | In this house, we obey the laws http://www.eyrie.org/~zednenem |of thermodynamics! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Numeric type classes
David Menendez wrote: * Having (+) work on lists, tuples and all the other monoids would make error messages more complicated. It gets worse than that. Imagine trying to explain to someone why 1 + sin is actually \a - const 1 a + sin a. It isn't that hard - it is done routinely in mathematics courses. In fact, that is what 1+sin means in Maple today (and has for 25 years). It is also what it means in MuPAD. AFAIK, that is also what 1+Sin means in Mathematica. That is what polymorphism is all about! [This is really equational-theory polymorphism rather than parametric polymorphism, but that's a minor detail, since Monad polymorphism is _also_ equational-theory polymorphism]. This kind of polymorphism [where you add the 'right number' of arrows on the left] is quite useful. Things like differential operators become quite tiresome to write down if you have to pedantically spell everything out, even though there is only one 'sensible' way to interpret a given expression [1]. In the very same way that fromInteger can project a literal integer into other typeclasses, one can project values into spaces of functions by just adding arrows on the left (ie exactly what const does). It is possible to make this quite formal, but you need Natural(s) (as an additive monoid) on the type level, and then be able to be polymorphic over _those_ to do make it all work. It should even be decidable [but that part I have not checked]. Something I should write up one of these days, but in the meantime go read [1]! Jacquces [1] Bjorn Lisper and Claes Thomberg have already investigated something very close to this, see http://www.mrtc.mdh.se/index.php?choice=publicationsid=0245 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Numeric type classes
[EMAIL PROTECTED] wrote: That is what polymorphism is all about! Not in this context, sorry. This is a convention. Another one may give you an abomination, e.g., 1+sin means 1 plus the addres of the sin routine. (Of course not in a 'decent' language, but I know a few undecent. No, it is much more than convention. In this case, it can be made completely formal. The paper I referred to offers one way to do this. I sketched another. Yes, it is possible to have 1+sin become meaningless in 'indecent' languages. But as the mathematics (and Maple and ...) convention shows, there is one reasonable way to make this make sense which turns out to be quite useful. In other words, the convention can be turned into a rule. ML and Haskell have (thankfully) learned a lot from Lisp and Scheme, and then proceeded to 'tame' these with static typing. And this is continuing - witness the flurry of type-theoretical research on continuations in the last 15 years (and very recent papers on typed delimited continuations). More recently, GADTs have added to the set of 'safe' programs that can by typed (which Lisp programmers writing interpreters knew all along). I am saying that the case of 'adding arrows to the left' is another safe practice. I backed myself up with a published reference [ie I took your comment regarding some of my previous haskell-cafe postings seriously!]. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Optimization problem
Bertram Felgenhauer wrote: splitSeq' :: Ord a = Map a () - [(a,b)] - ([(a,[b])], Map a [b]) splitSeq' bp [] = ([], map (const []) bp) splitSeq' bp ((a,b):xs) = case lookup a bp bp of Just _ - let (l, m) = splitSeq' bp xs in (l, update a (b:) bp m) _ - let (bp', m) = insert a bp m' (l, m') = splitSeq' bp' xs in ((a, b : (fromJust $ lookup a bp' m')) : l, m) splitSeq' takes a blueprint for a map with all keys seen so far, and a list tail. It returns the result list for all new keys, and a map (corresponding to the given blueprint) with the tails of the seen elements. The in the base case it just fills the blueprint with empty lists and returns to the caller. If a new element is seen, insert is used to create a new blueprint, including the new key a, which is passed to the recursive call of splitSeq'. The resulting map from that call is threaded back into insert, which gives us a new map without the a key which matches the structure of the original blueprint. Very interesting! So the map with the seen tails matches the blueprint and therefore throws away information (the future keys) from the future. This is what effectively allows the key-tree structure to be rebalanced. If one would return the tails-map with all future keys, it would be _|_ because the key-order in the tree depends on the future keys and changes everytime when a new key is found. I thought that there can only be a static solution, i.e. like the one Ross Paterson presented where the structure (I mean the outermost constructors) of the returned tree are determined before the future. This obviously excludes rebalancing. I found a static solution by trying to fit the key-tails pairs into an infinite tails-map which is filled first comes first: map ! 1 := (first key seen, tails) map ! 2 := (second key seen, tails) By keeping another key-position-map around which records where each key has been inserted, so that the future knows where to put the tails. The point is that the structure of tails-map is known before the future comes as its keys are just 1,2,3,... and so on. It remains to construct such an infinite random access list, but this is turns out to be even easier than finite random access lists (when using non-uniform recursion from Okasaki's chapter 10) :) data Imp a = Imp a (Imp (a,a)) deriving (Show) instance Functor Imp where fmap h ~(Imp x xs) = Imp (h x) (fmap (\(x,y) - (h x, h y)) xs) update :: (a - a) - Position - Imp a - Imp a update f 1 ~(Imp x xs) = Imp (f x) xs update f n ~(Imp x xs) = Imp x $ update f2 (n `div` 2) xs where f2 ~(y,z) = if even n then (f y, z) else (y, f z) Note that we can use irrefutable patterns without hesitation as there is only one constructor. Folding over an infinite thing is strange but here we are fold :: (a - b - b) - Imp a - b fold f ~(Imp x xs) = f x (fold f2 xs) where f2 (x,y) z = f x (f y z) It's not so strange anymore when we realize that this can be used to convert it into an infinite list toList = fold (:) The implementation of fromList is fun as well, so I won't tell it. As fold and unfold can be defined generically for Mu f where f is a functor, i wonder how to deal with it in the case of non-uniform recursion. For splitStreams, the key-position-map is needed in both directions, so we quickly define a bijective map type BiMap a b= (Map.Map a b, Map.Map b a) switch :: BiMap a b - BiMap b a switch (x,y) = (y,x) with the usual operations (empty, member, size etc.) omitted here. Now comes splitStreams itself: splitStreams :: Ord a = [(a,b)] - [(a,[b])] splitStreams xs = takeWhile (not . null . snd) $ toList $ splitStreams' empty xs splitStreams' :: Ord a = BiMap a Position - [(a,b)] - Imp (a,[b]) splitStreams' bimap [] = fmap (\i - (findWithDefault undefined i $ switch bimap,[])) $ fromList [1..] splitStreams' bimap ((a,b):xs) = update fun pos $ splitStreams' bimap' xs where fun ~(_,bs) = (a,b:bs) sz = size bimap pos = findWithDefault (sz+1) a bimap bimap' = (if member a bimap then id else insert a (sz+1)) bimap Note that update actually generates fresh constructors, so the structure of our tails-Imp is not really static. But this is no problem as the form of the constructors is completely known: there is only one. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
On Thu, Sep 14, 2006 at 05:22:05PM +0200, Bertram Felgenhauer wrote: [much subtle code] We can now build the splitStream function, using the following helper function: splitSeq' :: Ord a = Map a () - [(a,b)] - ([(a,[b])], Map a [b]) This works for infinite lists if there is no balancing, but if insert does balancing, the top of the map will not be available until the last key is seen, so splitSeq' could only be used for finite chunks. Then you'll need a way to put the partial answers together. It might be possible to amortize the cost of that for an appropriate choice of chunk length. It would also cost some laziness: the chunked version would work for infinite lists, but wouldn't produce all the output for a partial list. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
On Sep 14, 2006, at 03:05 , Rohan Drape wrote: splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] [snip] Furthermore it should work on infinite lists. It can't eat the whole list before producing any output. This doesn't seem to make sense? Only at the end of the list can you know that you've collected all the events for each channel. If you output anything before scanning to the end, you'd not know if there were perhaps more events on that channel? It makes good sense. Each list will of events will be evaluated lazily, so thing will appear there as they appear in the input. I don't think you can do it in Haskell without some magic in the IO/ ST monad. In LML we had an array construction function that did almost exactly what the O.P. asked for. -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: evaluate vs seq
On Sep 14, 2006, at 16:20 , [EMAIL PROTECTED] wrote: Michael Shulman wrote: On 9/13/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: So `seq` forces its first argument. When we define f x = x `seq` (Return x) we thereby get f _|_== _|_ f [] == Return [] f (x:xs) == Return (x:xs) To compare, the semantics of (evaluate) is evaluate _|_== ThrowException =/= _|_ evaluate [] == Return [] evaluate (x:xs) == Return (x:xs) That should answer your question. I must not be phrasing my question very well; I feel like we're talking past each other. It seems to me that when writing actual programs (rather than reasoning about denotational semantics) the reason one would use `seq' or `evaluate' is to force something to be evaluated now rather than later, i.e. to get around Haskell's default lazy execution. Your semantics say that (x `seq` return x) and (evaluate x) have the same result when x is anything other than _|_. All well and good, but (return x) *also* has those same results when x is not _|_. Why would one use the former two rather than (return x), if x is known not to be _|_? Because they evaluate x at different times, right? Even though the eventual return value is the same, and thus the *semantics* are the same. So laying aside the formal semantics, what is the difference in terms of actual, real, Haskell programs? You are right, I completely forgot that executing a real Haskell program is a graph reduction and that `seq`'s purpose is to control this reduction and associated memory usage. But it's possible to use denotational semantics as an approximation to the actual graph reduction. No, you were right the first time. :) The denotational semantics is the important one. Haskell can be executed by other means than graph reduction. (That's why the report says a non-strict rather than lazy language.) Peculiar language constructs may allow you to tell the difference, but then they are highly dubious (and like all dubious things, they should be in the IO monad :) ). -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Bit string
Hi all, I'm doing some work with ASN.1, and I'm thinking about how to represent the type BIT STRING. The obvious, and inefficient representation would be type BitString = [Bool] A reasonable sparse representation might be type BitString = [Integer] where the integers represent the positions of the non-zero bits, but other implementations (e.g. C C++ based ones) mostly seem to use dense representations, and there are certain predictability advantages to be had by following existing implementations in this regard. But given that a value of type BIT STRING is allowed to have leading 0 bits, which have no semantic effect, another representation would be type BitString = [Word64] (I'm a modern type, and believe in 64bit computing ;-), but you could use Word32 if you liked). However, after a few moments' consideration, I realized, that if I was going to use a representation like that, I could probably use type BitString = Integer which already has [I assume] a carefully optimized implementation. Also, it ends up being significantly more strict than a list representation, which is probably a good thing in most situations. My question for all present is: Have I missed either a problem with using Integer, or have I overlooked a better representation? T. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit string
It's hard to tell what the best representation is if you don't know what the operations that you are going to perform are. If all you are going to do is I/O of bitstrings, then [Bool] could be great. If you need to do bitwise boolean ops then Integer is a wise choice. -- Lennart On Sep 14, 2006, at 21:35 , Thomas Conway wrote: Hi all, I'm doing some work with ASN.1, and I'm thinking about how to represent the type BIT STRING. The obvious, and inefficient representation would be type BitString = [Bool] A reasonable sparse representation might be type BitString = [Integer] where the integers represent the positions of the non-zero bits, but other implementations (e.g. C C++ based ones) mostly seem to use dense representations, and there are certain predictability advantages to be had by following existing implementations in this regard. But given that a value of type BIT STRING is allowed to have leading 0 bits, which have no semantic effect, another representation would be type BitString = [Word64] (I'm a modern type, and believe in 64bit computing ;-), but you could use Word32 if you liked). However, after a few moments' consideration, I realized, that if I was going to use a representation like that, I could probably use type BitString = Integer which already has [I assume] a carefully optimized implementation. Also, it ends up being significantly more strict than a list representation, which is probably a good thing in most situations. My question for all present is: Have I missed either a problem with using Integer, or have I overlooked a better representation? T. ___ 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] Bit string
On 9/15/06, Lennart Augustsson [EMAIL PROTECTED] wrote: It's hard to tell what the best representation is if you don't know what the operations that you are going to perform are. If all you are going to do is I/O of bitstrings, then [Bool] could be great. If you need to do bitwise boolean ops then Integer is a wise choice. And is I/O of bitstring represented as Integer going to be significantly worse [Bool]? It is certainly a much denser representation. Actually the main operations are probably tests (is a certain bit set), and encoding and decoding (to and from BER, PER, etc). The operations that need to be efficient are: -- test to see if the Nth bit is set testBit :: BitString - Integer - Bool -- set the Nth bit setBit :: BitString - Integer - BitString -- clear the Nth bit clearBit :: BitString - Integer - BitString I can see the potential for creating large intermediate Integers (i.e. 1 `shift` n), if the number of bits is large. T. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: evaluate vs seq
On 9/14/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: With this in mind the equations 1) return _|_ == Return _|_ 2) _|_ `seq` (return _|_) == _|_ can be interpreted: 1) when reducing a return-redex (i.e. evaluating it), we get weak-head normal form without evaluating the argument (which was _|_) 2) when reducing the `seq`-thing but not further evaluating the arguments (_|_ in our case), we get nowhere (i.e. only _|_) Thus, when evaluating the expressions (one step!, i.e. just to weak head normal form), number 1) returns immediately but in 2), the `seq` needs to evaluate its first argument. So the semantics of applying _|_ to a function determines its behavior with respect to how much of its arguments will be evaluated! I think this is the point our misunderstanding is about? For (evaluate :: a-IO a), I said something like 3) evaluate _|_== ThrowException and meant, that when evaluating 3) one step to weak head normal form, the argument does not get evaluated. 2) is much different to that. Equation 3) is of course wrong and must be more like evaluate x == Evaluate x where (Evaluate x) is a constructor but with a particular behavior when executed in the IO-Monad. Great, thank you! I think this finally answers my question. Mike ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Ross Paterson wrote: On Thu, Sep 14, 2006 at 05:22:05PM +0200, Bertram Felgenhauer wrote: [much subtle code] We can now build the splitStream function, using the following helper function: splitSeq' :: Ord a = Map a () - [(a,b)] - ([(a,[b])], Map a [b]) This works for infinite lists if there is no balancing, but if insert does balancing, the top of the map will not be available until the last key is seen, so splitSeq' could only be used for finite chunks. Then you'll need a way to put the partial answers together. Just to prove the point, here's the same code with balancing: SNIP HERE (end marked with ) module SplitSeq (splitSeq) where import Prelude hiding (lookup, map) -- our map data Map k a = Node !Int k a (Map k a) (Map k a) | Leaf deriving Show size :: Map k a - Int size Leaf = 0 size (Node s _ _ _ _) = s member :: Ord k = k - Map k a - Bool member _ Leaf = False member k (Node _ k' _ l r) = case compare k k' of LT - member k l EQ - True GT - member k r -- insert key into blueprint and extract the corresponding value from -- the second argument, threading it backward through all operations insert :: Ord k = k - Map k () - Map k a - (Map k (), a, Map k a) insert k Leaf~(Node _ _ a _ _) = (Node 1 k () Leaf Leaf, a, Leaf) insert k (Node s k' _ l r) node = case compare k k' of LT - let (m, a, l'') = insert k l l' (m', a', l', r') = balance k' m r node in (m', a, Node s k' a' l'' r') EQ - error inserting existing element GT - let (m, a, r'') = insert k r r' (m', a', l', r') = balance k' l m node in (m', a, Node s k' a' l' r'') -- balance and co are taken from Data.Map and adapted balance k l r node | size l + size r = 1 = let Node _ _ a l' r' = node in (mkNode k () l r, a, l', r') | size r = 5 * size l = rotateL k l r node | size l = 5 * size r = rotateR k l r node | otherwise= let Node _ _ a l' r' = node in (mkNode k () l r, a, l', r') rotateL k l r@(Node _ _ _ l' r') node | size l' 2*size r' = singleL k l r node | otherwise = doubleL k l r node rotateR k l@(Node _ _ _ l' r') r node | size r' 2*size l' = singleR k l r node | otherwise = doubleR k l r node singleL k l (Node s k' _ m r) ~(Node _ _ a ~(Node _ _ a' l' m') r') = (mkNode k' () (mkNode k () l m) r, a', l', Node s k' a m' r') singleR k (Node s k' _ l m) r ~(Node _ _ a l' ~(Node _ _ a' m' r')) = (mkNode k' () l (mkNode k () m r), a', Node s k' a l' m', r') doubleL k l (Node s k' _ (Node s' k'' _ ml mr) r) ~(Node _ _ a ~(Node _ _ a' l' ml') ~(Node _ _ a'' mr' r')) = (mkNode k'' () (mkNode k () l ml) (mkNode k' () mr r), a', l', Node s k' a'' (Node s' k'' a ml' mr') r') doubleR k (Node s k' _ l (Node s' k'' _ ml mr)) r ~(Node _ _ a ~(Node _ _ a' l' ml') ~(Node _ _ a'' mr' r')) = (mkNode k'' () (mkNode k' () l ml) (mkNode k () mr r), a'', Node s k' a' l' (Node s' k'' a ml' mr'), r') -- make a new node with the correct size mkNode k x l r = Node (size l + size r + 1) k x l r -- update the element associated with the given key update :: Ord k = k - (a - a) - Map k x - Map k a - Map k a update k f (Node s k' _ l r) ~(Node _ _ a' l' r') = case compare k k' of LT - Node s k' a' (update k f l l') r' EQ - Node s k' (f a') l' r' GT - Node s k' a' l' (update k f r r') -- standard map function, no blueprints here map :: (a - b) - Map k a - Map k b map _ Leaf = Leaf map f (Node s k a l r) = Node s k (f a) (map f l) (map f r) -- finally, define splitSeq splitSeq :: Ord a = [(a,b)] - [(a,[b])] splitSeq = fst . splitSeq' Leaf splitSeq' :: Ord a = Map a () - [(a,b)] - ([(a,[b])], Map a [b]) splitSeq' bp [] = ([], map (const []) bp) splitSeq' bp ((a,b):xs) = case member a bp of True - let (l, m) = splitSeq' bp xs in (l, update a (b:) bp m) False - let (bp', a', m) = insert a bp m' (l, m') = splitSeq' bp' xs in ((a, b : a') : l, m) The balancing code is adopted from Data.Map. I added threading back the result map (from splitSeq) to the balancing operations. This results in the promised O(n*log m) time. The cost associated with a lazy pattern (it creates a closure for each bound variable, IIRC) is quite high but constant, so each call to insert takes O(log m) time, including future forces of the lazy patterns. Likewise, member and update are also O(log m). Example test: Prelude SplitSeq print $ take 11 $ snd $ splitSeq ([(n `mod` 1, 'a') | n - [1..10]] ++ [(n, 'b') | n - [0..]]) !! 9534 aab (1.07 secs, 137026252 bytes) The nonbalancing version would take ages. regards, Bertram ___ Haskell-Cafe mailing
[Haskell-cafe] Anonymous types
Hi all, Is there any deep and meaningful reason why Haskell doesn't have anonymous discriminated union types? I'm thinking of an example like: data Amount = Amount Integer (Mg|G|Kg|T) Now this particular case is perhaps unconvincing - a seperate Units type would be quite sensible, however I'm thinking of translating ASN.1 definitions into Haskell. ASN.1 allows SEQUENCE (record types) and CHOICE (discriminated unions) as a kind of type constructor. Not having to invent names for anonymous SEQUENCE and CHOICE types would be nice. T. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Why is type 'b' forced to be type 'm a' and not possibly 'm a - m a'
Dear Haskell
Cafe,
I have a problem I can't get my head around.
The
code below sets the problem out. What I need to be able to do is commented
out.
This code works, the
only problem is that what I need is that an argument will be evaluated before it
is passed,
so ((and fries eats)
eggs) has a single `eggs`(fries1 eggs2 and3 eats4 egg2) not (fries1 eggs2
and3 eats4 eggs5).
The code that
doesn't work is commented out at the bottom. I'm not sure the
behaviour of ghc is correct, because
when
it typechecks it tries to unify `b = t t1`
but `b` could actually be `t t1 - t t1`.
I want to be able to
specify that when the first argument of `b` is of type `m a` that fork should
run it and _then_
fork the
argument to the first two arguments of 'fork'. The instance for (a - b) covers the rest of
the possibilities.
just type "run test[1-4]" to see
results.
\begin{code}
{-# OPTIONS_GHC -fglasgow-exts
-fno-monomorphism-restriction #-}
module Fork where
{-}
import Prelude hiding (and)
import Control.Monad.State
{-}
data NRef = NS0
String | NS1 String
NRef | NS2 String NRef
NRef
deriving(Show)
{-}
data UniqueS = US { nums :: [String]
} deriving(Show)
type USM a = StateT UniqueS IO a
newUniqueS :: UniqueSnewUniqueS = US { nums = [
show x | x - [1..] ] }
freshInstance :: String - USM
StringfreshInstance x =
do
(f:fs) - gets
nums
put $ US { nums = fs
}
return $ x ++ f
{-}
single x = do x' -
freshInstance x return $ NS0 x'
unary x n = do x' -
freshInstance x n' - n return $
NS1 x' n'
binary x n1 n2 = do x' -
freshInstance x n1' - n1 n2'
- n2 return $ NS2 x' n1' n2'
{-}
foxy = single "foxy"eggs = single
"eggs"golden = unary "golden"white = unary "white"fries = binary
"fries"eats = binary "eats"
{-}
class Forkable a where fork
:: String - a - a - a
instance (Forkable a, Forkable b) = Forkable (a
- b) where fork n a1 a2 a = fork n (a1 a) (a2
a)
{-instance (Monad m, Forkable (m a),
Forkable b) = Forkable (m a - b) where fork n a1
a2 a =
do
a' -
a
fork n (a1$ return a')
(a2$ return
a')-}{-}
instance Forkable (USM NRef)
where fork n a1 a2 =
do
a1' -
a1
a2' -
a2
return $ NS2 n a1' a2'
{-}
and = fork "and"
test1 = (and foxy eggs)test2 = (and golden
white) eggstest3 = (and fries eats) foxy eggstest4 = (eats foxy (and
(golden eggs) (white eggs)))
run x = runStateT x newUniqueS =
(putStrLn . show . fst)\end{code
--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.405 / Virus Database: 268.12.4/448 - Release Date: 14/09/2006
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit string
On Fri, Sep 15, 2006 at 11:35:45AM +1000, Thomas Conway wrote: My question for all present is: Have I missed either a problem with using Integer, or have I overlooked a better representation? Consider also (UArray Int Bool). In GHC it has an efficient implementation. Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
