阅读(解释)此功能性 Miranda 代码时遇到问题。
g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])
我知道它的作用
- 通过获取长度来计算列表的大小
#
- 创建一个包含上述原始输入列表长度的单元素列表
- 使用对每个元素的操作将新列表折叠
foldr
成单个整数+0
但是我被括号弄糊涂了,看不到输入列表的输入位置。最右边的[]
构造函数是做什么的?
另外为什么这段代码只能通过函数g工作,但如果我直接调用它会抛出错误?
阅读(解释)此功能性 Miranda 代码时遇到问题。
g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])
我知道它的作用
#
foldr
成单个整数+0
但是我被括号弄糊涂了,看不到输入列表的输入位置。最右边的[]
构造函数是做什么的?
另外为什么这段代码只能通过函数g工作,但如果我直接调用它会抛出错误?
简而言之,g
就是一个返回列表长度的函数。
让我们把函数分解成几个部分。
|| returns 1 for any input.
|| return_one "hoobar" = 1
return_one :: * -> num
return_one = (#) . (:[])
|| ignore first argument, insert 1 to the second argument.
|| insert_one "hoobar" [4,5,6] = [1,4,5,6]
insert_one :: *->[num]->[num]
insert_one = (:) . return_one
|| sum of list.
|| sum_list [7,8,9] = 24
sum_list :: [num] -> num
sum_list = foldr (+) 0
|| generate list of 1 which as the same length of original list.
|| change_one ["apple","banana"] = [1,1]
change_one :: [*] -> [num]
change_one = foldr insert_one []
|| return the length of the list.
|| g ["apple","banana"] = 2
g :: [*] -> num
g = sum_list . change_one
我会解释一些令人困惑的功能。
(:[])
是一个创建单个元素列表并(#)
返回长度的函数。严格来说,是(:[])
作为第一个参数。(:)
[]
因此(:[]) "hoobar" = "hoobar":[] = ["hoobar"]
, 并应用(#)
到它返回 1。
它从空列表开始,[]
并通过在前面插入 1 来遍历列表。
foldr insert_one [] ["apple","banana"]
= foldr insert_one [1] ["apple"]
= foldr insert_one [1,1] []
我不太了解米兰达,但基于 Haskell(我相信这里两者之间的差异很小,只有#
作为列表长度的一元运算符是唯一的半重要运算符并且||
是注释语法) : .
is 函数组成:
(p . q) x = p (q x)
|| also can be written as:
p . q = \x -> p (q x)
函数组合是一个关联操作,所以p . (q . r)
= (p . q) . r
= p . q . r
。
使用此信息,我们可以使用以下定义扩展它.
:
g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) []) || Original definition
g list = foldr (+) 0 (foldr ((:) . ((#) . (:[]))) [] list)
g list = foldr (+) 0 (foldr (\x -> (:) (((#) . (:[])) x)) [] list)
g list = foldr (+) 0 (foldr (\x -> (:) ((\y -> (#) ((:[]) y)) x)) [] list)
这可以清理更多:
g list = foldr (+) 0 (foldr (\x -> (:) ((\y -> (#)(y:[])) x)) [] list) || More conventional operator syntax for the innermost `:`
g list = foldr (+) 0 (foldr (\x -> (:) ((#)(x:[]))) [] list) || Innermost lambda was applied to x. Substitute y for x.
g list = foldr (+) 0 (foldr (\x -> (:) ((#)([x]))) [] list) || Apply innermost `:`
g list = foldr (+) 0 (foldr (\x -> (:) #[x])) [] list) || Remove unnecessary parentheses
g list = foldr (+) 0 (foldr (\x acc -> (:) (#[x]) acc) [] list) || Explicitly write implicit argument. This particular step is called eta-expansion
g list = foldr (+) 0 (foldr (\x acc -> (:) 1 acc) [] list) || #[x] is always 1, no matter what x is
g list = foldr (+) 0 (foldr (\x acc -> 1 : acc) [] list) || More conventional syntax for `:`
另请注意,正如您在问题中所述,这foldr
并不适用于每个元素。变成(是另一种写法)。我一直认为这张图有助于理解:+0
foldr op z (a:b:c:[])
op a (op b (op c z)))
a:b:c:[]
[a,b,c]
p . q x
此外,直接调用它时出错的原因很可能与(p . q) x
.