特定结构Excerpt的合并算法递归挂起问题求助

数据结构定义 #

data ExcerptNode = ExcerptNode (Maybe Int) (Either Excerpt [Int]) deriving (Show, Eq)
data Excerpt = Excerpt [ExcerptNode] deriving (Show, Eq)

需求与现有实现 #

需要实现两个核心功能：

• 将[Maybe Int]列表转换为Excerpt结构
• 合并Excerpt及其节点列表

现有实现代码如下：

maybeIntListToExcerptNode :: [Maybe Int] -> ExcerptNode
maybeIntListToExcerptNode [] = ExcerptNode Nothing (Right [])
maybeIntListToExcerptNode (x:xs) = if all (==Nothing) xs 
  then ExcerptNode x (Right [])
  else ExcerptNode x (Left $ Excerpt [ maybeIntListToExcerptNode xs ])

mergeExcerptNodes :: ExcerptNode -> ExcerptNode -> [ExcerptNode]
mergeExcerptNodes a@(ExcerptNode x (Right xls)) b@(ExcerptNode y (Right yls)) = if x == y 
  then [ExcerptNode x (Right (nub $ sort (xls ++ yls)))]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Left xls)) b@(ExcerptNode y (Right yls)) = if x == y 
  then [ExcerptNode x (Left xls)]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Right xls)) b@(ExcerptNode y (Left yls)) = if x == y 
  then [ExcerptNode y (Left yls)]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Left xls)) b@(ExcerptNode y (Left yls)) = if x == y 
  then [ExcerptNode x (Left (mergeExcerpts xls yls))]
  else [a, b]

mergeExcerpts :: Excerpt -> Excerpt -> Excerpt 
mergeExcerpts (Excerpt []) (Excerpt y) = Excerpt y
mergeExcerpts (Excerpt x) (Excerpt []) = Excerpt x
mergeExcerpts (Excerpt a) (Excerpt b) = Excerpt $ mergeExcerptNodesLists a b

mergeExcerptNodesLists :: [ExcerptNode] -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodesLists [] [] = []
mergeExcerptNodesLists x [] = x
mergeExcerptNodesLists [] y = y
mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs b)

mergeExcerptNodeIntoList :: ExcerptNode -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodeIntoList x [] = [x]
mergeExcerptNodeIntoList a@(ExcerptNode x (Right xls)) (b@(ExcerptNode y (Right yls)):ys) = if x == y 
  then [ExcerptNode x (Right (nub $ sort (xls ++ yls)))] ++ ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Left xls)) (b@(ExcerptNode y (Right yls)):ys) = if x == y 
  then [ExcerptNode x (Left xls)] ++ ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Right xls)) (b@(ExcerptNode y (Left yls)):ys) = if x == y 
  then [ExcerptNode y (Left yls)] ++ ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Left xls)) (b@(ExcerptNode y (Left yls)):ys) = if x == y 
  then [ExcerptNode x (Left (mergeExcerpts xls yls))] ++ ys
  else mergeExcerptNodeIntoList a ys 

问题描述 #

当前算法在mergeExcerptNodesLists的以下代码行出现无限递归挂起：

mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs b)

示例输入 #

a = maybeIntListToExcerptNode [Nothing, Nothing, Just 0]; b = maybeIntListToExcerptNode [Nothing, Nothing, Just 1];
mergeExcerptNodes a b

预期输出 #

[ExcerptNode Nothing (Left (Excerpt [ExcerptNode Nothing (Left (Excerpt [ExcerptNode (Just 1) (Right []),ExcerptNode (Just 0) (Right [])]))]))]

已尝试的修改及问题 #

• 修改为mergeExcerptNodesLists (x:xs) b@(y:ys) = (mergeExcerptNodeIntoList x b) ++ (mergeExcerptNodesLists xs b)：仅做列表追加，未完成节点合并逻辑
• 修改为mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs ys)：会遗漏部分待合并的元素

优化思路 #

1. 修正递归逻辑：原递归式的核心问题是重复处理原b列表，导致无限递归。正确逻辑应为逐个将xs中的元素合并到当前结果列表中，而非重复处理原列表：

   mergeExcerptNodesLists (x:xs) b = mergeExcerptNodesLists xs (mergeExcerptNodeIntoList x b)
   

   该逻辑是：以b为初始结果，依次将xs中的每个节点合并到结果列表，最终得到完全合并后的列表。

2. 验证合并逻辑完整性：确保mergeExcerptNodeIntoList能正确处理所有节点类型组合——无论节点携带的是Right类型的整数列表，还是Left类型的嵌套Excerpt，只要节点的Maybe Int标识相同，就执行对应内容的合并，否则保留原节点。

3. 边界场景测试：针对空列表、单元素列表、多层嵌套列表等场景进行测试，确保合并逻辑覆盖所有边界情况，避免出现元素遗漏或递归异常。

内容的提问来源于stack exchange，提问作者altern