Haskell 简单的重复过滤
Haskell naive duplicate filtering
我不明白以下问题的示例解决方案：给定一个元素列表，删除重复项。然后计算一个数字的唯一数字。任何一个问题都不能使用显式递归。
我的代码：
removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = foldr (\x ys -> x:(filter (x /=) ys)) []
differentDigits :: Int -> Int
differentDigits xs = length (removeDuplicates (show xs))
我试图理解的解决方案对 differentDigits 有不同的定义，即
differentDigits xs = foldr (\ _ x -> x + 1) 0 ( removeDuplicates ( filter (/= '_') ( show xs )))
这两种方法都有效，但我无法理解示例解决方案。将我的问题分解成子问题，
- 过滤器的第一个参数如何工作？我是说
(/= '_')
- foldr 的 lambda 是如何工作的？在
foldr (\ _ x -> x + 1)
^
变量x应该还是Char列表吧？ Haskell 如何计算出实际上应该递增 0？
filter (/= '_') 是，我很确定，多余的。它过滤掉下划线字符，下划线字符不应出现在 show xs 的结果中，假设 xs 是某种数字。
foldr (\ _ x -> x + 1) 0等同于length。 foldr 的工作方式是将第二个参数（在您的示例中为零）作为起点，然后对输入的每个元素一遍又一遍地应用第一个参数（在您的示例中为 lambda）列表。输入列表的元素作为第一个参数传递到 lambda（在您的示例中表示为 _），并且 运行 总和作为第二个参数传递（表示为 x）。由于 lambda 在每次传递时只是 returns 一个 "plus one" 数字，因此结果将是一个数字，表示 lambda 被调用的次数 - 这是列表的长度。
First，注意 (2) 是以所谓的 point free style 编写的，省略了 foldr 的第三个参数。
https://en.wikipedia.org/wiki/Tacit_programming#Functional_programming
此外，\_ x -> x + 1中的下划线是一个通配符，它只是标记参数的位置但不给它一个名字（通配符作为无名参数）。
Second, (2) 只是一个向右折叠的简单递归函数。 foldr 是一种编写此类递归函数的紧凑方法（在您的情况下 length）：
foldr :: (a -> b -> b) -> b -> [a]
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
如果我们写
foldr f c ls
- ls 是我们的递归函数应该在其上重复的列表（a 是元素的类型）。
- c 是 base case 中的结果（当 recursive 递归函数应用于空列表时）。
- f 计算 一般情况 的结果（当递归函数应用于非空列表时）。 f 接受两个参数：
- 列表的头部和
- 链表尾部递归调用的结果。
因此，给定 f 和 c，foldr 将递归地遍历列表 ls。
第一个例子
关于 point free style 的维基百科页面给出了我们如何使用 foldr 计算列表中所有元素总和的示例：
而不是写
sum [] = 0
sum (x:xs) = x + sum xs
我们可以写
sum = foldr (+) 0
运算符部分 (+) 是一个添加其参数的 2 参数函数。表达式
sum [1,2,3,4]
计算为
1 + (2 + (3 + (4)))
（因此 "folding to the right"）。
示例：将所有元素相乘。
而不是
prod [] = 1
prod (x:xs) = x * prod xs
我们可以写
prod = foldr (*) 1
示例：从列表中删除所有出现的值。
而不是
remove _ [] = []
remove v (x:xs) = if x==v then remove v xs else x:remove v xs
我们可以写
remove v = foldr (\x r -> if x==v then r else x:r) []
你的情况，(2)
我们现在可以完全理解
length = foldr (\ _ x -> x + 1) 0
其实和
一样
length [] = 0
length (x:xs) = length xs + 1
也就是长度函数。
希望这个关于 foldr 的递归视图能帮助您理解代码。
我不明白以下问题的示例解决方案：给定一个元素列表，删除重复项。然后计算一个数字的唯一数字。任何一个问题都不能使用显式递归。
我的代码：
removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = foldr (\x ys -> x:(filter (x /=) ys)) []
differentDigits :: Int -> Int
differentDigits xs = length (removeDuplicates (show xs))
我试图理解的解决方案对 differentDigits 有不同的定义，即
differentDigits xs = foldr (\ _ x -> x + 1) 0 ( removeDuplicates ( filter (/= '_') ( show xs )))
这两种方法都有效，但我无法理解示例解决方案。将我的问题分解成子问题，
- 过滤器的第一个参数如何工作？我是说
(/= '_')
- foldr 的 lambda 是如何工作的？在
foldr (\ _ x -> x + 1)
^
变量x应该还是Char列表吧？ Haskell 如何计算出实际上应该递增 0？
filter (/= '_')是，我很确定，多余的。它过滤掉下划线字符，下划线字符不应出现在show xs的结果中，假设xs是某种数字。foldr (\ _ x -> x + 1) 0等同于length。foldr的工作方式是将第二个参数（在您的示例中为零）作为起点，然后对输入的每个元素一遍又一遍地应用第一个参数（在您的示例中为 lambda）列表。输入列表的元素作为第一个参数传递到 lambda（在您的示例中表示为_），并且 运行 总和作为第二个参数传递（表示为x）。由于 lambda 在每次传递时只是 returns 一个 "plus one" 数字，因此结果将是一个数字，表示 lambda 被调用的次数 - 这是列表的长度。
First，注意 (2) 是以所谓的 point free style 编写的，省略了 foldr 的第三个参数。
https://en.wikipedia.org/wiki/Tacit_programming#Functional_programming
此外，\_ x -> x + 1中的下划线是一个通配符，它只是标记参数的位置但不给它一个名字（通配符作为无名参数）。
Second, (2) 只是一个向右折叠的简单递归函数。 foldr 是一种编写此类递归函数的紧凑方法（在您的情况下 length）：
foldr :: (a -> b -> b) -> b -> [a]
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
如果我们写
foldr f c ls
- ls 是我们的递归函数应该在其上重复的列表（a 是元素的类型）。
- c 是 base case 中的结果（当 recursive 递归函数应用于空列表时）。
- f 计算 一般情况 的结果（当递归函数应用于非空列表时）。 f 接受两个参数：
- 列表的头部和
- 链表尾部递归调用的结果。
因此，给定 f 和 c，foldr 将递归地遍历列表 ls。
第一个例子 关于 point free style 的维基百科页面给出了我们如何使用 foldr 计算列表中所有元素总和的示例：
而不是写
sum [] = 0
sum (x:xs) = x + sum xs
我们可以写
sum = foldr (+) 0
运算符部分 (+) 是一个添加其参数的 2 参数函数。表达式
sum [1,2,3,4]
计算为
1 + (2 + (3 + (4)))
（因此 "folding to the right"）。
示例：将所有元素相乘。
而不是
prod [] = 1
prod (x:xs) = x * prod xs
我们可以写
prod = foldr (*) 1
示例：从列表中删除所有出现的值。
而不是
remove _ [] = []
remove v (x:xs) = if x==v then remove v xs else x:remove v xs
我们可以写
remove v = foldr (\x r -> if x==v then r else x:r) []
你的情况，(2)
我们现在可以完全理解
length = foldr (\ _ x -> x + 1) 0
其实和
一样length [] = 0
length (x:xs) = length xs + 1
也就是长度函数。
希望这个关于 foldr 的递归视图能帮助您理解代码。