我有一個函式prefixes，給定[1, 2, 3]，回傳 prefixes [[1], [1, 2], [1, 2, 3]]。定義如下：
prefixes :: Num a => [a] -> [[a]]
prefixes = foldr (\x acc -> [x] : (map ((:) x) acc)) []
我花了將近兩天的時間試圖理解為什么會這樣。當我在腦海中除錯它時，我想這是為了prefixes [1, 2, 3]：
foldr call|__________________________________________________________________________
1 | [1] : (map ((:) 1) [])
|
| where x = 1 and acc = []
| returns acc = [[1]]
|
2 | [2] : (map ((:) 2) [[1]])
|
| where x = 2 and acc = [[1]]
| and (map ((:) 2) [[1]])
| returns acc = [[1, 2]]
| and [2] : [[1, 2]]
| returns [[2], [1, 2]]
|
3 | [3] : (map ((:) 3) [[2], [1, 2]])
|
| where x = 3 and acc = [[2], [1, 2]]
| and (map ((:) 3) [[2], [1, 2]])
| returns acc = [[2, 3], [1, 2, 3]]
| and [3] : [[2, 3], [1, 2, 3]]
| returns [[3], [2, 3], [1, 2, 3]]
|
然后函式終止并回傳[[3], [2, 3], [1, 2, 3]]。但顯然這并沒有發生。它回傳[[1], [1, 2], [1, 2, 3]]。
在 Ghci 中，我發現：
Stopped in Main.prefixes, ex.hs:21:20-63
_result :: [a] -> [[a]] = _
[ex.hs:21:20-63] *Main> :step
Stopped in Main.prefixes, ex.hs:21:37-59
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 1
[ex.hs:21:37-59] *Main> :step
[[1]
Stopped in Main.prefixes, ex.hs:21:44-58
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 1
[ex.hs:21:44-58] *Main> :step
Stopped in Main.prefixes, ex.hs:21:37-59
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 2
[ex.hs:21:37-59] *Main> :step
,
Stopped in Main.prefixes, ex.hs:21:49-53
_result :: [Integer] -> [Integer] = _
x :: Integer = 1
[ex.hs:21:49-53] *Main> :step
[1,2]
Stopped in Main.prefixes, ex.hs:21:44-58
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 2
[ex.hs:21:44-58] *Main> :step
Stopped in Main.prefixes, ex.hs:21:37-59
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 3
[ex.hs:21:37-59] *Main> :step
,
[1Stopped in Main.prefixes, ex.hs:21:49-53
_result :: [Integer] -> [Integer] = _
x :: Integer = 2
[ex.hs:21:49-53] *Main> :step
,2,3]
Stopped in Main.prefixes, ex.hs:21:44-58
_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 3
[ex.hs:21:44-58] *Main> :step
]
我將其解釋為：
__lines___|__________________________________________________________________________
21:37-59 | [1] : (map ((:) 1) acc) -> [[1]
|
|
|
21:44-58 | (map ((:) 1) acc) -> does nothing, as acc = []
|
|
|
21:37-59 | [2] : (map ((:) 2) acc) -> ,
|
|
|
21:49-53 | ((:) 1) -> [1, 2]
|
|
|
21:44-58 | (map ((:) 2) acc) -> outputs nothing
|
|
|
21:37-59 | [3] : (map ((:) 3) acc) -> ,[1
|
|
|
21:49-53 | ((:) 2) -> , 2, 3]
|
|
21:44-58 | (map ((:) 3) acc) -> ]
|
印刷[[1], [1, 2], [1, 2, 3]]。有人可以解釋為什么在評估第 49-53 行時，xx 值是來自上一次foldr呼叫嗎？
我知道(map ((:) x) acc)可以擴展為(foldr ((:) . ((:) x)) [] acc), as map f = foldr ((:) . f) []。所以我將函式重寫為以下
prefixesSolution :: Num a => [a] -> [[a]]
prefixesSolution = foldr (\x acc -> [x] : (foldr ((:) . ((:) x)) [] acc)) []
And this works as well. Now, the lambda passed to the second foldr ((:) . ((:) x)) I would imagine could be refactored as (\ element accumulator -> (element:accumulator) . ((element:accumulator) x)). But this does not work: Couldn't match expected type ‘a -> a0 -> b0’ with actual type ‘[[a]]’. All this I have done in order to pinpoint exactly what is happening.
I also do not understand the function passed to map ((:) x).
I apologize for how convoluted this post is. At this point I don't even know what I don't know. If someone could clearly walk me through this function I would be so so grateful.
uj5u.com熱心網友回復：
foldr從串列的末尾開始累積。
最初acc = []（使用 的第二個引數foldr）。
從最后開始，我們將給定的函式\x acc -> [x] : (map ((:) x) acc)應用于x = 3：
[3] : map (3 :) []
= [[3]]
使用acc = [[3]]，添加前面的元素，x = 2：
[2] : map (2 :) [[3]]
= [[2], [2,3]]
使用acc = [[2], [2,3]]，添加前面的元素，x = 1：
[1] : map (1 :) [[2], [2,3]]
= [[1], [1,2], [1,2,3]]
您仍然可以評估foldr“從左到右”，但在這種情況下，請記住acc使用“下一個遞回呼叫”來實體化。
foldr f b (x : xs) = f x (foldr f b xs)
prefixes [1,2,3]
= [1] : map (1 :) (prefixes [2,3]) -- acc = prefixes [2,3], the next recursive call
= [1] : map (1 :) ([2] : map (2 :) (prefixes [3]))
...
uj5u.com熱心網友回復：
從關于傳遞給 map 的函式的問題開始：
在 Haskell 中，所有的運算子也是函式。就其本身而言，:是串列構造（“cons”）運算子：
1 : [2,3] -- > [1,2,3]
如果你在它周圍加上括號，它就變成了一個前綴函式而不是一個中綴運算子：
(:) 1 [2,3] -- > [1,2,3]
當您記得 Haskell 函式應用程式是 curried 時，您可以看到它(:) 1必然是一個將 1 附加到串列的函式：
f = (:) 1
f [2,3] -- > [1,2,3]
所以傳遞給的函式map是一個將串列作為其引數并將x（來自 的當前項foldr）添加到該串列的函式。
周圍的函式在[x]that 的結果之前map，增加了串列。
接下來說說foldr自己。將串列 [1,2,3] 視為創建它所需的 cons 呼叫序列可能會有所幫助。以如下所示的樹形形式：
(:)
1 (:)
2 (:)
3 []
在 Haskell 中，你可以這樣寫：
(:) 1 ( (:) 2 ( (:) 3 [] ) )
鑒于上述情況，呼叫foldr func init [1,2,3]所做的是將 final 替換[]為initvalue 并將所有(:)s 替換為提供的func。所以最終的結果和這個運算式的結果是一樣的，你可以把它看作是foldr版本的擴展：
func 1 ( func 2 ( func 3 init ) )
That is, foldr first calls the func on 3 (which becomes x) and [] (which becomes acc). (Technically, it calls the function on 3, and the result of that call is another function that it then calls on [], but that's just how function application works in Haskell; the difference is not important to this particular discussion.) Then it calls the func on 2 and the result of the first call, and then it calls it on 1 and the result of the second call.
As we established above, the func first does a map ((:) 3) [] - returning [], since mapping anything across the empty list just returns the empty list - and prepends [3] to the result, giving [[3]].
然后它在 2 和 上呼叫函式[[3]]。映射回傳[[2,3]]，它預先設定[2]，產生[[2],[2,3]]。
最后它在 1 和 上呼叫函式[[2],[2,3]]。映射回傳[[1,2],[1,2,3]]，函式[1]添加到它前面，產生最終的答案[[1],[1,2],[1,2,3]]。
uj5u.com熱心網友回復：
在手動評估某些東西時prefixes [1,2,3]，您應該非常小心地寫出評估的每個步驟。
我會這樣看：
在我們開始之前，我建議幾個準備步驟。我也會給變數新的名字，希望能讓事情更清楚。
將模式匹配寫成case運算式會有所幫助，所以我們接下來會這樣做。
我們可以觀察到foldr可以寫成
foldr f z list =
case list of
[] -> z
(y:ys) -> f y (foldr f z ys)
稍后我將跳過特定map應用程式的一些細節，更多地關注這些foldr步驟。如果不清楚，我可以進一步擴展。
既然我們已經解決了這個問題，我們就可以進行評估了。我不會過多關注評估順序，因為這不會影響最終結果。這將使我簡化一些事情。因此，您不必假設這正是計算機正在執行的操作（即使此處的結果相同，但在記憶體效率、時間效率和可能的嚴格性屬性方面可能存在差異）。
prefixes [1,2,3]
==> {definition of prefixes}
foldr (\x acc -> [x] : (map ((:) x) acc)) [] [1,2,3]
==> {definition of foldr}
let f = \x acc -> [x] : (map ((:) x) acc)
in
case [1,2,3] of
[] -> []
(y:ys) -> f y (foldr f [] ys)
==> {reduce case match on known value}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (foldr f [] [2,3])
==> {definition of foldr}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (case [2,3] of
[] -> []
(y:ys) -> f y (foldr f [] ys))
==> {reduce case match on known value}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 (foldr f [] [3]))
==> {definition of foldr}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 (case [3] of
[] -> []
(y:ys) -> f y (foldr f [] ys)))
==> {reduce case match on known value}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 (f 3 (foldr f [] [])))
==> {definition of foldr}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 (f 3 (case [] of
[] -> []
(y:ys) -> f y (foldr f [] ys))))
==> {reduce case match on known value}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 (f 3 []))
==> {apply f}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 ([3] : map ((:) 3) []))
==> {apply map}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 ([3] : []))
==> {list sugar}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 (f 2 [[3]])
==> {apply f}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 ([2] : map ((:) 2) [[3]])
==> {apply map}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 ([2] : [((:) 2) [3]])
==> {list sugar}
let f = \x acc -> [x] : (map ((:) x) acc)
in
f 1 [[2], [2,3]]
==> {apply f}
[1] : map ((:) 1) [[2], [2,3]]
==> {apply map}
[1] : [((:) 1) [2], ((:) 1) [2,3]]
==> {list sugar}
[1] : [[1,2], [1,2,3]]
==> {list sugar}
[[1], [1,2], [1,2,3]]
This is the general process can be used to understand the result obtained from evaluating expressions. Note that every step is a valid Haskell expression that behaves identically to the original expression. Essentially, I just expanded definitions, reduced case expressions when the case is matching on a (:) ... ... or a [], applied functions (using beta-reduction) and introduced some syntactic sugar for lists to make things a bit easier to read in parts. Those kinds of steps already cover a significant portion of the tools you need to reduce most Haskell expressions by hand.
A very similar process can also be used for equational reasoning, which can be used as a systematic technique to optimize Haskell programs. It works by replacing expressions with other expressions that always give the same result but could have different efficiency characteristics. Essentially anything written by Richard Bird will provide examples of equational reasoning, among others.
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/446074.html
上一篇：型別級約束編碼