Documenting strictness properties for Data.Map.Strict

[Johan Tibell-2]

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

[Johan Tibell-2]

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

[Ivan Lazar Miljenovic]

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

[Evan Laforge]

> 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

[Roman Cheplyaka-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

[Roman Leshchinskiy]

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

[Bas van Dijk-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

[Twan van Laarhoven]

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

[Johan Tibell-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

[Johan Tibell-2]

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

[Johan Tibell-2]

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

[Johan Tibell-2]

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

[Roman Cheplyaka-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

[Brandon Allbery]

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

--
brandon s allbery                                      [hidden email]
wandering unix systems administrator (available)     [phone] vm/sms

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Roman Cheplyaka-2]

* 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

[Johan Tibell-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

[Henk-Jan van Tuyl]

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