嵌套的块在Haskell中？

Question

说我想这样做:

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]]]

在Python中,我可以做到这一点

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]]]

但在哈斯克尔,我不能只说

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

要么

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

那么如何才能在Haskell中实现同样的功能呢？

Answer 1

类似的函数nestedChunksOf不能直接在Haskell中完成,至少不能在普通列表上运行.列表的深度是类型的一部分,因此您不能具有参数指定的任意深度.

但是你可以做的是巢chunksOf.

如果我们这样定义chunksOf:

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

我们可以嵌套它:

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]]]

我希望能完成你想要的!

Answer 2

正如在其他的答案说明,这不能被直接完成如在Haskell你总是需要知道的表达式的类型,从而区分[a],[[a]]等等.然而,使用多态递归可以定义一个数据类型,它允许这种任意嵌套通过在构造函数中包装每个级别:

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

所以只要Value是同构的a,Nested (Value ...)是同构的[a],双Nested对[[a]]等,然后你就可以实现

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

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

确实如此

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

输出

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

Answer 3

使用依赖类型可以相当容易地完成.

我们想表达的是[Int]参数的长度决定了结果的类型.我们需要两件事:一个具有固定长度的列表类型,以及一个从长度计算返回类型的类型级函数:

{-# 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将类型构造函数f n时间应用于参数.例如,Iterate (S (S Z)) [] Int减少到[[Int]].nestedChunksOf现在可以直接写:

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

用法:

> 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]]]