[haskell] 遍历列表的一个技巧

Question

本帖最后由 retuor 于 2010-07-28 13:05 编辑

本来是遍历树的，我把它简化成遍历列表了，本质一样的。

题目：有个整数列表 [a,b,c,...,z]，s 为全部元素的和，把这个列表转换成 [a/s, b/s, ...., z/s]. 要求只遍历一次。

代码是这样的：

2. g s (x:xs)=  (fromIntegral(x)/fromIntegral(s): p, x+s' )
3.     where (p, s')= g s xs
5. g s _ = ([], 0)
7. f l = l'
8.     where (l', s) = g s l

复制代码它是按 a/s: (b/s) : .... : [] 来构造输出的，这种方法在函式编程里太常见了。不同寻常的地方是，那些 a/s, b/s 的值开始的时候是不确定的，直到把链表遍历完成时，才得到 s 的值。

Answer 1

收集数据一次，输出一次。这样总要两次的。可以把题目所说的遍历一次理解成搜索数据一次，输出不算。

Answer 2

其实还是两遍：  计算 x + s' 一遍， 返回  [x/s] 一遍