haskell - 将树(嵌套列表)展平到一定深度

Question

我有一个递归代数数据类型来实现类似 Lisp 的嵌套列表:

data T a = N a | L [T a] deriving (Show, Eq)

L [N 1, L [N 2, L [N 3, L [N 4], N 5], N 6], N 7]相当于 Lisp 的 (1 (2 (3 (4) 5) 6) 7) .现在我想部分展平这个嵌套列表，即降低到某个级别，但仅此而已:

flattenN 0 t -- L [N 1,L [N 2,L [N 3,L [N 4],N 5],N 6],N 7]
flattenN 1 t -- L [N 1,N 2,L [N 3,L [N 4],N 5],N 6,N 7]
flattenN 2 t -- L [N 1,N 2,N 3,L [N 4],N 5,N 6,N 7]
flattenN 3 t -- L [N 1,N 2,N 3,N 4,N 5,N 6,N 7]

我将此函数实现为树递归，其中元素从类型构造函数解包，连接，然后打包回 L :

flattenN :: Int -> T a -> T a
flattenN 0 x = x
flattenN n (N x) = N x
flattenN n (L []) = L []
flattenN n (L (x:xs)) = flattenN (n-1) x +++ flattenN n (L xs)
  where N  x +++ N  y = L [N x, N y]
        N  x +++ L ys = L (N x:ys)
        L xs +++ N  y = L (xs++[N y])
        L xs +++ L ys = L (xs++ys)

对我来说，这看起来有点难看，应该比这更简单。您是否有任何想法如何以不同的方式实现嵌套列表函数的部分展平？我很高兴收到任何答案，从简约优雅到巧妙复杂，以及 Haskell 提供的任何功能。

Answer 1

我会写一个扁平化一次的函数，然后迭代它。像这样:

values (N x) = [N x]
values (L ts) = ts

flattenOnce (L ts) = L (concatMap values ts)
flattenOnce t = t

flattenN n t = iterate flattenOnce t !! n

如果你觉得神秘，你也可以实现 flattenOnce作为

flattenOnce t = L (concatMap values (values t))