1
\$\begingroup\$

Learn You a Haskell mentions the partition function:

partition takes a list and a predicate and returns a pair of lists. The first list in the result contains all the elements that satisfy the predicate, the second contains all the ones that don't.

How's my implementation? I'd prefer to avoid the ++ function, but I'm not sure how to avoid it here.

partition' :: (a -> Bool) -> [a] -> ([a], [a])
partition' f []     = ([], [])
partition' f ys = partition'' f ys [] []
                       where partition'' f [] as bs = (as, bs)
                             partition'' f (x:xs) as bs 
                               | f x       = partition'' f xs (as ++ [x]) bs
                               | otherwise = partition'' f xs as (bs ++ [x])
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Your current version is not equivalent to the partition of Data.List. take 10 $ fst $ partition' (\x -> (x `mod` 2 == 0)) [1..] gives a runtime error. Where as take 10 $ fst $ partition (\x -> (x `mod` 2 == 0)) [1..] is [2,4,6,8,10,12,14,16,18,20] \$\endgroup\$ Commented May 12, 2014 at 11:21
  • \$\begingroup\$ @abuzittingillifirca You've found a bug. I think that's worthy of an answer, not a comment. \$\endgroup\$ Commented May 12, 2014 at 12:00
  • \$\begingroup\$ thank you, @abuzittingillifirca, for finding this bug. thanks too, 200_success. \$\endgroup\$ Commented May 14, 2014 at 0:03

2 Answers 2

Reset to default
6
\$\begingroup\$

As @aled1027 suggests, partition' is just a fancy form of filter. Therefore, it would be useful to study how filter can be implemented without ++.

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f (x:xs)
  | f x       = x:rest
  | otherwise = rest
  where rest = filter' f xs

The key to avoiding ++, I think, is to force yourself to write x: first, then figure out how to fill in everything surrounding it. The next logical step would be to write

  | f x = x:filter' f xs

… and the rest should follow naturally.

Here's what I came up with for partition' (hover for spoiler):

partition' :: (a -> Bool) -> [a] -> ([a], [a]) partition' _ [] = ([], []) partition' f (x:xs) | f x = ((x:accepted), rejected) | otherwise = (accepted, (x:rejected)) where (accepted, rejected) = partition' f xs

\$\endgroup\$
1
  • \$\begingroup\$ Excellent! I used your helpful answer to write your "spoiler" answer. It's so concise - thanks \$\endgroup\$ Commented May 17, 2014 at 14:50
0
\$\begingroup\$

Why not just use filter -- unless you are trying to avoid using filter? Filter would remove the need for ++.

Check out this SO question.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.