在有序二叉树遍历期间避免列表串联
Haskell初学者在这里：二叉树的中序遍历很简单，例如：
data IntegerTree = Leaf Integer
| Node IntegerTree Integer IntegerTree
inorder :: IntegerTree -> [Integer]
inorder (Leaf n) = [n]
inorder (Node l n r) = inorder l ++ [n] ++ inorder r
然而，在我看来，必须有一个更有效的实现。由于列表是单链表，串联inorder l和[n]似乎浪费，特别是因为这种工作是为一棵大树进行多次。我可以通过以不同的方式编写相同的函数来避免这个问题吗？
我最初是在尝试解决以类似方式构建移动列表的河内塔难题时考虑到这一点的，我希望可以使用类似的递归算法解决许多问题。
回答
Nested ++，正如您在按顺序访问中所拥有的那样，可能效率低下。这是因为list1 ++ list2将复制（的脊椎）list1，如下：
(1:2:3:[]) ++ list2
=
1: ((2:3:[]) ++ list2)
=
1:2: ((3:[]) ++ list2)
=
1:2:3: ([] ++ list2)
=
1:2:3:list2
如果完成一次，复制第一个列表可能不会那么糟糕，但是当我们嵌套++时
((list1 ++ list2) ++ list3) ++ list4
我们复制副本的副本，这会减慢一切，通常使 O(N^2) 成为 O(N)。
在计算 时list1 ++ list2，一个关键思想是这样的：如果我们只能在[]内部保留一个指向末尾的“指针” list1，我们就可以避免复制，并简单地用指向 的指针重写它list2，我们将获得恒定时间（破坏性）追加。
现在，我们在 Haskell 中有命令式的可变性吗？不适用于常规列表。然而，我们可以将列表转换为“最终的功能”，即而不是写
1:2:3:[]
对于列表，我们可以写
end -> 1:2:3:end
来表示相同的数据。列表的后一种表示称为“差异列表”。从常规列表到差异列表的转换很简单：
type DList a = [a] -> [a]
toDList :: [a] -> DList a
toDlist = (++)
fromDlist :: DList a -> [a]
fromDlist dl = dl []
到目前为止一切顺利，但如何连接两个DList a？我们需要采取类似
list1 = end -> 1:2:3:end
list2 = end -> 4:5:6:7:end
并返回
concatenate list1 list2 = end -> 1:2:3:4:5:6:7:end
事实证明，这concatenate只是函数组合，(.)。即list1 . list2正是我们需要的串联。当我们评估
fromDList (list1 . list2)
-- i.e.
(list1 . list2) []
不进行复制，因为 的结尾list1立即链接到list2。
因此，考虑到这一点，我们可以用最少的更改重写您的代码：
inorder :: IntegerTree -> [Integer]
inorder tree = fromDList (inorderDL tree)
inorderDL :: IntegerTree -> DList Integer
inorderDL (Leaf n) = (n :) -- that is, end -> n: end
inorderDL (Node l n r) = inorderDL l . (n :) . inorderDL r
这不会产生列表副本，因为在每个递归步骤生成每个子列表时，它的尾部不会是[]，而是指向要连接的下一个列表的“指针”。
最后，请注意，在不同的角度下，这种方法正是威廉在他的回答中使用的方法。