将树（嵌套列表）展平到一定深度

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))

将树（嵌套列表）展平到一定深度

Flatten a tree (nested list) up to a certain depth

tree

haskell

nested-lists

algebraic-data-types