CODEWITHSUNDEEP
haskell
Alex B
Alex B

Reputation: 84952

How to partition a list in Haskell?

I want to take a list (or a string) and split it into sub-lists of N elements. How do I do it in Haskell?

Example:

mysteryFunction 2 "abcdefgh"
["ab", "cd", "ef", "gh"]

Upvotes: 3

Views: 7635

Answers (7)

Sassa NF
Sassa NF

Reputation: 5406

A fancy answer.

In the answers above you have to use splitAt, which is recursive, too. Let's see how we can build a recursive solution from scratch.

Functor L(X)=1+A*X can map X into a 1 or split it into a pair of A and X, and has List(A) as its minimal fixed point: List(A) can be mapped into 1+A*List(A) and back using a isomorphism; in other words, we have one way to decompose a non-empty list, and only one way to represent a empty list.

Functor F(X)=List(A)+A*X is similar, but the tail of the list is no longer a empty list - "1" - so the functor is able to extract a value A or turn X into a list of As. Then List(A) is its fixed point (but no longer the minimal fixed point), the functor can represent any given list as a List, or as a pair of a element and a list. In effect, any coalgebra can "stop" decomposing the list "at will".

{-# LANGUAGE DeriveFunctor #-}
import Data.Functor.Foldable

data N a x = Z [a] | S a x deriving (Functor)

(which is the same as adding the following trivial instance):

instance Functor (N a) where
  fmap f (Z xs) = Z xs
  fmap f (S x y) = S x $ f y

Consider the definition of hylomorphism:

hylo :: (f b -> b) -> (c -> f c) -> c -> b
hylo psi phi = psi . fmap (hylo psi phi) . phi

Given a seed value, it uses phi to produce f c, to which fmap applies hylo psi phi recursively, and psi then extracts b from the fmapped structure f b.

A hylomorphism for the pair of (co)algebras for this functor is a splitAt:

splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs = hylo psi phi (n, xs) where
  phi (n, []) = Z []
  phi (0, xs) = Z xs
  phi (n, (x:xs)) = S x (n-1, xs)

This coalgebra extracts a head, as long as there is a head to extract and the counter of extracted elements is not zero. This is because of how the functor was defined: as long as phi produces S x y, hylo will feed y into phi as the next seed; once Z xs is produced, functor no longer applies hylo psi phi to it, and the recursion stops.

At the same time hylo will re-map the structure into a pair of lists:

  psi (Z ys) = ([], ys)
  psi (S h (t, b)) = (h:t, b)

So now we know how splitAt works. We can extend that to splitList using apomorphism:

splitList :: Int -> [a] -> [[a]]
splitList n xs = apo (hylo psi phi) (n, xs) where
  phi (n, []) = Z []
  phi (0, xs) = Z xs
  phi (n, (x:xs)) = S x (n-1, xs)

  psi (Z []) = Cons [] $ Left []
  psi (Z ys) = Cons [] $ Right (n, ys)
  psi (S h (Cons t b)) = Cons (h:t) b

This time the re-mapping is fitted for use with apomorphism: as long as it is Right, apomorphism will keep using hylo psi phi to produce the next element of the list; if it is Left, it produces the rest of the list in one step (in this case, just finishes off the list with []).

Upvotes: 1

Will Ness
Will Ness

Reputation: 71119

There's already 

Prelude Data.List> :t either
either :: (a -> c) -> (b -> c) -> Either a b -> c

and

Prelude Data.List> :t maybe
maybe :: b -> (a -> b) -> Maybe a -> b

so there really should be

list :: t -> ([a] -> t) -> [a] -> t
list n _ [] = n
list _ c xs = c xs

as well. With it,

import Data.List (unfoldr)

g n = unfoldr $ list Nothing (Just . splitAt n)

without it, 

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

Upvotes: 1

Harkonnen
Harkonnen

Reputation: 11

mysteryFunction x "" = []
mysteryFunction x s = take x s : mysteryFunction x (drop x s)

Probably not the elegant solution you had in mind.

Upvotes: 1

Landei
Landei

Reputation: 54584

import Data.List 
import Data.Function

mysteryFunction n = map (map snd) . groupBy ((==) `on` fst) . zip ([0..] >>= replicate n)

... just kidding...

Upvotes: 1

is7s
is7s

Reputation: 3480

cabal update
cabal install split

And then use chunksOf from Data.List.Split

Upvotes: 13

Paul Manta
Paul Manta

Reputation: 31597

Here's one option:

partition :: Int -> [a] -> [[a]]
partition _ [] = []
partition n xs = (take n xs) : (partition n (drop n xs))

And here's a tail recursive version of that function:

partition :: Int -> [a] -> [[a]]
partition n xs = partition' n xs []
  where
    partition' _ [] acc = reverse acc
    partition' n xs acc = partition' n (drop n xs) ((take n xs) : acc)

Upvotes: 12

Lee
Lee

Reputation: 144206

You could use:

mysteryFunction :: Int -> [a] -> [[a]]
mysteryFunction n list = unfoldr takeList list
  where takeList [] = Nothing
        takeList l  = Just $ splitAt n l

or alternatively:

mysteryFunction :: Int -> [a] -> [[a]]
mysteryFunction n list = unfoldr (\l -> if null l then Nothing else Just $ splitAt n l) list

Note this puts any remaining elements in the last list, for example

mysteryFunction 2 "abcdefg" = ["ab", "cd", "ef", "g"]

Upvotes: 5

Related Questions