Haskell递归合并索引值对列表问题求助

你的函数出错的核心原因是在otherwise分支中丢弃了剩余的元组列表xs，每次递归只保留当前的(x,y)，导致后续的元组（比如示例中的(3,10)）永远不会被处理到。当处理完(4,5)后，递归传入的列表为空，函数就停止了，所以最终结果缺少了索引10对应的3。

下面提供两种可行的修复方案：

方案1：基于排序的递归实现（高效） #

先将元组按索引从小到大排序，再递归遍历索引逐个填充值或0，适合处理较大数据量：

import Data.List (sortBy)
import Data.Ord (comparing)

insert :: [(Int, Int)] -> [Int]
insert xs = insertSorted (sortBy (comparing snd) xs) 0
  where
    insertSorted :: [(Int, Int)] -> Int -> [Int]
    insertSorted [] _ = []
    insertSorted ((x, y):rest) t
      | t == y    = x : insertSorted rest (t + 1)
      | t < y     = 0 : insertSorted ((x, y):rest) (t + 1)
      | otherwise = insertSorted rest t  -- 跳过索引已过期的元组

工作逻辑： #

1. 通过sortBy (comparing snd)把元组按索引（元组第二个元素）从小到大排序，确保按顺序处理每个索引位置。
2. 递归函数insertSorted从索引0开始遍历：
   • 当前索引t等于元组索引y时，填入对应值x，递归处理剩余元组并将索引+1。
   • 当前索引t小于y时，填入0，索引+1，保留当前元组等待后续处理。
   • 当前索引t大于y时，跳过该元组，直接处理剩余元组。

测试示例：

insert [(2,0),(4,5),(3,10)]  -- 输出 [2,0,0,0,0,4,0,0,0,0,3]

方案2：基于查找的简洁实现（适合小列表） #

利用lookup函数直接查找每个索引对应的值，代码更简洁，适合数据量不大的场景：

import Data.List (maximum)
import Data.Maybe (maybe)

insert :: [(Int, Int)] -> [Int]
insert [] = []
insert xs = map getVal [0..maxIdx]
  where
    maxIdx = maximum (map snd xs)
    -- 转换元组格式为（索引，值），方便lookup查找
    idxValPairs = map (\(val, idx) -> (idx, val)) xs
    getVal t = maybe 0 id (lookup t idxValPairs)

工作逻辑： #

1. 计算所有元组中的最大索引maxIdx，确定输出列表的长度（从0到maxIdx）。
2. 将原元组(值, 索引)转换为(索引, 值)，用lookup函数查找每个索引t对应的值：找到则用该值，否则用0填充。

测试示例：

insert [(2,0),(4,5),(3,10)]  -- 输出 [2,0,0,0,0,4,0,0,0,0,3]

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