任何顺序或维度的 Haskell 列表理解

Question

考虑以下程序。

chars = [" "] ++ ["A"] ++ ["B"] ++ (repeat "ABCD")

f :: Int -> [(Char,Int)]
f n = (,) <$> (chars !! n) <*> [1..3]

g :: Int -> [[(Char,Int)]]
g 1 = (\a     -> [a    ]) <$> (f 1)
g 2 = (\a b   -> [a,b  ]) <$> (f 1) <*> (f 2)
g 3 = (\a b c -> [a,b,c]) <$> (f 1) <*> (f 2) <*> (f 3)
-- g n = (\x1 x2 ... xn -> [x1,x2,...,xn]) <$> (f 1) <*> (f 2) <*> ... (f n)

我们如何g n为所有 n > 0编写一般性的内容，而不像上面那样明确地输入扩展，理想情况下只使用Prelude（并且Control.Applicative如果需要）？请注意，f n = f (n-1)对于所有 n>3，因此可以g递归定义。

输出是这样的（忽略漂亮的打印）：

> g 1
[ [ ( 'A' , 1 ) ] , [ ( 'A' , 2 ) ] , [ ( 'A' , 3 ) ] ]

> g 2
[ [ ( 'A' , 1 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 3 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 3 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 3 ) ]
]

> g 3
[ [ ( 'A' , 1 ) , ( 'B' , 1 ) , ( 'A' , 1 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 1 ) , ( 'A' , 2 ) ]
...
, [ ( 'A' , 3 ) , ( 'B' , 3 ) , ( 'D' , 3 ) ]
]

Answer 1

g n = traverse f [1 .. n]

traverse 是前奏曲（至少在过去几年中）。

由于这有点不明显，这是我到达那里的方式：

1. 我注意到你申请f的是从 1 到 n 的数字，所以我从map f [1 .. n].

2. 这产生了 a [[(Char, Int)]]，这是所需的结果类型，但它需要有点......侧身并相乘。您需要来自内部列表中非确定性值选择的所有列表。非确定性选择是Applicativefor 实例的本质，[]事实证明，sequence在某种类型[[a]]上的操作正是“生成您通过组合组合来自内部列表的元素而获得的所有列表”的操作。这让我来sequence $ map f [1 .. n]。

3. 但是这对sequenceandmap很常见，以至于有一个操作可以同时执行这两个操作。sequence . map f=== traverse f。因此应用该规则简化了结果。 traverse f [1 .. n].