是否可以定义一个在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]]])))

一旦我们给出了一个Functor实例DeepList,编写索引列表也不难:

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