Hi,
On 02.09.2010, at 13:41, Daniel Fischer wrote:
takes a little to run and keeps the entire file until the first
occurrence
of pat in memory.
first of all thanks very much for the detailed instructions.
I have rewritten the example slightly using Strings instead of
Bytestrings. Replacing all occurrences of 'รค' by "ä" in the
collected works of Shakespeare ; ) has a maximum memory usage of
around 65MB with the current implementation of intersperse while it
has a maximum memory usage of only around 5KB with the less strict
implementation.
replaceBy :: Eq alpha => alpha -> [alpha] -> [alpha] -> [alpha]
replaceBy x sep = concat . intersperse sep . splitBy (==x)
splitBy :: (alpha -> Bool) -> [alpha] -> [[alpha]]
splitBy _ [] = []
splitBy p xs =
case break p xs of
(l,ys) -> l : case ys of
[] -> []
(_:zs) -> splitBy p zs
This function only runs in constant space if I use the strict pattern
matching on the result of break. If I use the following implementation
I observe a linear memory usage instead.
splitBy' :: (alpha -> Bool) -> [alpha] -> [[alpha]]
splitBy' _ [] = []
splitBy' p xs =
l : case ys of
[] -> []
(_:zs) -> splitBy' p zs
where
(l,ys) = break p xs
I think this is due to the Wadler tuple space leak. The same would
apply to the current implementation of lines. I wonder whether an
implementation of lines analogous to splitBy has any disadvantages.
That is, we could have
intersect [] _|_ = [] and intersect (_|_:_|_) [] = []
or
intersect [] (_|_:_|_) = [] and intersect _|_ [] = []
and the current implementation satisfies neither.
Right. So the question is, has the current implementation advantages
over
either of these? (I don't see any.) If not, which of these two
behaviours
is preferable?
I'd prefer the first one as it is in line with the left to right
pattern matching of Haskell.
I have mixed feelings about those. Part of me dislikes breaking the
symmetry between (<=), (==) and compare.
I think you should not blame (<=) for the existence of a function that
yields a superset of the information that (<=) yields ; )
Cheers, Jan_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
