Opened 4 years ago

Closed 4 years ago

#4282 closed proposal (fixed)

Proposal: make Data.List.intersperse and intercalate less strict

Reported by: daniel.is.fischer Owned by:
Priority: normal Milestone: Not GHC
Component: libraries/base Version: 6.12.3
Keywords: intersperse, laziness, intercalate Cc: bos@…, daniel.is.fischer@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Other Difficulty:
Test Case: Blocked By:
Blocking: Related Tickets:

Description (last modified by duncan)

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 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 ++ _|_

Attachments (1)

intersperse.dpatch (48.6 KB) - added by daniel.is.fischer 4 years ago.
Corrected patch

Download all attachments as: .zip

Change History (15)

comment:1 Changed 4 years ago by duncan

See the strictness testing framework in the stream fusion list library. It has a test that identifies this and a few other similar cases. I recall that there are two where the base implementations are too strict, intersperse and intercalate. There are others where H98 is basically wrong and base is right. There's particular wierdness with some of the generic functions not matching strictness with the non-generic versions.

comment:2 Changed 4 years ago by maeder

Does the following implementation gain something?

intersperse :: a -> [a] -> [a]
intersperse s l = case l of
  [] -> l
  x : r -> x : case r of
    [] -> r
    _ -> s : intersperse s r

comment:3 Changed 4 years ago by dons

As Duncan says, during the stream fusion work we identified some of the strictness properties of core functions were unusual. The List library has,

intersperse             :: a -> [a] -> [a]
intersperse _   []      = []
intersperse _   [x]     = [x]
intersperse sep (x:xs)  = x : sep : intersperse sep xs

But we wanted,

intersperse :: a -> [a] -> [a]
intersperse _   []       = []
intersperse sep (x0:xs0) = x0 : go xs0
  where
    go []     = []
    go (x:xs) = sep : x : go xs

Related by

prop_intersperse        = Test.intersperse `refines2`   Spec.intersperse
prop_intercalate        = Test.intercalate `refines2`   Spec.intercalate

There is an extensive set of strictness properties for Data.List now that we could use to improve their specification.

For the strictness property suite, look at,
http://code.haskell.org/~dons/code/stream-fusion/tests/Strictness/

comment:4 Changed 4 years ago by igloo

Please see http://www.haskell.org/haskellwiki/Library_submissions for the details of the library submissions process.

comment:5 Changed 4 years ago by bos

  • Cc bos@… added

comment:6 Changed 4 years ago by daniel.is.fischer

  • Cc daniel.is.fischer@… added

Discussion period two weeks, until 2010-09-30.

comment:7 Changed 4 years ago by daniel.is.fischer

  • Keywords intercalate added

I've forgotten to explicitly mention that this change would also change the behaviour of intercalate from

intercalate sep (xs : _|_) = _|_

to

intercalate sep (xs : _|_) = xs ++ _|_

which I also deem desirable and hence include in the proposal.
Thanks to Duncan for pointing out the omission.

comment:8 Changed 4 years ago by duncan

  • Description modified (diff)
  • Summary changed from Data.List.intersperse not lazy enough to Proposal: make Data.List.intersperse and intercalate less strict

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

comment:9 Changed 4 years ago 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.

comment:10 Changed 4 years ago by igloo

  • Milestone set to Not GHC

comment:11 Changed 4 years ago by daniel.is.fischer

  • Status changed from new to patch

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

Please review and apply.

comment:12 Changed 4 years ago 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?

Changed 4 years ago by daniel.is.fischer

Corrected patch

comment:13 Changed 4 years ago 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.

comment:14 Changed 4 years ago by igloo

  • Resolution set to fixed
  • Status changed from patch to closed

Applied, thanks

Note: See TracTickets for help on using tickets.