是否有可能定义在Haskell

Question

返回n维列表的功能，我想这样做：

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]]。在仙人掌的答案中，我们有一个更复杂的类型，通过在类型级别暴露维度并强制所有列表具有该维度来修复此问题;但它使用了一些非常复杂的扩展。

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

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 

Answer 2

makeList最大的问题是你不容易给它一个类型。你可以做的一件事是使用递归类型而不是列表列表。代替具有[a],[[a]],[[[a]]]，...的类型序列，您有一个类型RecList a，它表示具有任意数量级别的嵌套列表。

下面是使用长度为1的列表的简化示例，而不是无限列表：

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

makeNested :: Int -> RecList String 
makeNested n 
    | n == 0 = Elem "Hi There" 
    | n > 0 = Dim [(makeList (n - 1))] 
    | n < 0 = undefined 

从ghci的输出：

Main*> makeList 4 
Dim [Dim [Dim [Dim [Elem "0"]]]] 

通过使用递归类型这样你使维数是一种价值层面的东西，而不是一种类型的东西。它没有类型级别或基于元编程的解决方案的静态安全性，但它更容易实现。

Answer 3

您可以通过添加一个类型索引RecList跟踪在RecList的数dimenions的提高@ hugomg的答案代码：

{-# LANGUAGE GADTs, DataKinds, KindSignatures, TypeFamilies, StandaloneDeriving #-} 
import Data.Singletons 
import Data.Singletons.TH 

data Nat = Z | S Nat 

data RecList (d :: Nat) a where 
    Elem :: a -> RecList Z a 
    Dim :: [RecList d a] -> RecList (S d) a 
deriving instance (Show a) => Show (RecList d a) 

这样，你就会知道，RecList d a具有完全相同d尺寸。

下面是使用Singletons库来具体化一个类型级索引术语的例子，所以我们可以递归了它，使的()秒的无限，d维网：

{-# LANGUAGE TemplateHaskell #-} 

$(genSingletons [''Nat]) 

makeNested :: Sing d -> RecList d() 
makeNested SZ = Elem() 
makeNested (SS d) = Dim $ repeat (makeNested d) 

和这里的东西更接近自己的例子：

makeList :: Sing d -> RecList (S d) Int 
makeList SZ = Dim $ map Elem [0..] 
makeList (SS d) = Dim $ repeat $ makeList d