Haskell 中嵌套的 chunksOf？

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

但是在Haskell，我不能只说

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 中通过 "normal" 实现，因为它需要依赖类型 - 结果的类型取决于第一个参数的长度。

也许可以接受元组解决方案？

{-# 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 3

使用依赖类型可以很容易地完成。

我们想表达的是，[Int] 参数的长度决定了结果的类型。为此，我们需要两件事：固定长度的列表类型，以及根据长度计算 return 类型的类型级函数：

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

Answer 4

如其他答案所述，这不能像 Haskell 中那样直接完成，您始终需要知道表达式的类型，从而区分 [a]、[[a]] 等。但是，使用 polymorphic recursion 您可以定义一种数据类型，通过将每个级别包装在构造函数中来允许这种任意嵌套：

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

所以 Value 同构于 a，Nested (Value ...) 同构于 [a]，double 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]]])))

Haskell 中嵌套的 chunksOf？

Nested chunksOf in Haskell?

haskell

nested

list