Haskell如何实现适配无限列表的长度<3子列表求和功能
问题原因
原实现无法处理无限子列表的核心问题是调用了length函数判断子列表长度:length会完整遍历整个列表才能返回结果,遇到无限列表时会一直遍历无法终止,哪怕我们只需要知道列表长度是否小于3。
原逻辑的判定规则不需要获取子列表的精确长度,只需要确认子列表元素个数是否小于3:只要子列表元素够3个,不管后面还有多少内容(哪怕无限多),都直接过滤掉,不需要继续遍历剩余元素。
修改后代码
sumsOf :: Num a => [[a]] -> [a] sumsOf = map sum . filter isShortList where -- 仅检查前3个元素即可完成判定,不会触发无限列表的全量遍历 isShortList (_:_:_:_) = False -- 能匹配到至少3个元素,判定为长列表直接过滤 isShortList _ = True -- 剩余情况都是长度0/1/2的短列表,保留求和
实现说明
- 用模式匹配代替
length做长度判断,每个子列表最多只会被检查前3个元素:- 碰到无限长的子列表时,取到前3个元素就会直接判定为长列表,终止对这个子列表的遍历,不会卡死
- 长度小于3的有限子列表会正常匹配,不会出现漏判
- 所有场景行为完全符合预期:
- 纯有限列表输入和原实现运行结果完全一致
- 全是无限子列表的输入会直接返回空列表,不会陷入死循环
- 长短列表、无限列表混合的场景会正确跳过长度≥3的子列表(包括无限子列表),对剩余短列表求和
内容的提问来源于stack exchange,提问作者teki2021
相关产品推荐
相关产品推荐

