[Haskell-beginners] splitWith and foldr stack overflow

Felipe Lessa felipe.lessa at gmail.com
Sun Mar 22 13:02:18 EDT 2009


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.


More information about the Beginners mailing list