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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

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_fo... 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 --

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

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

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

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 allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

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

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