Hi all,
Data.Map is getting split into Data.Map.Lazy and Data.Map.Strict (with Data.Map re-exporting the lazy API). I want to better document the strictness properties of the two new modules. Right now the documentation for Data.Map.Strict reads: Strictness properties ===================== * All functions are strict in both key and value arguments. Examples: insertWith (+) k undefined m == undefined delete undefined m == undefined * Keys and values are evaluated to WHNF before they are stored in the map. Examples: map (\ v -> undefined) == undefined mapKeys (\ k -> undefined) == undefined I'm not entirely happy with this formulation. I'm looking for something that's clear (i.e. precise and concise, without leaving out important information), assuming that the reader already knows how lazy evaluation works at a high level. Ideas? Cheers, Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell <[hidden email]> wrote:
> I'm not entirely happy with this formulation. I'm looking for > something that's clear (i.e. precise and concise, without leaving out > important information), assuming that the reader already knows how > lazy evaluation works at a high level. > > Ideas? This reads a bit better to me: Strictness properties ===================== This module is strict in keys and values. In particular, * key and value function arguments passed to functions are evaluated to WHNF before the function body is evaluated, and * keys and values returned by high-order function arguments are evaluated to WHNF before they are inserted into the map. Here are some examples: insertWith (+) k undefined m == undefined delete undefined m == undefined map (\ v -> undefined) == undefined mapKeys (\ k -> undefined) == undefined Any ideas for further improvements? -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 18 November 2011 16:44, Johan Tibell <[hidden email]> wrote:
> On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell <[hidden email]> wrote: >> I'm not entirely happy with this formulation. I'm looking for >> something that's clear (i.e. precise and concise, without leaving out >> important information), assuming that the reader already knows how >> lazy evaluation works at a high level. >> >> Ideas? > > This reads a bit better to me: > > Strictness properties > ===================== > > This module is strict in keys and values. In particular, > > * key and value function arguments passed to functions are > evaluated to WHNF before the function body is evaluated, and > > * keys and values returned by high-order function arguments are > evaluated to WHNF before they are inserted into the map. > > Here are some examples: > > insertWith (+) k undefined m == undefined > delete undefined m == undefined > map (\ v -> undefined) == undefined > mapKeys (\ k -> undefined) == undefined > > Any ideas for further improvements? I think this is rather clear and to the point, maybe just re-word "key and value function arguments passed to functions ..." (maybe just "key and value arguments" ?) -- Ivan Lazar Miljenovic [hidden email] IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
> Any ideas for further improvements?
I feel like there should be a canonical "what is WHNF" page on haskell.org that docs like this can link to. Namely, what it is theoretically, what that means for various examples of thunks (i.e. show how a sample graph would get reduced), and what that means for programs (e.g. this builds up thunks, this doesn't). All this info is certainly available, but it seems to not be as easy as it should be to find, e.g. http://haskell.org/haskellwiki/Lazy_vs._non-strict says "described WHNF..." and, well, http://en.wikibooks.org/wiki/Haskell/Laziness#Thunks_and_Weak_head_normal_form is pretty good actually. Maybe the haskellwiki page should just link to that. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
* Johan Tibell <[hidden email]> [2011-11-17 21:21:47-0800]
> Hi all, > > Data.Map is getting split into Data.Map.Lazy and Data.Map.Strict (with > Data.Map re-exporting the lazy API). I want to better document the > strictness properties of the two new modules. Right now the > documentation for Data.Map.Strict reads: > > Strictness properties > ===================== > > * All functions are strict in both key and value arguments. Examples: > > insertWith (+) k undefined m == undefined > delete undefined m == undefined > > * Keys and values are evaluated to WHNF before they are stored in the > map. Examples: > > map (\ v -> undefined) == undefined > mapKeys (\ k -> undefined) == undefined Is it mentioned anywhere that Map is spine-strict? An important property, although may be non-trivial to formulate while keeping the implementation abstract. -- Roman I. Cheplyaka :: http://ro-che.info/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
Johan Tibell wrote:
> > map (\ v -> undefined) == undefined > mapKeys (\ k -> undefined) == undefined Not really related to the question but I don't really understand how these properties can possibly hold. Shouldn't it be: map (\v -> undefined) x = undefined And even then, does this really hold for empty maps? Roman _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
On 18 November 2011 06:44, Johan Tibell <[hidden email]> wrote:
> Here are some examples: > > insertWith (+) k undefined m == undefined > delete undefined m == undefined > map (\ v -> undefined) == undefined > mapKeys (\ k -> undefined) == undefined > > Any ideas for further improvements? I would use '_|_' instead of 'undefined'. Then again, this does require the reader to know what '_|_' means. But note we already use this symbol in the base library. Bas _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
On 18/11/11 06:44, Johan Tibell wrote:
> On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell<[hidden email]> wrote: >> I'm not entirely happy with this formulation. I'm looking for >> something that's clear (i.e. precise and concise, without leaving out >> important information), assuming that the reader already knows how >> lazy evaluation works at a high level. >> >> Ideas? > > This reads a bit better to me: I actually much prefer the original formulation. In particular, you should keep examples together with the rules they illustrate. > * key and value function arguments passed to functions are > evaluated to WHNF before the function body is evaluated, and "function arguments passed to functions" sounds a bit redundant. Either say "arguments passed to functions" or "function arguments". Also "before the function body is evaluated" says something about evaluation order, does that really matter for strictness? * All key and value arguments passed to functions are evaluated to WHNF before the function body is evaluated > * keys and values returned by high-order function arguments are > evaluated to WHNF before they are inserted into the map. Keys and values not returned by higher order functions, but passed in directly are also evaluated to WHNF (per the first rule), so that qualification is unnecessary. Just say: * keys and values are evaluated to WHNF before they are inserted into the map. I also think 'stored' is better here than 'inserted', because the latter might give the impression that it only applies to the insert function, and not to things like map. > insertWith (+) k undefined m == undefined > etc. As Roman suggested, use = here instead of ==. To really illustrate the first rule, insertWith (+) is not enough, you would really need a function that doesn't use the value, so insertWith (\new old -> old) k undefined m = undefined But that is just nitpicking. Twan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roman Cheplyaka-2
On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <[hidden email]> wrote:
> Is it mentioned anywhere that Map is spine-strict? It's not and we should probably mention it. I was mulling this over last night. My initial thought was that it shouldn't matter as long as the algorithmic complexity of the functions is maintained. But it is important in that a lookup following an insert might do all the work of the insert, which is somewhat surprising (and inefficient). > An important property, although may be non-trivial to formulate while > keeping the implementation abstract. Perhaps we could talk about the presence or absence of thunks of a Map that's in WHNF? -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roman Leshchinskiy
On Fri, Nov 18, 2011 at 1:58 AM, Roman Leshchinskiy <[hidden email]> wrote:
> Johan Tibell wrote: >> >> map (\ v -> undefined) == undefined >> mapKeys (\ k -> undefined) == undefined > > Not really related to the question but I don't really understand how these > properties can possibly hold. Shouldn't it be: > > map (\v -> undefined) x = undefined > > And even then, does this really hold for empty maps? It doesn't hold. It needs the side condition that the map is initially empty. I wonder if there's any function in the API that'd let me express this property (of HOFs) that doesn't require a side condition. I don't think so e.g. insertWith (\old new -> undefined) k v m has a side condition that k is in the map. -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Twan van Laarhoven
On Fri, Nov 18, 2011 at 5:02 AM, Twan van Laarhoven <[hidden email]> wrote:
>> * key and value function arguments passed to functions are >> evaluated to WHNF before the function body is evaluated, and > > "function arguments passed to functions" sounds a bit redundant. Either say > "arguments passed to functions" or "function arguments". Also "before the > function body is evaluated" says something about evaluation order, does that > really matter for strictness? It is a bit redundant. I will remove it. >> * keys and values returned by high-order function arguments are >> evaluated to WHNF before they are inserted into the map. > > Keys and values not returned by higher order functions, but passed in > directly are also evaluated to WHNF (per the first rule), so that > qualification is unnecessary. Just say: > > * keys and values are evaluated to WHNF before they are > inserted into the map. I don't think we have any higher-order functions that don't store evaluated keys/values in the map so this should be equivalent. Without the part about higher-order functions it's not quite clear why this second property is needed and that's why I included it to begin with. Perhaps I should instead clarify that particular part with an example. > I also think 'stored' is better here than 'inserted', because the latter > might give the impression that it only applies to the insert function, and > not to things like map. 'stored' is a bit more clear, I agree. >> insertWith (+) k undefined m == undefined > >> etc. > > As Roman suggested, use = here instead of ==. I was trying to be consistent with e.g. Control.Functor etc, which use == and two surrounding spaces. I think it's good, as it avoids confusion with function declarations. > To really illustrate the first rule, insertWith (+) is not enough, you would > really need a function that doesn't use the value, so > > insertWith (\new old -> old) k undefined m = undefined > > But that is just nitpicking. My example is enough, but I forgot to include the side condition that k is in the map. You're example is a bit better in that it doesn't require that side condition. -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Here's an attempt at an improved version:
Strictness properties ===================== This module satisfies the following properties: 1. Key and value arguments are evaluated to WHNF; 2. Keys and values are evaluated to WHNF before they are stored in the map. Here are some examples that illustrate the first property: insertWith (\ old new -> old) k undefined m == undefined delete undefined m == undefined Here are some examples that illustrate the second property: map (\ v -> undefined) m == undefined -- m is not empty mapKeys (\ k -> undefined) m == undefined -- m is not empty What do you think? -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Johan Tibell-2
* Johan Tibell <[hidden email]> [2011-11-18 08:06:29-0800]
> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <[hidden email]> wrote: > > Is it mentioned anywhere that Map is spine-strict? > > It's not and we should probably mention it. Hm. Perhaps I'm missing something, but data Map k a = Tip | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) looks pretty (spine-)strict to me. (This is in the latest rev from http://github.com/haskell/containers.git) > I was mulling this over last night. My initial thought was that it > shouldn't matter as long as the algorithmic complexity of the > functions is maintained. But it is important in that a lookup > following an insert might do all the work of the insert, which is > somewhat surprising (and inefficient). It's also space and "stack" complexities that matter (not sure if you include those in algorithmic complexity). For example, if it's not spine-strict, then Map.lookup k $ foldl' Map.union Map.empty longList would overflow the stack despite the prime in foldl'. -- Roman I. Cheplyaka :: http://ro-che.info/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka <[hidden email]> wrote:
* Johan Tibell <[hidden email]> [2011-11-18 08:06:29-0800] Parser failure on your part; "it's not" refers to "mentioned", not "spine-strict". Admittedly, figuring this out requires the rest of the sentence to provide what isn't even an explicit context. (Ah, English.)
brandon s allbery [hidden email] wandering unix systems administrator (available) (412) 475-9364 vm/sms _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
* Brandon Allbery <[hidden email]> [2011-11-18 12:20:33-0500]
> On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka <[hidden email]> wrote: > > > * Johan Tibell <[hidden email]> [2011-11-18 08:06:29-0800] > > > On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <[hidden email]> > > wrote: > > > > Is it mentioned anywhere that Map is spine-strict? > > > It's not and we should probably mention it. > > > > looks pretty (spine-)strict to me. > > > > Parser failure on your part; "it's not" refers to "mentioned", not > "spine-strict". Admittedly, figuring this out requires the rest of the > sentence to provide what isn't even an explicit context. (Ah, English.) Ah! I see :-) -- Roman I. Cheplyaka :: http://ro-che.info/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roman Cheplyaka-2
On Fri, Nov 18, 2011 at 9:16 AM, Roman Cheplyaka <[hidden email]> wrote:
> * Johan Tibell <[hidden email]> [2011-11-18 08:06:29-0800] >> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <[hidden email]> wrote: >> > Is it mentioned anywhere that Map is spine-strict? >> >> It's not and we should probably mention it. > > Hm. Perhaps I'm missing something, but > > data Map k a = Tip > | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) > > looks pretty (spine-)strict to me. > (This is in the latest rev from http://github.com/haskell/containers.git) "it's not" as in "it's not documented". > It's also space and "stack" complexities that matter (not sure if you > include those in algorithmic complexity). > > For example, if it's not spine-strict, then > > Map.lookup k $ foldl' Map.union Map.empty longList > > would overflow the stack despite the prime in foldl'. Good point. I will mull this over. -- Johan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Evan Laforge
On Fri, 18 Nov 2011 06:58:41 +0100, Evan Laforge <[hidden email]> wrote:
>> Any ideas for further improvements? > > I feel like there should be a canonical "what is WHNF" page on > haskell.org that docs like this can link to. Namely, what it is > theoretically, what that means for various examples of thunks (i.e. > show how a sample graph would get reduced), and what that means for > programs (e.g. this builds up thunks, this doesn't). > > All this info is certainly available, but it seems to not be as easy > as it should be to find, e.g. > http://haskell.org/haskellwiki/Lazy_vs._non-strict says "described > WHNF..." and, well, > http://en.wikibooks.org/wiki/Haskell/Laziness#Thunks_and_Weak_head_normal_form > is pretty good actually. Maybe the haskellwiki page should just link > to that. I created a page with the title "Weak head normal form"[0] and a redirect from WHNF to this page. Regards, Henk-Jan van Tuyl [0] http://www.haskell.org/haskellwiki/Weak_head_normal_form -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html -- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |