如何在Haskell中按索引正确对齐元素并实现列表对比？

你的需求本质是对齐两个列表的公共元素，同时保留非公共元素在原列表中的位置，错位元素放到对应列表的末尾，并用占位符填充对应位置。我们可以基于**最长公共子序列（LCS）**来优雅实现，避免繁琐的逐个比对。

实现步骤 #

1. 计算两个列表的最长公共子序列（LCS），作为对齐的基准。
2. 从第二个列表中分离出属于LCS的元素和非LCS的错位元素。
3. 构建第一个列表的结果：原列表加上与错位元素数量相等的占位符。
4. 构建第二个列表的结果：遍历第一个列表，匹配LCS元素则保留，否则填占位符，最后追加错位元素。

完整代码 #

-- 计算两个列表的最长公共子序列（LCS）
lcs :: Eq a => [a] -> [a] -> [a]
lcs [] _ = []
lcs _ [] = []
lcs (x:xs) (y:ys)
  | x == y    = x : lcs xs ys
  | otherwise = maxBy length (lcs (x:xs) ys) (lcs xs (y:ys))
  where maxBy f a b = if f a >= f b then a else b

-- 从列表中提取出属于LCS的元素，同时返回剩余的非LCS元素
extractCommon :: Eq a => [a] -> [a] -> ([a], [a])
extractCommon [] _ = ([], [])
extractCommon _ [] = ([], [])
extractCommon (x:xs) lcs@(l:ls)
  | x == l    = let (common, rest) = extractCommon xs ls
                in (x : common, rest)
  | otherwise = let (common, rest) = extractCommon xs lcs
                in (common, x : rest)

-- 核心对齐函数
myFunc :: [String] -> [String] -> ([String], [String])
myFunc xs ys = (alignedX, alignedY)
  where
    -- 获取两个列表的公共子序列
    commonSeq = lcs xs ys
    -- 从ys中分离公共元素和错位元素
    (ysCommon, ysRest) = extractCommon ys commonSeq
    -- 构建第一个列表的结果：原列表 + 对应ys错位元素数量的占位符
    alignedX = xs ++ replicate (length ysRest) "-"
    -- 构建第二个列表的结果：匹配xs的公共元素，否则填占位符，最后追加错位元素
    buildAlignedY [] _ rest = rest
    buildAlignedY _ [] rest = map (const "-") xs ++ rest
    buildAlignedY (x:xs') (y:ys') rest
      | x == y    = y : buildAlignedY xs' ys' rest
      | otherwise = "-" : buildAlignedY xs' (y:ys') rest
    alignedY = buildAlignedY xs ysCommon ysRest

测试示例 #

let l1 = ["a", "b", "c"]
let l2 = ["a", "d", "c"]
(l1', l2') = myFunc l1 l2

-- 验证结果
l1' == ["a", "b", "c", "-"]  -- True
l2' == ["a", "-", "c", "d"]  -- True

扩展说明 #

• 如果需要处理更复杂的错位场景（比如两个列表都有多个错位元素），这个实现同样适用。例如：

  let l1 = ["x", "a", "b", "c", "y"]
  let l2 = ["a", "d", "c", "z"]
  (l1', l2') = myFunc l1 l2
  -- l1' = ["x","a","b","c","y","-","-"]
  -- l2' = ["-","a","-","c","-","d","z"]
  

• 若要调整占位符，只需修改replicate和map (const "-")中的"-"即可。

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