Haskell中不使用length函数实现indexList递归函数的方法

你需要实现的indexList函数要求递归生成元素到列表末尾距离的元组，且不能使用length函数。原代码的问题在于无法直接获取后续子列表的长度（也就是当前元素到末尾的距离），可以通过引入辅助递归函数来解决——这个辅助函数同时返回处理后的列表和对应子列表的长度，正好满足需求。

完整实现代码如下：

indexList :: [a] -> [(Int, a)]
indexList xs = fst (helper xs)
  where
    helper [] = ([], 0)
    helper (x : xs) =
      let (processedRest, restLength) = helper xs
      in ((restLength, x) : processedRest, restLength + 1)

代码解释 #

• 辅助函数helper返回一个元组：第一个元素是处理完成的带距离的列表，第二个元素是当前子列表的长度（恰好是当前子列表第一个元素到末尾的距离）。
• 处理空列表时，返回空列表和长度0，作为递归的终止条件。
• 处理非空列表x : xs时：
  1. 先递归处理子列表xs，得到processedRest（xs的最终处理结果）和restLength（xs的长度，也就是元素x到列表末尾的距离）。
  2. 将(restLength, x)添加到processedRest的头部，同时更新长度为restLength + 1（因为当前列表比xs多了一个元素x）。

测试用例验证：indexList [True, False, True]会返回[(2, True), (1, False), (0, True)]，完全符合预期。

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