Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, 18 Nov 2011 06:58:41 +0100, Evan Laforge 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, Nov 18, 2011 at 9:16 AM, Roman Cheplyaka wrote:
> * Johan Tibell [2011-11-18 08:06:29-0800]
>> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
* Brandon Allbery [2011-11-18 12:20:33-0500] > On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka wrote: > > > * Johan Tibell [2011-11-18 08:06:29-0800] > > > On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka > > 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka wrote: > * Johan Tibell [2011-11-18 08:06:29-0800] > > On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka > 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.) -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
* Johan Tibell [2011-11-18 08:06:29-0800]
> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, Nov 18, 2011 at 5:02 AM, Twan van Laarhoven 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, Nov 18, 2011 at 1:58 AM, Roman Leshchinskiy 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On 18/11/11 06:44, Johan Tibell wrote: On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On 18 November 2011 06:44, Johan Tibell 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
* Johan Tibell [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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
> 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On 18 November 2011 16:44, Johan Tibell wrote: > On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell 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 ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibell 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Documenting strictness properties for Data.Map.Strict
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
