Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
On Fri, 2012-02-24 at 07:49 +0100, Jos Pedro Magalhes wrote: Hi, 2012/2/23 Maxime Henrion mhenr...@gmail.com * Why do you have the instance: instance GDeepSeq V1 where grnf _ = () The only way to construct values of a void type is using ⊥. And I would expect that rnf ⊥ = ⊥, not (). I think the best thing is to just remove the V1 instance. This would have the consequence that any type tagged with a phantom type (for whatever reason) couldn't be used with deepseq, it would return bottom. What if I want to deepseq a 2-3 finger tree tagged with a type-level natural that ensures the proper shape of the tree statically? It seemed to me that I should be able to do that; this is why I added this V1 instance. I'm not sure I understand your comment... V1 should only be used for datatypes without constructors, such as `data Empty`. Yes, such as the usual type-level naturals (not using DataKinds): data Z data S n Those can be used to tag a type which also contains actual values that you would want to deepseq? For example, a length-type vector? I seemed to remember a similar construct for 2-3 finger trees that would statically guarantee that the shape of the tree is valid, so I took that as an example, but I don't remember the specifics. Cheers, Maxime signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
2012/2/24 Maxime Henrion mhenr...@gmail.com On Fri, 2012-02-24 at 07:49 +0100, Jos Pedro Magalhes wrote: Hi, 2012/2/23 Maxime Henrion mhenr...@gmail.com * Why do you have the instance: instance GDeepSeq V1 where grnf _ = () The only way to construct values of a void type is using ⊥. And I would expect that rnf ⊥ = ⊥, not (). I think the best thing is to just remove the V1 instance. This would have the consequence that any type tagged with a phantom type (for whatever reason) couldn't be used with deepseq, it would return bottom. What if I want to deepseq a 2-3 finger tree tagged with a type-level natural that ensures the proper shape of the tree statically? It seemed to me that I should be able to do that; this is why I added this V1 instance. I'm not sure I understand your comment... V1 should only be used for datatypes without constructors, such as `data Empty`. Yes, such as the usual type-level naturals (not using DataKinds): data Z data S n Those can be used to tag a type which also contains actual values that you would want to deepseq? For example, a length-type vector? But in those cases they are used as tags, not as values, and hence do not show up in the generic representation. So if all you want is to be able to deepseq a value of a type like data Proxy t = Proxy even if your value is of type `Proxy Ze`, you shouldn't need a `V1` instance. Cheers, Pedro ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.IntMap union complexity
2012/2/24 Clark Gaebel cgae...@csclub.uwaterloo.ca: Since insertion [2] is O(min(n, W)) [ where W is the number of bits in an Int ], wouldn't it be more efficient to just fold 'insert' over one of the lists for a complexity of O(m*min(n, W))? This would degrade into O(m) in the worst case, as opposed to the current O(n+m). Or am I just crazy? This way you will create much more garbage, I think. The union of two completely disjoint maps can hold parts of them intact. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.IntMap union complexity
Folding insert might still be a win if one of the maps is very much smaller than the other, but since size is O(n) for Data.IntMap, there's no way to find out if that's the case. - chris On Fri, Feb 24, 2012 at 4:48 AM, wren ng thornton w...@freegeek.org wrote: When the two maps are of vastly different sizes, O(min(m,n)) is a more intuitive way to think about it. Since you only have to look at the places where the spines clash, that will be on the order of the smaller map. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
On Fri, 2012-02-24 at 09:32 +0100, Jos Pedro Magalhes wrote: 2012/2/24 Maxime Henrion mhenr...@gmail.com On Fri, 2012-02-24 at 07:49 +0100, Jos Pedro Magalhes wrote: Hi, 2012/2/23 Maxime Henrion mhenr...@gmail.com * Why do you have the instance: instance GDeepSeq V1 where grnf _ = () The only way to construct values of a void type is using ⊥. And I would expect that rnf ⊥ = ⊥, not (). I think the best thing is to just remove the V1 instance. This would have the consequence that any type tagged with a phantom type (for whatever reason) couldn't be used with deepseq, it would return bottom. What if I want to deepseq a 2-3 finger tree tagged with a type-level natural that ensures the proper shape of the tree statically? It seemed to me that I should be able to do that; this is why I added this V1 instance. I'm not sure I understand your comment... V1 should only be used for datatypes without constructors, such as `data Empty`. Yes, such as the usual type-level naturals (not using DataKinds): data Z data S n Those can be used to tag a type which also contains actual values that you would want to deepseq? For example, a length-type vector? But in those cases they are used as tags, not as values, and hence do not show up in the generic representation. So if all you want is to be able to deepseq a value of a type like data Proxy t = Proxy even if your value is of type `Proxy Ze`, you shouldn't need a `V1` instance. Oh, ok; in that case, I probably don't need that V1 instance indeed. I should probably write QuickCheck tests using the ChasingBottoms package in order to ensure correct behaviour of this code. Thanks, Maxime signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
I don't understand what's going on here. Instances for V1 should of course be defined if they can be! And in this case, a V1 instance makes sense and should be defined. The definition itself doesn't matter, as it'll never be executed. Cheers, Andres ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
Hi Andres, 2012/2/24 Andres Löh andres.l...@googlemail.com I don't understand what's going on here. Instances for V1 should of course be defined if they can be! And in this case, a V1 instance makes sense and should be defined. The definition itself doesn't matter, as it'll never be executed. The definition certainly matters: data Ze deriving Generic class DeepSeq a where rnf :: a - () default rnf :: (Generic a, GDeepSeq (Rep a)) = a - () rnf = grnf . from instance DeepSeq Ze class GDeepSeq f where grnf :: f a - () instance GDeepSeq V1 where grnf _ = () instance GDeepSeq a = GDeepSeq (M1 i c a) where grnf = grnf . unM1 -- other instances are not relevant now t :: Ze t = undefined seq t () == undefined. rnf t == (), because the V1 instance dictates so. Cheers, Pedro ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
Hi. I don't understand what's going on here. Instances for V1 should of course be defined if they can be! And in this case, a V1 instance makes sense and should be defined. The definition itself doesn't matter, as it'll never be executed. The definition certainly matters: [...] You're right. I was too quick to conclude the definition doesn't matter. But it should still be there. V1 can occur in representations of non-empty types (even if the current mechanism might not generate them). You'd still want to be able to call generic functions on such types. Cheers, Andres ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] SURVEY: hledger, shelltestrunner, rss2irc, FunGEn usage 2012
As promised, here are the (live-updating) results. The surveys will remain open, keep em coming... hledger: Details: https://docs.google.com/spreadsheet/ccc?key=0Au47MrJax8HpdHVGUHBXRUhRNWF3Y2RsZGVHNmlFLWc#gid=3 Summary: https://docs.google.com/spreadsheet/gform?key=0Au47MrJax8HpdHVGUHBXRUhRNWF3Y2RsZGVHNmlFLWcgridId=3#chart (summary requires login) shelltestrunner: Details: https://docs.google.com/spreadsheet/ccc?key=0Au47MrJax8HpdGpZSzdhWHlCUkJpR2hjX1MwMWFoUEE#gid=3 Summary: https://docs.google.com/spreadsheet/gform?key=0Au47MrJax8HpdGpZSzdhWHlCUkJpR2hjX1MwMWFoUEEgridId=3#chart rss2irc ( hackagebot): Details: https://docs.google.com/spreadsheet/ccc?key=0Au47MrJax8HpdFhhLWZrZ3l4elFYa3M1ZmFxWDViYlEpli=1#gid=3 Summary: https://docs.google.com/spreadsheet/gform?key=0Au47MrJax8HpdFhhLWZrZ3l4elFYa3M1ZmFxWDViYlEgridId=3#chart FunGEn: Details: https://docs.google.com/spreadsheet/ccc?key=0Au47MrJax8HpdFN5dllFTGFFU3ZhclcxWTZFNEludlEpli=1#gid=3 Summary: https://docs.google.com/spreadsheet/gform?key=0Au47MrJax8HpdFN5dllFTGFFU3ZhclcxWTZFNEludlEgridId=3#chart Thanks for the excellent feedback. -Simon On Feb 23, 2012, at 7:13 PM, Simon Michael wrote: Hey all, I'm gathering usage data on my main FOSS projects, to help me prioritize and steer them. I've prepared a short survey, 10 optional questions that should take 1-5 minutes per project. If you use any of these projects and/or would like them to continue, you can help a lot by adding your experience to: hledger: https://docs.google.com/spreadsheet/viewform?formkey=dHVGUHBXRUhRNWF3Y2RsZGVHNmlFLWc6MA#gid=3 shelltestrunner: https://docs.google.com/spreadsheet/viewform?formkey=dGpZSzdhWHlCUkJpR2hjX1MwMWFoUEE6MA#gid=3 rss2irc ( hackagebot): https://docs.google.com/spreadsheet/viewform?formkey=dFhhLWZrZ3l4elFYa3M1ZmFxWDViYlE6MA#gid=3 FunGEn: https://docs.google.com/spreadsheet/viewform?formkey=dFN5dllFTGFFU3ZhclcxWTZFNEludlE6MA#gid=3 Don't hold back! Honest critique welcome. You'll see a summary report after submitting your answers, and before long I'll follow up with the urls for full results. Note that contact info will be public, except that I'll keep email addresses private. It's optional but at least a little is quite useful in several ways. I made the survey generic, so feel free to re-use it. Best, -Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Using multiplate to get free variables from a syntax tree
On Thu, Feb 23, 2012 at 01:18:22PM -0800, Matt Brown wrote: Hi all, I'm reading the haskellwiki article on multiplate. Is it possible to modify the getVariablesPlate example to return the free variables? One idea I had is to store an environment in a reader monad, and use local to update the environment at a let expression. Couldn't figure it out, though. Any ideas? Hi Matt, I am not very familiar with Multiplate, but from what I can see it doesn't seem like this will work. The code for traversing Let looks like Let $ decl child d * expr child e The call to 'decl child d' can certainly have some sort of side-effects which can influence the processing of e -- but intuitively it seems to me there is no way to *localize* the effects only to e; it will also affect everything processed afterwards. If you really do want to compute free variables (not just test the limits of Multiplate), you may be interested in taking a look at Unbound: http://hackage.haskell.org/package/unbound -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Using multiplate to get free variables from a syntax tree
I'm not familiar with Multiplate either, but presumably you can descend into the decl - collect the bound vars, then descend into the body expr. Let $ decl child d * expr child e This seems like a common traversal that Strafunski would handle, and with Multiplate being a competitor / successor to Strafunski it should be able to do it too. Naturally you would need a monadic traversal rather than an applicative one... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
On Fri, 2012-02-24 at 15:28 +0100, Andres Löh wrote: Hi. I don't understand what's going on here. Instances for V1 should of course be defined if they can be! And in this case, a V1 instance makes sense and should be defined. The definition itself doesn't matter, as it'll never be executed. The definition certainly matters: [...] You're right. I was too quick to conclude the definition doesn't matter. But it should still be there. V1 can occur in representations of non-empty types (even if the current mechanism might not generate them). You'd still want to be able to call generic functions on such types. Would you have an example of a type for which it would be useful to have a DeepSeq instance, and that would require a V1 instance? I cannot think of one now; I originaly thought it would be necessary to permit deriving DeepSeq instances for types tagged with void types, but as José explained, in that case, the V1 instance isn't needed because those void types don't show up in the representation. Cheers, Maxime signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: generic-deepseq 1.0.0.0
On Thu, 2012-02-23 at 23:24 +0100, Bas van Dijk wrote: Some nitpicking: * In the instance: instance GDeepSeq U1 where grnf _ = () I think it makes sense to pattern match on the U1 constructor, as in: grnf U1 = (). I haven't checked if that's necessary but my fear is that assuming: data Unit = Unit deriving Generic; instance DeepSeq Unit rnf (⊥ :: Unit) would equal: () while I would expect it to equal ⊥. I just tested this and you were right; I have corrected the code in the mercurial repository. * Why do you have the instance: instance GDeepSeq V1 where grnf _ = () The only way to construct values of a void type is using ⊥. And I would expect that rnf ⊥ = ⊥, not (). I think the best thing is to just remove the V1 instance. I have confirmed what Jos explained, and V1 instances are indeed not necessary for the use case I originally intended them for, that is for types tagged with void types. I have removed the V1 instance for now. Thanks, Maxime signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.IntMap union complexity
I've wondered if it's faster to insert many keys by successive insertion, or by building another map and then unioning, and likewise with deletion. I eventually decided on successive, thinking a log n build + merge is going to be slower than a m*log n for successive insertion. So I wound up with: insert_list :: (Ord k) = [(k, v)] - Map.Map k v - Map.Map k v insert_list kvs m = List.foldl' (\m (k, v) - Map.insert k v m) m kvs delete_keys :: (Ord k) = [k] - Map.Map k a - Map.Map k a delete_keys keys fm = Map.difference fm (Map.fromList [(k, ()) | k - keys]) Oops, I guess I changed my mind by the time I got to writing 'delete_keys' :) But if the list of things to insert or delete is already sorted, then you could take advantage of fromListAsc and maybe a union would save some time? On Fri, Feb 24, 2012 at 12:38 AM, Serguey Zefirov sergu...@gmail.com wrote: 2012/2/24 Clark Gaebel cgae...@csclub.uwaterloo.ca: Since insertion [2] is O(min(n, W)) [ where W is the number of bits in an Int ], wouldn't it be more efficient to just fold 'insert' over one of the lists for a complexity of O(m*min(n, W))? This would degrade into O(m) in the worst case, as opposed to the current O(n+m). Or am I just crazy? This way you will create much more garbage, I think. The union of two completely disjoint maps can hold parts of them intact. ___ 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