4
\$\begingroup\$

So I've read an F# question on partitioning a list in F# and wondered whether I could cleanly write the concept down in haskell and if that would help me review the code ...

Now I have a haskell implementation of this "not-quite partition, not-quite group" and noticed it seems somewhat clumsy

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list 
    where
        go :: ([a] -> Bool) -> [a] -> [a] -> [[a]]
        go _ working [] = [working]
        go pred working l@(x:xs) = if pred working
                then (working:(go pred [] l))
                else go pred (working++[x]) xs 

A few questions:

  1. The compiler gets very annoyed with me when I try to express the else-branch as a concatenation with : instead of ++. Would it be cleaner to use the following go?

    go _ working [] = [reverse working]
    go pred working l@(x:xs) = if pred working
        then ((reverse working):(go pred [] l))
        else go pred (x:working) xs
    
  2. Am I missing a special case of groupBy here? It feels like there should be a simple standard function to do this

\$\endgroup\$
4
\$\begingroup\$

The code can be written cleaner if one removes the pred from go. go has access to all bindings in its context, including the ones in partitionOn pred list.

A first step to declutter partitionOn is therefore to get rid of duplication and get rid of unnecessary parentheses:

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list 
    where
        go working [] = [working]
        go working l@(x:xs) = if pred working
                then working : go [] l
                else go (working ++ [x]) xs

Note that I've removed go's type signature. This is somewhat controversial, but the general rule-of-thumb is that you want type signatures at the top-level and usually leave the type-signatures at the not-top level, unless GHC gets confused.

The (small) problem with type signatures in where and let is that the type parameter a in parititionOn is not the same as the one in go. -XScopedTypeVariables is necessary for that. So lets get rid of that.

Would it be cleaner to use the following go?

No. Or rather: it would be slightly cleaner, but pred also needs to work on the reversed list. This is more obvious if we don't use a position-independent predicate:

notInOrder []           = False
notInOrder (x:xs@(y:_)) = x > y || notInOrder xs

Your old version returns [1..10] on partitionOn notInOrder [1..10], but your new one returns [[1],[2],[3],…,[10]], unless you also check pred (reverse working).

Therefore—At least in the sense of asymptotic analysis—both variants will have the same performance.

Am I missing a special case of groupBy here? It feels like there should be a simple standard function to do this.

The standard functions for splitting lists at some point are span, break, splitAt, take(While), drop(While(End)), group(By), inits and tails. They all are concerned with a single element in their predicate, so they are not candidates for our problem, unless we already have our splits:

splits :: [a] -> [([a],[a])]
splits xs = zip (inits xs) (tails xs)

That function does not exist, though. A perfect building block for partitionOn would have the type signature ([a] -> Bool) -> [a] -> ([a],[a]), but that's missing from the standard library. Others packages provide functions with that signature, but none does provide our needed functionality.

But we can write that function ourself:

breakAcc :: ([a] -> Bool) -> [a] -> ([a],[a])
breakAcc p = go []
  where
    go ys []     = if p ys then (ys,[]) else ([],ys)
    go ys (x:xs) = if p ys then (ys, xs)
                           else go (ys ++ [x]) xs

-- or, using `splits` above:

breakAcc p xs = case find (p . fst) (splits xs) of
                 Just ys -> ys
                 Nothing -> ([], xs)

Note that the first variant still has the somewhat awkward ++ [x] there. A partition that starts from the right wouldn't have that problem, but we're stuck with that.

Now partitionOn is just

-- feel free to use a worker wrapper approach here
partitionOn p xs = case spanAcc p xs of
              ([],bs) -> [bs]
              (as,bs) -> as : partitionOn p bs

Note that this will add the empty list at the end if our partition works for all elements, e.g. partitionOn ((0 <) . sum) [1..4] == [[1],[2],[3],[4],[]]. But that's easy to get rid of.

All at once:

import Data.List (inits, tails, find)

splits :: [a] -> [([a],[a])]
splits xs = zip (inits xs) (tails xs)

breakAcc :: ([a] -> Bool) -> [a] -> ([a],[a])
breakAcc p xs = case find (p . fst) (splits xs) of
                  Just ps -> ps
                  Nothing -> ([],xs)

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn p xs = case breakAcc p xs of
                     ([],bs) -> [bs]
                     (as,bs) -> as : partitionOn p bs

-- for QuickCheck
partitionOnResult_prop :: ([a] -> Bool) -> [[a]] -> Bool
partitionOnResult_prop p xs = all p (init xs)

partitionOn_prop :: ([a] -> Bool) -> [a] -> Bool
partitionOn_prop p xs = partitionOnResult_prop p (partitionOn p xs)

-- quickCheck $ \(Blind p) -> partitionOn_prop p

Now that we have all of this code, let's compare it again with your (almost) original variant:

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list 
    where
        go working [] = [working]
        go working l@(x:xs) = if pred working
                then working : go [] l
                else go (working ++ [x]) xs

If we quint our eyes, both codes look the same (if we use the first breakAcc variant). However, I wouldn't call a list l, since lists are usually identified with a suffix s called e.g. ls. Also, working is somewhat of a misnomer: are we working with that list? Or does that list fulfill some requirement? As we currently accumulate elements in there, the usual acc or accs might be better, but naming is hard and left as an exercise.

Other than that, unless you want to have little, test-able functions, your original variant was therefore fine to begin with, but contained some functions that can be re-used.

\$\endgroup\$
0
\$\begingroup\$

Having explored several options in the original question. I quite liked the option of using a fold. The resulting function strikes me as pretty clean and easy to understand.

I've spend several minutes learning Haskell to post this here, so please excuse me if it's not quite idiomatic.

partitionOn pred list = nestedReverse (foldl folder [] list)
    where
        folder [] y = [[y]]
        folder (x:xs) y
            | pred x = [y]:(x:xs)
            | otherwise = (y:x):xs
        nestedReverse list = reverse (map (\l -> reverse l) list)

let result1 = partitionOn (\l -> sum l  > 5) [1,5,2,6,2]
let result2 = partitionOn (\l -> length l == 3) [1,5,2,6,2]

This builds up the result backwards and reverses it, as appending to the end of a list is expensive in F#, and I'm assuming the same is true of Haskell.

\$\endgroup\$
  • \$\begingroup\$ As mentioned by Zeta on the original question, this only works if the predicate is position-independent. Or ordering independent. As such this is pretty idiomatic, but doesn't actually do the same thing \$\endgroup\$ – Vogel612 Nov 10 '17 at 12:52
  • \$\begingroup\$ @Vogel612 good point. I hadn't noticed that as all of my use-cases have been order independent up to now. I guess just changing to pred (reverse x) but that's probably a touch inefficient. \$\endgroup\$ – Scroog1 Nov 10 '17 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.