Nested chunksOf in Haskell?

Question

Say I want to do this:

nestedChunksOf [3, 2] [1,1,1,2,2,2,3,3,3,4,4,4] == [[[1,1,1], [2,2,2]], [[3,3,3], [4,4,4]]]

In Python, I can do this

def group(a, *ns):
    for n in ns:
        a = [a[i:i+n] for i in xrange(0, len(a), n)]
    return a

group([1,1,1,2,2,2,3,3,3,4,4,4], 3, 2) == [[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]]

But in Haskell, I can't just say

nestedChunksOf :: [Int] -> [a] -> [[a]]

or

nestedChunksOf :: [Int] -> [a] -> [[[a]]]

So how can I achieve the same thing in Haskell?

Answer 1

A function like nestedChunksOf can't be done directly in Haskell, at least not one which operates on normal lists. The depth of the list is part of the type, so you can't have an arbitrary depth specified by a parameter.

But what you can do is nest chunksOf.

If we define chunksOf like this:

chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = fxs : chunksOf n sxs
    where (fxs, sxs) = splitAt n xs

We can then nest it:

Main> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> chunksOf 3 [1,1,1,2,2,2,3,3,3,4,4,4]
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]
*Main> chunksOf 2 $ chunksOf 3 [1,1,1,2,2,2,3,3,3,4,4,4]
[[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]]

I hope that accomplishes what you wanted!

Answer 2

As stated in the other answers, this can't be done directly as in Haskell you always need to know the type of an expression and thus distinguish between [a], [[a]] etc. However, using polymorphic recursion you can define a data type that allows such arbitrary nesting by wrapping each level in a constructor:

data NestedList a = Value a | Nested (NestedList [a])
  deriving (Show)

So just Value is isomorphic to a, Nested (Value ...) is isomorphic to [a], double Nested to [[a]] etc. Then you can implement

chunksOf :: Int -> [a] -> [[a]]
...

nestedChunksOf :: [Int] -> [a] -> NestedList a
nestedChunksOf [] xs = Nested (Value xs)
nestedChunksOf (c:cs) xs = Nested (nestedChunksOf cs $ chunksOf c xs)

And indeed

print $ nestedChunksOf [3, 2] [1,1,1,2,2,2,3,3,3,4,4,4]

outputs

Nested (Nested (Nested (Value [[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]])))

Answer 3

This can not be achieved in Haskell through "normal" means because it would require a dependent type - the type of the result depends on the length of the first argument.

Perhaps a tuple solution would be acceptable?

{-# Language TypeFamilies #-}
{-# Language FlexibleInstances #-}
import Data.List.Split
class NestedChunksOf a where
    nco :: a -> [b] -> AList a b
    type AList a b :: *

instance NestedChunksOf (Int,Int) where
    nco (f,s) xs = chunksOf f (chunksOf s xs)
    type AList (Int,Int) a = [[[a]]]


-- More instances as desired.

Answer 4

It can be done fairly easily with dependent types.

We'd like to express that the length of the [Int] argument determines the type of the result. We need two things for that: a list type with fixed length, and a type-level function which computes the return type from the length:

{-# LANGUAGE DataKinds, GADTs, TypeFamilies #-}

import Data.List.Split

data Nat = Z | S Nat -- natural numbers (zero, successor)

data Vec n a where -- "n" length lists of "a" elements
  Nil  :: Vec Z a
  (:>) :: a -> Vec n a -> Vec (S n) a
infixr 5 :>

type family Iterate n f a where
  Iterate Z     f a = a
  Iterate (S n) f a = f (Iterate n f a)

Iterate n f a applies the type constructor f n times to an argument. For example, Iterate (S (S Z)) [] Int reduces to [[Int]]. nestedChunksOf can be written directly now:

nestedChunksOf :: Vec n Int -> [a] -> Iterate (S n) [] a
nestedChunksOf Nil       as = as
nestedChunksOf (n :> ns) as = chunksOf n $ nestedChunksOf ns as

Usage:

> nestedChunksOf (2 :> 3 :> Nil) [1,1,1,2,2,2,3,3,3,4,4,4]
[[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]]