Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
+---
  Reporter:  daniel.is.fischer  |  Owner:   
 
  Type:  proposal   | Status:  closed   
 
  Priority:  normal |  Milestone:  Not GHC  
 
 Component:  libraries/base |Version:  6.12.3   
 
Resolution:  fixed  |   Keywords:  intersperse, laziness, 
intercalate
  Testcase: |  Blockedby:   
 
Difficulty: | Os:  Unknown/Multiple 
 
  Blocking: |   Architecture:  Unknown/Multiple 
 
   Failure:  Other  |  
+---
Changes (by igloo):

  * status:  patch => closed
  * resolution:  => fixed


Comment:

 Applied, thanks

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner: 
Type:  proposal|   Status:  patch  
Priority:  normal  |Milestone:  Not GHC
   Component:  libraries/base  |  Version:  6.12.3 
Keywords:  intersperse, laziness, intercalate  | Testcase: 
   Blockedby:  |   Difficulty: 
  Os:  Unknown/Multiple| Blocking: 
Architecture:  Unknown/Multiple|  Failure:  Other  
---+

Comment(by daniel.is.fischer):

 Terribly sorry. Picked the patch from the wrong directory. Corrected patch
 uploaded, but if it's easier to edit the source yourself, the sep was
 meant to be passed to the recursive call, that's (marginally) more
 efficient than SATing.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner: 
Type:  proposal|   Status:  patch  
Priority:  normal  |Milestone:  Not GHC
   Component:  libraries/base  |  Version:  6.12.3 
Keywords:  intersperse, laziness, intercalate  | Testcase: 
   Blockedby:  |   Difficulty: 
  Os:  Unknown/Multiple| Blocking: 
Architecture:  Unknown/Multiple|  Failure:  Other  
---+

Comment(by igloo):

 The patch doesn't compile. I don't know if you meant for the `sep` arg to
 be passed to the recursive call of `prependToAll`, or for the function to
 be SATed?

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner: 
Type:  proposal|   Status:  patch  
Priority:  normal  |Milestone:  Not GHC
   Component:  libraries/base  |  Version:  6.12.3 
Keywords:  intersperse, laziness, intercalate  | Testcase: 
   Blockedby:  |   Difficulty: 
  Os:  Unknown/Multiple| Blocking: 
Architecture:  Unknown/Multiple|  Failure:  Other  
---+
Changes (by daniel.is.fischer):

  * status:  new => patch


Comment:

 The proposal was supported by Duncan Coutts, Felipe Lessa, Nicolas
 Pouillard, Christian Maeder and John Lato. No objections were raised.

 Please review and apply.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner: 
Type:  proposal|   Status:  new
Priority:  normal  |Milestone:  Not GHC
   Component:  libraries/base  |  Version:  6.12.3 
Keywords:  intersperse, laziness, intercalate  | Testcase: 
   Blockedby:  |   Difficulty: 
  Os:  Unknown/Multiple| Blocking: 
Architecture:  Unknown/Multiple|  Failure:  Other  
---+
Changes (by igloo):

  * milestone:  => Not GHC


-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner:
Type:  proposal|   Status:  new   
Priority:  normal  |Milestone:
   Component:  libraries/base  |  Version:  6.12.3
Keywords:  intersperse, laziness, intercalate  | Testcase:
   Blockedby:  |   Difficulty:
  Os:  Unknown/Multiple| Blocking:
Architecture:  Unknown/Multiple|  Failure:  Other 
---+

Comment(by daniel.is.fischer):

 A slightly faster implementation than the proposed is
 {{{
 intersperse :: a -> [a] -> [a]
 intersperse _   [] = []
 intersperse sep (x:xs) = x : intersperseLoop s xs

 intersperseLoop :: a -> [a] -> [a]
 intersperseLoop _   [] = []
 intersperseLoop sep (x:xs) = sep : x : intersperseLoop sep xs
 }}}
 In practice, I don't expect the difference to be measurable, but
 nevertheless.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #4282: Proposal: make Data.List.intersperse and intercalate less strict (was: Data.List.intersperse not lazy enough)

[GHC]

#4282: Proposal: make Data.List.intersperse and intercalate less strict
---+
Reporter:  daniel.is.fischer   |Owner:
Type:  proposal|   Status:  new   
Priority:  normal  |Milestone:
   Component:  libraries/base  |  Version:  6.12.3
Keywords:  intersperse, laziness, intercalate  | Testcase:
   Blockedby:  |   Difficulty:
  Os:  Unknown/Multiple| Blocking:
Architecture:  Unknown/Multiple|  Failure:  Other 
---+

Old description:

> Investigating a space leak in Data.Text.Lazy.replace, I found that
> Data.List.intersperse is not lazy enough.
> {{{
> intersperse :: a -> [a] -> [a]
> intersperse _   []  = []
> intersperse _   [x] = [x]
> intersperse sep (x:xs)  = x : sep : intersperse sep xs
> }}}
> If a is for example a list-like type and the list elements are lazily
> produced one after the other, intersperse requires each element to be
> completely constructed and whether a next one follows to be determined
> before it delivers anything. Thus it forces O(size element) space
> behaviour. This also affects intercalate.
> {{{
> intersperse _   [] = []
> intersperse sep (x:xs) = x : intersperse' xs
>   where
> interpserse' [] = []
> intersperse' (y:ys) = sep : y: intersperse' ys
> }}}
> would fix it.

New description:

 It is proposed that `intersperse` and `intercalate` be changed to be less
 strict.

 Period of discussion: Two weeks, until 30 Sep. 2010.

 A patch is attached to this ticket. See also the
 [http://www.haskell.org/pipermail/libraries/2010-September/014293.html
 mailing list discussion thread].

 This change is in keeping with the spirit of the Haskell98 List module,
 which is for list functions to be as lazy as possible (unless there are
 good reasons otherwise). There are use cases where the current overly-
 strict versions are problematic. In addition, the more lazy versions are
 slightly more efficient.

 current implementation:
 {{{
 intersperse :: a -> [a] -> [a]
 intersperse _   [] = []
 intersperse _   [x]= [x]
 intersperse sep (x:xs) = x : sep : intersperse sep xs
 }}}
 current strictness properties:
 {{{
 intersperse _   _|_   = _|_
 intersperse _   (x :_|_)  = _|_
 intersperse sep (x:y:_|_) = x : sep : _|_
 }}}

 proposed implementation:
 {{{
 intersperse :: a -> [a] -> [a]
 intersperse _   [] = []
 intersperse sep (x:xs) = x : go xs
  where
go [] = []
go (y:ys) = sep : y : go ys
 }}}
 strictness properties after change:
 {{{
 intersperse _   _|_   = _|_
 intersperse _   (x:_|_)   = x : _|_
 intersperse sep (x:y:_|_) = x : sep : y : _|_
 }}}

 current and proposed implementation of `intercalate`:
 {{{
 intercalate :: [a] -> [[a]] -> [a]
 intercalate sep xss = concat (intersperse sep xss)
 }}}
 current strictness properties:
 {{{
 intercalate _   _|_ = _|_
 intercalate _   (xs:_|_)= _|_
 intercalate sep (xs:ys:_|_) = xs ++ sep ++ _|_
 }}}
 strictness properties after proposed change to `intersperse`:
 {{{
 intercalate _   _|_ = _|_
 intercalate _   (xs:_|_)= xs ++ _|_
 intercalate sep (xs:ys:_|_) = xs ++ sep ++ ys ++ _|_
 }}}

--

Comment(by duncan):

 Proposal description updated (edited on behalf of Daniel who cannot edit
 the ticket description).

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs