Chinaunix

标题: [haskell] 遍历列表的一个技巧 [打印本页]

作者: retuor 时间: 2010-07-28 13:04
标题: [haskell] 遍历列表的一个技巧
本帖最后由 retuor 于 2010-07-28 13:05 编辑

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

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

代码是这样的：

g s (x:xs)= (fromIntegral(x)/fromIntegral(s): p, x+s' )
where (p, s')= g s xs
g s _ = ([], 0)
f l = l'
where (l', s) = g s l

复制代码

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

作者: boilplate 时间: 2010-07-28 21:32
其实还是两遍：计算 x + s' 一遍，返回 [x/s] 一遍

作者: retuor 时间: 2010-07-28 22:10
收集数据一次，输出一次。这样总要两次的。可以把题目所说的遍历一次理解成搜索数据一次，输出不算。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)