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)

我们如何为所有n> 0通常编写g n，而又不像上面那样显式地输入扩展名，理想情况下仅使用Prelude（必要时使用Control.Applicative）？注意，对于所有n> 3，f n = f (n-1)，因此可以递归定义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. 这产生了[[(Char, Int)]]，这是所需的结果类型，但是它需要有点...向侧面倾斜并相乘。您需要所有来自内部列表中值的不确定性选择的列表。非确定性选择是Applicative的[]实例的本质，事实证明，在sequence类型的某物上的[[a]]恰好是“产生从组合中组合元素得到的所有列表的操作”内部列表”。这使我进入sequence $ map f [1 .. n]。

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

Answer 2

喜欢这个：

g 0 = [[]]
g n = (\xs x -> xs ++ [x]) <$> g (n - 1) <*> f n

或更复杂，但也更有效：

g = map ($ []) . go
  where
    go :: Int -> [[(Char,Int)] -> [(Char,Int)]]
    go 0 = [id]
    go n = (\xs x -> xs . (x:)) <$> go (n - 1) <*> f n

这使用休斯列表/差异列表来避免\xs x -> xs ++ [x]的二次减速。