Is there a non-recursive way to write this "paginate" function?

Question

The following function is not in the standard Haskell libraries, so I wrote it:

paginate _ [] = []
paginate n xs = let (h, t) = splitAt n xs in h : paginate n t

Then I wanted to rewrite it without the explicit recursion yet still be easily understandable.

I've tried the fix version, which does not yield very satisfactory results:

paginate = fix go
  where
    go _ _ [] = []
    go v n xs = let (h, t) = splitAt n xs in h : v n t 

Are there simpler solutions which use the Prelude functions?

Answer 1

When I see this sort of problem, I like to think about the "shape" of the function you want. In this case, you're starting with a list and producing a list of lists. This is a special case of starting with a single value and producing a list, which corresponds to an unfold. So, if you don't mind importing Data.List, you can neatly write your function using unfoldr.

Lets take a look at how to derive this step by step. First, as above, you just have to know about unfoldr and see that it can apply. This is where a bit of experience (like reading answers like this one :)) comes in.

Next, we take a look at the type of unfoldr:

Prelude Data.List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

The idea is that we start with a single "kernel" value (b), and apply a step function (b -> Maybe (a, b)) repeatedly until we hit Nothing. Our starting value is the list we want to separate into chunks, so we don't need to do any more processing there. This means the last step we have is implementing the step function.

Since we're starting with a list of values, we can replace b with [n]; moreover, since we want to produce a list of lists at the very end, we can replace [a] with [[n]] and, therefore, a with [n]. This gives us the final type we have to implement for the step function:

[n] -> Maybe ([n], [n])

Hey, that looks very similar to the type of splitAt!

splitAt :: Int -> a -> ([a], [a])

In fact, we can just wrap the result of splitAt in Just and satify our types. But this leaves out a very important part: the final Nothing that tells unfoldr to stop! So our helper function needs an extra base case for [] to return the right result.

Putting it all together gives us the final function:

import Data.List (unfoldr)

paginate n = unfoldr go
  where go [] = Nothing -- base case
        go ls = Just (splitAt n ls)

I think the end result is pretty good, but I'm not sure it's any more readable than the recursive version.

If you don't mind enabling an extension (LambdaCase), you can rewrite this in a slightly neater way by avoiding naming go:

paginate n = unfoldr $ \case
  [] -> Nothing
  ls -> Just (splitAt n ls)

Answer 2

FYI, following from Tikhon Jelvis' answer, I eventually ended up with:

boolMaybe p f x = if p x then Just (f x) else Nothing
groupWith       = unfoldr . boolMaybe null 
paginate        = groupWith . splitAt

which is a bit too obfuscated for me. Back to the recursive version.

Answer 3

Here is a slightly changed version of the Tikhon Jelvis' code:

import Data.Maybe
import Data.List
import Control.Applicative

paginate n = unfoldr $ \xs -> listToMaybe xs *> Just (splitAt n xs)

Or in pointfree:

paginate n = unfoldr $ (*>) <$> listToMaybe <*> Just . splitAt n