[lyah] 晕在折叠 foldl foldr
Zoom.Quiet
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
or
map' f xs = foldr (\x acc -> f x : acc) [] xs
- 那些 acc 都仅仅是代号嘛?
- 为毛特别描述:
左折叠的二元函数取累加值作首个参数，当前值为第二个参数
（即\acc x -> ...）
而右折叠的二元函数参数的顺序正好相反
（即\x acc -> ...）
- 其实,为了读者分清哈?
不然,都是 \acc x 也没有任何问题的?!
那么:
map' f xs = foldr (\x acc -> f x : acc) [] xs
:t map'
map' :: (a -> a1) -> [a] -> [a1]
等价:
let map'' f = foldr (\x acc -> f x : acc) []
:t map''
map'' :: (a -> a1) -> [a] -> [a1]
仅仅换 foldl:
let map''' f = foldl (\x acc -> f x : acc) []
:t map'''
map''' :: ([a] -> a) -> [[a]] -> [a]
嗯嗯嗯,完全不对了!
let map'''' f = foldl (\acc x -> f x : acc) []
:t map''''
map'''' :: (b -> a) -> [b] -> [a]
现在基本和 map' 一致?
调用一下:
map' (+1) [1,2,3]
[2,3,4]
map'''' (+1) [1,2,3]
[4,3,2]
不理解怎么就反序了呢? :t 出来的类型怎么看都是一致的哈,,,
map' :: (a -> a1) -> [a] -> [a1]
map'''' :: (b -> a) -> [b] -> [a]
都是說:
- 函式要两个参数,第一参数为一函式(此函式也要一个参数),第二参数为一列表
- 返回一个列表
为毛反应完全不同!?!
传说 scan 可以展现計算过程,所以:
let map''''s f = scanl (\acc x -> f x : acc) []
调用:
map's (+1) [1,2,3]
[[2,3,4],[3,4],[4],[]]
过程推导:
~ []
[1,2,3]
~ (1+1):[]
[2,3]
~ (2+1):[2]
[3]
~ (3+1):[3,2]
[]
[4,3,2]
let map's f = scanr (\x acc -> f x : acc) []
调用:
map''''s (+1) [1,2,3]
[[],[2],[3,2],[4,3,2]]
过程推导:
~ []
[1,2,3]
~ (3+1):[]
[1,2]
~ (2+1):[4]
[1]
~ (1+1):[3,4]
[]
[2,3,4]
所以?!混乱就在:
- foldl/foldr 吼的行为一样,都是从列表中逐一取值和函式进行处理
- 但是,函式接受的两个参数,是有严格不同的?!
:t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
直接使用形如: foldl (\acc x -> x+1 : acc) [] [1,2,3]
如果:
foldl (\x acc -> x+1 : acc) [] [1,2,3]
则:
<interactive>:1:18:
Occurs check: cannot construct the infinite type: a0 = [a0]
In the first argument of `(+)', namely `x'
In the first argument of `(:)', namely `x + 1'
In the expression: x + 1 : acc
类型分配失败, x 应该是个 []
也就是説: foldl :: (a -> b -> a) -> a -> [b] -> a
要这么理解::
+ 接受3个参数:
1. 要两个参数的函式,其中:
+ 第一参数为一值,从 [b] 头上依次取出
+ 第二参数为一容器,收集各次计算結果
但是! 实际使用时,必须! 要调换顺序来用!
2. 容器 a
3. 值列表 [b]
+ 运算結果堆积到 a 返回
:t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
直接使用形如: foldr (\x acc -> x+1 : acc) [] [1,2,3]
+ 接受3个参数:
1. 要两个参数的函式,其中:
+ 第一参数为一值,从 [b] 尾中依次取出
+ 第二参数为一容器,收集各次计算結果
2. 容器 b
3. 值列表 [a]
+ 运算結果堆积到 b 返回
是也乎,是也乎?! 真心特么混乱了?!
- 完全类似的名字,具体使用时,含义完全不同?!
- 哪儿有 :t 出来的类型提示,具体含义解释的?!
>> >> 在 2012年2月24日 上午11:22，Zoom.Quiet <zoom....@gmail.com> 写道：
>> >> > lyah 真心好书,代码选择,描述手法,,,没有压力的进入 FP 世界,,,
>> >> > 不过, curry 化太神奇了,俺有点转不过筋来,,,
--
人生苦短, Pythonic! 冗余不做,日子甭过!备份不做,十恶不赦!
俺: http://about.me/zoom.quiet
文字协议: http://creativecommons.org/licenses/by-sa/2.5/cn/
Zoom.Quiet
- 为毛? 无限列表的右方是无限远哈?
take 4 (foldr (\x acc -> x+1 : acc) [] [1..])
[2,3,4,5]
可是! take 4 [1..]
[1,2,3,4]
- [1..] 是自然数,从右边取,应该是无穷大哈,,,!?!?!?
yi huang
--
您收到此邮件是因为您订阅了 Google 网上论坛的"HaskellCUG"论坛。
要向此网上论坛发帖，请发送电子邮件至 haske...@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 haskellcug+...@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/haskellcug?hl=zh-CN 访问此网上论坛。
http://www.yi-programmer.com/blog/
Zoom.Quiet
> 哈哈，fold是很晕。
> 你看看这个 http://www.haskell.org/haskellwiki/Fold
> 实际使用时一般就是结果是strict的就用foldl和foldl'，lazy的就用foldr。里面参数的顺序我总记不住，用的时候查一下签名就行。
>
- 是也乎,是也乎,俺纠结的是,明明两种行为模式,为毛用如此接近的命名?!
- 签名的输出,怎么理解是精确的?!
比如:
map' :: (a -> a1) -> [a] -> [a1]
map'''' :: (b -> a) -> [b] -> [a]
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanr :: (a -> b -> b) -> b -> [a] -> [b]
?! 否则, 仅仅看錯誤输出是什么也不知道哪儿出问题了,,,
--
yi huang
在 2012年2月24日 下午4:49，yi huang <yi.cod...@gmail.com> 写道：
> 哈哈，fold是很晕。- 是也乎,是也乎,俺纠结的是,明明两种行为模式,为毛用如此接近的命名?!
> 你看看这个 http://www.haskell.org/haskellwiki/Fold
> 实际使用时一般就是结果是strict的就用foldl和foldl'，lazy的就用foldr。里面参数的顺序我总记不住，用的时候查一下签名就行。
>
- 签名的输出,怎么理解是精确的?!
比如:
map' :: (a -> a1) -> [a] -> [a1]scanl :: (a -> b -> a) -> a -> [b] -> [a]
map'''' :: (b -> a) -> [b] -> [a]
scanr :: (a -> b -> b) -> b -> [a] -> [b]
?! 否则, 仅仅看錯誤输出是什么也不知道哪儿出问题了,,,
Steps (displaying 50 max.)
foldl (+) 0 [1, 2, 3, 4] foldl (+) 0 (1 : [2, 3, 4]) foldl (+) ((+) 0 1) [2, 3, 4] foldl (+) ((+) 0 1) (2 : [3, 4]) foldl (+) ((+) ((+) 0 1) 2) [3, 4] foldl (+) ((+) ((+) 0 1) 2) (3 : [4]) foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4] foldl (+) ((+) ((+) ((+) 0 1) 2) 3) (4 : []) foldl (+) ((+) ((+) ((+) ((+) 0 1) 2) 3) 4) [] (+) ((+) ((+) ((+) 0 1) 2) 3) 4 1 + 2 + 3 + 4 3 + 3 + 4 6 + 4 10
http://hpaste.org/steps/64266
|
http://www.yi-programmer.com/blog/
yi huang
--
您收到此邮件是因为您订阅了 Google 网上论坛的"HaskellCUG"论坛。
要向此网上论坛发帖，请发送电子邮件至 haske...@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 haskellcug+...@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/haskellcug?hl=zh-CN 访问此网上论坛。
http://www.yi-programmer.com/blog/