monadplus/lazy.markdown

Last active April 12, 2022 08:24

Star (0) You must be signed in to star a gist
Fork (0) You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/monadplus/ae87375a5764bd267138ff079a170e43.js"></script>
Save monadplus/ae87375a5764bd267138ff079a170e43 to your computer and use it in GitHub Desktop.

Lazy pattern matching

Raw

If the pattern was strict, the tuples must have been evaluated to WHNF
forcing the whole list to be traversed before p x could be evaluated. This would not work on infinite lists nor bottom values.

partition :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs = foldr (select p) ([],[]) xs
  where
    select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
    select p x ~(ts,fs) | p x       = (x:ts,fs)
                        | otherwise = (ts, x:fs)