如何在fold中控制列表元素索引？Haskell多项式转换实现求助

首先，你的代码存在几个核心问题：

• 错误地用length l作为所有项的次数，而每个元素的次数应该是它在列表中的索引
• foldl的lambda参数顺序颠倒（foldl的累加器是第一个参数，当前元素是第二个）
• 未过滤系数为0的项（这类项通常不需要保留在多项式中）

如何在Fold中获取列表元素的索引 #

要在fold操作中获取元素的索引，最直接的方法是用zip [0..]将列表元素与对应的索引（从0开始）配对。比如zip [0..] [6,1,0,3]会生成[(0,6), (1,1), (2,0), (3,3)]，这样每个元素都携带了自己的次数信息，fold时就能同时拿到次数和系数。

正确的list2Pol实现 #

结合fold操作，我们可以按以下步骤实现：

1. 将列表元素与索引配对，得到(次数, 系数)的元组列表
2. 过滤掉系数为0的项
3. 将元组列表按次数从高到低排序（或反转原配对列表，因为zip [0..]生成的是次数递增的序列）
4. 用foldr构造多项式结构（因为我们需要最高次项作为最外层节点）

代码实现如下：

-- 先明确类型别名（可选，但让代码更清晰）
type Grade = Int
type Coefficient = Integer
data Pol = Nil | P Grade Coefficient Pol deriving Show

list2Pol :: [Integer] -> Pol
list2Pol = foldr buildTerm Nil
         . filter (\(_, coeff) -> coeff /= 0)
         . reverse
         . zip [0..]
  where buildTerm (deg, coeff) acc = P deg coeff acc

代码解释 #

• zip [0..]：为每个列表元素绑定对应的次数（索引）
• reverse：将次数递增的序列转为递减，确保最高次项排在最前面
• filter：移除系数为0的无用项
• foldr buildTerm Nil：从右到左折叠，用每个(次数,系数)元组构造多项式节点，最终生成嵌套结构

测试你的示例：

list2Pol [6,1,0,3] -- 返回 P 3 3 (P 1 1 (P 0 6 Nil))

如果你不想用reverse，也可以用sortBy显式按次数降序排序，需要导入Data.List和Data.Ord：

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

list2Pol :: [Integer] -> Pol
list2Pol = foldr buildTerm Nil
         . filter (\(_, coeff) -> coeff /= 0)
         . sortBy (flip (comparing fst))
         . zip [0..]
  where buildTerm (deg, coeff) acc = P deg coeff acc

内容的提问来源于stack exchange，提问作者j.j.3