应对任意深度嵌套列表

Question

我正在编写一段代码,通过吃掉包含输入元素的列表来产生大量结果.说[i1,i2,i3,i4]

产生结果的函数将以所有可能的方式组合前两个:o1,o2和o3,并用此计算的结果替换输入:

[[o1,i3,i4],[o2,i3,i4],[o3,i3,i4]]

从现在开始,我希望依靠递归来生成单个列表的列表,这些列表是组合输入的结果,但我仍然在应对任意嵌套列表时遇到问题,很可能是因为我正在寻求映射输出回到这种(某种)功能:

tides :: [a] -> [a]
tides (i1:i2:is) =  map tides ((makeResult i1 i2):is) 
tides [] = []

- 其中makeResult产生所述输出

这不起作用,我相信我不会发现这样的工作功能.描述这种递归的正确方法是什么？

Answer 1

列表类型([])不进行任意嵌套,它在其他类型的顶部引入了一个级别的"列表".

[1,2,3]            :: [Int]
[(), (), ()]       :: [()]
[[1,2,3], [4,5,6]] :: [[Int]]

这意味着您的嵌套列表集中的每个子树必须具有相同的深度.此外,这个确切的深度必须以类型(静态!)表示,因此您必须在编译时知道它.

如果你习惯了更多动态列表,那么这听起来很荒谬.然而,真正发生的事情是,Haskell列表只是比其他地方使用的列表更具限制性的类型 - 这些列表实际上是Rose Trees:

data Rose a = Rose [Rose a] | Leaf a

类型的值Rose a可以是一个单件(包装在一个Leaf)或列表Rose as,各进一步被任一个单或列表的另一层,仅在运行时可用的区别.

(((1 (2 3)) 
  (4 5) 6) 
 (1 2))

Rose [ Rose [Leaf 1, Rose [Leaf 2, Leaf 3]]
     , Rose [Rose [Leaf 4, Leaf 5], Leaf 6]
     , Rose [Leaf 1, Leaf 2]]