CODEWITHSUNDEEP
haskell
user1002430
user1002430

Reputation:

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

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?

Upvotes: 6

Views: 210

Answers (4)

Will Ness
Will Ness

Reputation: 71109

there's always been this:

import Data.List

chunks n = takeWhile (not . null) . unfoldr (Just . splitAt n)

but the new champion, for me, is

import Data.Maybe                    -- additional imports
import Control.Applicative

chunks n = unfoldr $ (<$) . splitAt n <*> listToMaybe
               --  \xs -> splitAt n xs <$ listToMaybe xs

(tweaking just a little bit the code from this comment by @user3237465).

The bits used here are:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
(f <*> g) x = f x (g x)              -- S combinator
x <$ c = fmap (const x) c            -- "mapped into"
listToMaybe xs = head (map Just xs ++ [Nothing])

Another, similar way to write it is

import Control.Monad                 -- an additional import

chunks n = unfoldr $ listToMaybe . join ((<$) . splitAt n)
               --  \xs -> listToMaybe (splitAt n xs <$ xs)

using the monadic join for functions,

join f x = f x x                     -- W combinator

Upvotes: 0

effectfully
effectfully

Reputation: 12715

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

Upvotes: 2

user1002430
user1002430

Reputation:

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.

Upvotes: 2

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

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)

Upvotes: 14

Related Questions