haskell - Haskell中是否可以定义一个返回n维列表的函数

Question

我想做这样的事情:

makeList n
    | n == 0 = [0 ..]
    | n > 0  = repeat $ makeList (n - 1)
    | n < 0  = undefined

该代码是错误的，因为其返回类型取决于值n。有没有办法实现类似的东西？

此外，我想构造一个 N 维列表，其中每个元素都包含其索引，例如:

oneD = [0 ..]
twoD = map (\x -> map (\y -> (x, y)) [0 ..]) [0..]
threeD = .. -- hard to code

有没有一种优雅的方式来构造高维列表？

Answer 1

在hugomg的回答中，我们有

data RecList a
  = Elem a
  | Dim [RecList a]
  deriving (Eq, Show)

这些并不能完全代表某些 n 的 n 维列表；事实上，它们允许混合不同维度的列表，如 Dim [Elem 0, Dim [Elem 0]] 所示。在 Cactus 的回答中，我们有一个更复杂的类型，它通过在类型级别公开维度并强制所有列表都具有该维度来解决此问题；但它使用了一些相当复杂的扩展。

在这个答案中，我们将给出一个不包含混合维度列表的类型，但不需要扩展。这个想法只是通过为高维列表提供更多构造函数来跟踪维度。所以:

data DeepList a = Z a | S (DeepList [a]) deriving Show

每个值都是一个给出维度的 Peano nat，后跟该维度的列表。因此:

Z 0
S (Z [0])
S (S (Z [[0]]))

都是值。另一方面，我们根本不能写这样的东西

S (S (Z ["zero", ["zero"]]))

因为它的类型不正确!

我们可以构造这种类型的值。出于测试目的，我将使用 replicate 3 而不是 repeat，但想法是相同的。

makeList :: Int -> a -> DeepList a
makeList 0 v = S (Z (replicate 3 v))
makeList n v = S (makeList (n-1) (replicate 3 v))

在 ghci 中:

*Main> makeList 2 5
S (S (S (Z [[[5,5,5],[5,5,5],[5,5,5]],[[5,5,5],[5,5,5],[5,5,5]],[[5,5,5],[5,5,5],[5,5,5]]])))

一旦我们为 DeepList 提供了一个 Functor 实例，编写索引列表也不会太难:

instance Functor DeepList where
    fmap f (Z v) = Z (f v)
    fmap f (S v) = S (fmap (map f) v)

nD :: Int -> DeepList [Int]
nD 0 = Z []
nD n = S (fmap (\v -> map (:v) [0..]) (nD (n-1)))

在 ghci 中:

*Main> putStrLn . take 100 . show $ nD 3
S (S (S (Z [[[[0,0,0],[1,0,0],[2,0,0],[3,0,0],[4,0,0],[5,0,0],[6,0,0],[7,0,0],[8,0,0],[9,0,0],[10,0,
*Main> let S (S (S (Z v))) = nD 3
*Main> putStrLn . take 100 . show . drop 1 $ v
[[[[0,0,1],[1,0,1],[2,0,1],[3,0,1],[4,0,1],[5,0,1],[6,0,1],[7,0,1],[8,0,1],[9,0,1],[10,0,1],[11,0,1]
*Main> putStrLn . take 100 . show . map (drop 1) $ v
[[[[0,1,0],[1,1,0],[2,1,0],[3,1,0],[4,1,0],[5,1,0],[6,1,0],[7,1,0],[8,1,0],[9,1,0],[10,1,0],[11,1,0]
*Main> putStrLn . take 100 . show . map (map (drop 1)) $ v
[[[[1,0,0],[2,0,0],[3,0,0],[4,0,0],[5,0,0],[6,0,0],[7,0,0],[8,0,0],[9,0,0],[10,0,0],[11,0,0],[12,0,0