Re: [Haskell-cafe] Superset of Haddock and Markdown
* Johan Tibell johan.tib...@gmail.com [2011-11-17 21:09:15-0800] Hi all, I spent some time today documenting a library and the experience left me wanting a better markup language. In particular, Haddock lacks: * markup for bold text: bold text works better than italics for emphasis on computer monitors. * hyperlinks with anchor texts: having the actual URL rendered inline with text hurts readability. Could Haddock markup be extended to also include some Markdown features? The new features could be hidden behind a flag so old documentation doesn't get unwanted markup (e.g. if it uses *...* to not mean bold). P.S. This good make a good weekend hack that shouldn't be too difficult. Sounds awesome! Maybe have a switch that enables markdown and disables markup-related features of haddock (everything except linking to identifiers/modules, I believe), so that we don't affect existing docs. Then make it possible to pass this flag through cabal. -- 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
* Johan Tibell johan.tib...@gmail.com [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] Superset of Haddock and Markdown
On 18 November 2011 19:06, Roman Cheplyaka r...@ro-che.info wrote: Maybe have a switch that enables markdown and disables markup-related features of haddock (everything except linking to identifiers/modules, I believe), so that we don't affect existing docs. Then make it possible to pass this flag through cabal. As in have an opt-in Cabal field? -- 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] Superset of Haddock and Markdown
Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: Wasn't there talk at one stage of integrating pandoc into haddock? I wouldn't mind Haddock depending on Pandoc, at least optionally (-fmarkdown-comments). Taking this to its conclusion you could easily have syntax-highlighted code examples in Haddock documentations and allow alternative output formats. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife = sex) http://ertes.de/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [ANN] transformers-base, transformers-abort, monad-abort-fd
Felipe Almeida Lessa felipe.le...@gmail.com writes: It's funny how we, haskellers, find 'm' and 'b' descriptive names. I know many programmers who would cry after seeing this =). It takes a bit of practice to get used to, but then they really are descriptive. The trick is to keep the number of entities - parameters, types, etc low enough to keep mental track. To me, LongAndVeryDescripteNames is a code smell: your code is too complicated. Let them cry, I say! -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A Mascot
John Meacham j...@repetae.net writes: People tend to concentrate on the lambda which cooresponds to the functional aspect of haskell when designing logos. Not nearly enough attention is paid to the other striking feature, the What about types? This is a distinguishing feature from many of the other lambda-users out there, isn't \lambda_\tau used to signify that? -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Stream fusion
Hello, While re-reading RealWorldHaskell, chapter 25, I saw that -- unlike I believed -- loop fusion wasn't activated by default under GHC for lists (but that module Data.List.Stream from package stream-fusion could provide it). Is that still the case? If not, then are there some cases of list processing where loop fusion would be a bad thing? (Ergo cases where you should stick to Prelude/Data.List functions and not use Data.List.Stream implementation) Thanks. ___ 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] ST not strict enough?
Instead of rewriting modifySTRef, why not just do : modifySTRef counter (\x - let y = x+1 in y `seq` y) Is there a problem with that? 2011/11/16 Johan Tibell johan.tib...@gmail.com On Wed, Nov 16, 2011 at 11:58 AM, Jason Dusek jason.du...@gmail.comwrote: diff --git a/Rebuild.hs b/Rebuild.hs @@ -15,6 +15,7 @@ import Data.STRef import Data.String import Data.Word +import Control.DeepSeq import Data.Vector.Unboxed (Vector) import qualified Data.Vector.Unboxed as Vector (create, length) import qualified Data.Vector.Unboxed.Mutable as Vector hiding (length) @@ -46,8 +47,8 @@ rebuildAsVector bytes= byteVector n - readSTRef counter return (Vector.unsafeSlice 0 n v) writeOneByte v counter b = do n - readSTRef counter - Vector.unsafeWrite v n b + w v n b modifySTRef counter (+!1) + (+!) a b = ((+) $!! a) $!! b + w v n b = (Vector.unsafeWrite v $!! n) $!! b +! doesn't work unless modifySTRef is already strict in the result of the function application. You need to write modifySTRef' that seq:s the result of the function application before calling writeSTRef. -- Johan ___ 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
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On 18 November 2011 06:44, Johan Tibell johan.tib...@gmail.com 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] ST not strict enough?
On Friday 18 November 2011, 11:18:33, Yves Parès wrote: Instead of rewriting modifySTRef, why not just do : modifySTRef counter (\x - let y = x+1 in y `seq` y) Is there a problem with that? Yes, y `seq` y is precisely the same as y. a `seq` b means whenever evaluation of b is demanded, also evaluate a (to WHNF). So y `seq` y ~ whenever evaluation of y is demanded, also evaluate y. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ST not strict enough?
Okay, thanks I was pretty sure I was wrong (or else somebody would already have come up with that solution), but I wanted to know why. 2011/11/18 Daniel Fischer daniel.is.fisc...@googlemail.com On Friday 18 November 2011, 11:18:33, Yves Parès wrote: Instead of rewriting modifySTRef, why not just do : modifySTRef counter (\x - let y = x+1 in y `seq` y) Is there a problem with that? Yes, y `seq` y is precisely the same as y. a `seq` b means whenever evaluation of b is demanded, also evaluate a (to WHNF). So y `seq` y ~ whenever evaluation of y is demanded, also evaluate y. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ST not strict enough?
(Sorry for the double mail) ...so there is no way to do that inside the function passed to modifySTRef? In other words, there is no way to ensure *inside* a function that its result will be evaluated strictly? 2011/11/18 Daniel Fischer daniel.is.fisc...@googlemail.com On Friday 18 November 2011, 11:18:33, Yves Parès wrote: Instead of rewriting modifySTRef, why not just do : modifySTRef counter (\x - let y = x+1 in y `seq` y) Is there a problem with that? Yes, y `seq` y is precisely the same as y. a `seq` b means whenever evaluation of b is demanded, also evaluate a (to WHNF). So y `seq` y ~ whenever evaluation of y is demanded, also evaluate y. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A Mascot
Apart from the whole big discussion about an official mascot for Haskell, I for one am SURELY adopting Da, the Lamb from now on on my desktop background and on the lid of my laptop! :D I think some cute animal to connect with is something nice to us, as a community :) Could you imagine Linux without Tux?! Now I cannot imagine Haskell without the Lamb Da. João Paulo Pizani Flor joaopiz...@gmail.com Computer Science Federal University of Santa Catarina - Brazil On Fri, Nov 18, 2011 at 7:23 AM, Ketil Malde ke...@malde.org wrote: John Meacham j...@repetae.net writes: People tend to concentrate on the lambda which cooresponds to the functional aspect of haskell when designing logos. Not nearly enough attention is paid to the other striking feature, the What about types? This is a distinguishing feature from many of the other lambda-users out there, isn't \lambda_\tau used to signify that? -k -- If I haven't seen further, it is by standing in the footprints of giants ___ 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
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 Tibelljohan.tib...@gmail.com 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] ST not strict enough?
On Friday 18 November 2011, 13:05:06, Yves Parès wrote: ...so there is no way to do that inside the function passed to modifySTRef? In other words, there is no way to ensure inside a function that its result will be evaluated strictly? Well, modifySTRef ref fun = do val - readSTRef ref writeSTRef ref (fun val) (resp. modifySTRef ref f = writeSTRef ref . f = readSTRef ref as it's actually written in Data.STRef). What's written to ref is the thunk (fun val), meaning, when the value is demanded, evaluate fun applied to the argument val. So, no, the function is not entered before the result is demanded, hence it can't. It can ensure that the result is evaluated to a deeper level than required by the calling context when the function is entered, though. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Superset of Haddock and Markdown
On 18/11/11 09:18, Ivan Lazar Miljenovic wrote: On 18 November 2011 19:06, Roman Cheplyakar...@ro-che.info wrote: Maybe have a switch that enables markdown and disables markup-related features of haddock (everything except linking to identifiers/modules, I believe), so that we don't affect existing docs. Then make it possible to pass this flag through cabal. As in have an opt-in Cabal field? For a cabal field, we could just have haddock be the default markup language. Something like: DocMarkupLanguage: Haddock | Markdown | Plain | Html | ... -- default is Haddock But before worrying about that, such a possibility should exist in haddock. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ST not strict enough?
On 18 November 2011 13:17, Daniel Fischer daniel.is.fisc...@googlemail.com wrote: On Friday 18 November 2011, 13:05:06, Yves Parès wrote: ...so there is no way to do that inside the function passed to modifySTRef? In other words, there is no way to ensure inside a function that its result will be evaluated strictly? Well, modifySTRef ref fun = do val - readSTRef ref writeSTRef ref (fun val) But note therefore that you can just: val - readSTRef ref writeSTRef ref $! fun val rather than using modifySTRef. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion
Yves Parès wrote: While re-reading RealWorldHaskell, chapter 25, I saw that -- unlike I believed -- loop fusion wasn't activated by default under GHC for lists (but that module Data.List.Stream from package stream-fusion could provide it). Note that stream fusion is only one way to do fusion. For lists, GHC uses foldr/build fusion which is a different approach but still fuses loops. You get this by default when compiling with optimisations. Is that still the case? If not, then are there some cases of list processing where loop fusion would be a bad thing? (Ergo cases where you should stick to Prelude/Data.List functions and not use Data.List.Stream implementation) I'm not sure if anybody has actually benchmarked the stream-fusion package with a modern GHC. I suspect it wouldn't hold up well, too many things have changed in the compiler since it was written. So I'm not really sure you should be using it at all. Chances are, if you really care about having tight loops you shouldn't be using lists at all. 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
On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka r...@ro-che.info 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 Fri, Nov 18, 2011 at 1:58 AM, Roman Leshchinskiy r...@cse.unsw.edu.au 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 5:02 AM, Twan van Laarhoven twa...@gmail.com 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
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
[Haskell-cafe] Visi.Pro -- My Next Thing
Howdy Haskeller, I've launch a new, Haskell powered, adventure: Visi.Pro, Cloud Computing for the Rest of Us. Visi.Pro will offer a HyperCard-like development environment that will empower normal people to build and run beautiful, interactive apps on their iPad and seamlessly integrate the Cloud including real-time data feeds and destinations. More about the journey that led me to Visi.Pro at http://blog.visi.io/ and more about the product vision at http://visi.pro (http://visi.pro/) I am totally stoked about where this journey will lead... it's going to be amazingly exciting! I'm also looking forward to taking advantage of Haskell awesomeness as I build Visi.Pro and Visi.io out. Haskell has been a wonderful journey for me so far. The quality in design and implementation of the language, the runtime, and the libraries is amazing. I am standing on the shoulders of giants by building Visi.Pro on Haskell. Thanks! David -- @dpp ___ 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 johan.tib...@gmail.com [2011-11-18 08:06:29-0800]
On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka r...@ro-che.info 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
On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka r...@ro-che.info wrote: * Johan Tibell johan.tib...@gmail.com [2011-11-18 08:06:29-0800] On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka r...@ro-che.info 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
* Brandon Allbery allber...@gmail.com [2011-11-18 12:20:33-0500] On Fri, Nov 18, 2011 at 12:16, Roman Cheplyaka r...@ro-che.info wrote: * Johan Tibell johan.tib...@gmail.com [2011-11-18 08:06:29-0800] On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka r...@ro-che.info 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 9:16 AM, Roman Cheplyaka r...@ro-che.info wrote:
* Johan Tibell johan.tib...@gmail.com [2011-11-18 08:06:29-0800]
On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka r...@ro-che.info 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
On Fri, 18 Nov 2011 06:58:41 +0100, Evan Laforge qdun...@gmail.com 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
