splitWith and foldr stack overflow
I wrote a splitWith function (from RWH) and then converted it to use foldr: splitWith, splitWith2 :: (a -> Bool) -> [a] -> [[a]] splitWith p xs = let (ls, ts) = f xs in ts:ls where f [] = ([], []) f (x:xs) | p x = (ls, x:ts) | otherwise = (ts:ls, []) where (ls, ts) = f xs splitWith2 p xs = let (ls, ts) = foldr f ([],[]) xs in ts:ls where f x (ls, ts) | p x = (ls, x:ts) | otherwise = (ts:ls, []) Tested with something simple like take 8 $ splitWith id (cycle [False,True]) splitWith works fine, but splitWith2 causes a stack overflow. Don't they have the same recursive structure, though?
On Sun, Mar 22, 2009 at 12:26:35PM -0400, Sean Bartell wrote:
splitWith p xs = let (ls, ts) = f xs in ts:ls where f [] = ([], []) f (x:xs) | p x = (ls, x:ts) | otherwise = (ts:ls, []) where (ls, ts) = f xs
splitWith2 p xs = let (ls, ts) = foldr f ([],[]) xs in ts:ls where f x (ls, ts) | p x = (ls, x:ts) | otherwise = (ts:ls, [])
[snip]
Don't they have the same recursive structure, though?
Err, no. In 'splitWith' you use 'where (ls, ts) = f xs', which means that you are binding 'ls' and 'ts' lazily, while on 'splitWith2' you use a pattern in the argument, which is strict. Being strict means that you need to traverse the whole list in order to produce any results. If you want to pattern match lazily, you just need to use an irrefutable pattern, changing 'f x (ls, ts)' to 'f x ~(ls, ts)'. And, just for the record, I'd prefer to write the function in semi-pointfree style, as in
splitWith3 p = uncurry (:) . foldr f ([],[]) where f x ~(ts, ls) | p x = (x:ts, ls) | otherwise = ([], ts:ls)
HTH, -- Felipe.
participants (2)
-
Felipe Lessa -
Sean Bartell