From 2b17b2a58087c438ebd5a7de91b2e9f69e09a17f Mon Sep 17 00:00:00 2001 From: Daniel Fischer Date: Sat, 2 Oct 2010 23:12:01 +0000 Subject: [PATCH] Lazier intersperse A lazier implementation of intersperse, and consequentially intercalate, to avoid space leaks. --- Data/List.hs | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/Data/List.hs b/Data/List.hs index c954757..221a340 100644 --- a/Data/List.hs +++ b/Data/List.hs @@ -422,8 +422,16 @@ intersectBy eq xs ys = [x | x <- xs, any (eq x) ys] intersperse :: a -> [a] -> [a] intersperse _ [] = [] -intersperse _ [x] = [x] -intersperse sep (x:xs) = x : sep : intersperse sep xs +intersperse sep (x:xs) = x : prependToAll sep xs + + +-- Not exported: +-- We want to make every element in the 'intersperse'd list available +-- as soon as possible to avoid space leaks. Experiments suggested that +-- a separate top-level helper is more efficient than a local worker. +prependToAll :: a -> [a] -> [a] +prependToAll _ [] = [] +prependToAll sep (x:xs) = sep : x : prependToAll sep xs -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@. -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the -- 1.7.10.4