如何对两个列表的元素求和。 Haskell
How to sum elements of two lists. Haskell
我才刚刚开始学习Haskell,目前我正在探索列表的可能性。
本来想总结两张单子的,结果莫名其妙出错了
所以:
输入:sumTwoLists [2,5,7,7,9] [1,2,2](基本上是25779 + 122)
输出:[2,5,9,0,1]
首先我把整个表倒过来了,因为多位数的加法必须从末尾开始:
reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]
有效。然后我实现了一个add函数:
add :: (Num a) => [a] -> [a] -> [a]
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys
但是当一个列表比另一个短时,它就会出错。 (添加 [2,5,7,7,9] [1,2,2] = [3,7,9])
所以 finction 也必须在较低数字的末尾添加 0 ([1,2,2] = [1,2,2,0,0].)
然后我尝试像这样实现 sumTwoLists 函数:
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists (x:xs) (y:ys) = reverseList ((reverseList (x:xs)) add (reverseList (y:ys)))
但是这段代码没有考虑到元素不能大于9的事实。
我不想将元素转换为 Int 或 Integer,这就是我不使用它们的原因。
我基本上只是想反转列表,然后在最短列表中添加 0,然后将每个元素与另一个列表中的元素相加,如果结果 >9,则结果除以 10 ( mod?)并且相邻的数字增加
如有任何帮助,我将不胜感激!
这是以 10 为基数的 adic 和。这是一个实现。
-- odometer (add one in base b)
odom :: Int -> [Int] -> [Int]
odom b (x : xs) | x<(b-1) = (x+1) : xs
| xs==[] = [0,1]
| otherwise = 0 : odom b xs
-- iterated odometer
odom_iter :: Int -> [Int] -> Int -> [Int]
odom_iter b t n | n == 0 = t
| otherwise = odom b (odom_iter b t (n-1))
-- adic addition
sumadic :: Int -> [Int] -> [Int] -> [Int]
sumadic b (x:xs) (y:ys) | xs == [] = odom_iter b (y:ys) x
| ys == [] = odom_iter b (x:xs) y
| sumxy < b = (sumxy : (sumadic b xs ys))
| sumxy == b = (0 : (odom b (sumadic b xs ys)))
| otherwise = (1 : (odom b (sumadic b xs ys)))
where sumxy = x+y
这通过反转列表来实现:
> sumadic 10 [9, 7, 7, 5, 2] [2, 2, 1]
[1,0,9,5,2]
因此您只需将 sumadic
应用于反转列表并反转输出:
sumTwoLists x y = reverse $ sumadic 10 (reverse x) (reverse y)
用列表做这个没有多大意义,因为它会引入很多额外的问题:
- 如果两个列表的长度不同,或者求和需要额外的元素,则用零填充;和
- 考虑到将两位数字相加可能会产生大于
9
的值,因此引入了 进位。
add
函数无法正常工作,因为它会在其中一个列表用完时停止,而且它没有考虑到数字可能会“溢出”。因此,我们应该构造一个函数 add
,它有一个额外的参数:进位:
add' :: Int -> [Int] -> [Int] -> [Int]
add' 0 [] [] = []
add' n [] [] = [n]
add' n xs [] = add' n xs [0]
add' n [] xs = add' n [0] xs
add' n (x:xs) (y:ys) = r : add' q xs ys
where (q,r) = quotRem (x+y+n) 10
add
因此从零开始作为进位:
add :: [Int] -> [Int] -> [Int]
add = add' 0
如果我们这样计算反转列表的总和,我们得到:
Prelude> add [9,7,7,5,2] [2,2,1]
[1,0,9,5,2]
为了让它工作,你需要使用 add
作为中缀运算符,并且两个操作数可以是空或非空列表:
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists xs ys = reverseList ((reverseList xs) <b>`add`</b> (reverseList ys))
或 on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
:
import Data.Function(on)
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists = add <b>`on`</b> reverse
对于给定的样本输入,我们现在得到:
Prelude> sumTwoLists [2,5,7,7,9] [1,2,2]
[2,5,9,0,1]
最后 reverseList
已经存在于 Prelude
中:reverse :: [a] -> [a]
。你实现的reverseList
函数运行在O(n2),效率不是很高,可以用累加器求线性时间。
此答案将使用 Haskell 的内置 reverse
而不是您的 reverseList
,尽管它们可以互换。
让我们先看看您的添加函数:
add :: (Num a) => [a] -> [a] -> [a]
-- look at these next 2 lines specfically
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys
如果您将非空列表添加到空列表,您当前的代码会说它是空列表,这显然不是真的(add [1, 2, 3] []
应该是 [1, 2, 3]
) .因此,您可以首先通过返回另一个列表来修复您的基本情况:
add :: (Num a) => [a] -> [a] -> [a]
-- return the other list
add [] x = x
add x [] = x
add (x:xs) (y:ys) = (x + y) : add xs ys
如果您 添加了两个空列表,那么另一个列表就是空列表,因此您仍然正确地返回了空列表。现在,我们可以解决“这段代码没有考虑元素不能大于 9 的事实”部分。因为你的加法是模拟你在笔和纸上做加法的方式,所以继续这样做。例如,如果结果为 12,则数字为 2,进位 1。请记住,mod 是除法的余数,因此 12 `mod` 10
(backticks in Haskell makes a function infix) 是 2
,而 12 `div` 10
,由于整数除法向下舍入的性质,将为您提供第一个数字后的每个数字,即 1
.
废话少说,让我们来写点代码吧:
-- change Num to Integral because we need to work with integers
add :: (Integral a) => [a] -> [a] -> a -> [a]
-- we need to add a carry now ^
-- these base cases break down if carry is non-zero
add [] x c
-- if carry is zero we're fine
| c == 0 = x
-- just add the carry in as a digit
| otherwise = add [c] x 0
-- same applies here
add x [] c
| c == 0 = x
| otherwise = add x [c] 0
add (x:xs) (y:ys) c = dig : add xs ys rst
where sum = x + y + c -- find the sum of the digits plus the carry
-- these two lines can also be written as (rst, dig) = sum `divMod` 10
dig = sum `mod` 10 -- get the last digit
rst = sum `div` 10 -- get the rest of the digits (the new carry)
现在,您的辅助函数只需将 0 作为初始进位即可调用它:
addTwoLists :: (Num a) => [a] -> [a] -> [a]
addTwoLists x y = reverse $ add (reverse x) (reverse y) 0
我才刚刚开始学习Haskell,目前我正在探索列表的可能性。 本来想总结两张单子的,结果莫名其妙出错了
所以:
输入:sumTwoLists [2,5,7,7,9] [1,2,2](基本上是25779 + 122)
输出:[2,5,9,0,1]
首先我把整个表倒过来了,因为多位数的加法必须从末尾开始:
reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]
有效。然后我实现了一个add函数:
add :: (Num a) => [a] -> [a] -> [a]
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys
但是当一个列表比另一个短时,它就会出错。 (添加 [2,5,7,7,9] [1,2,2] = [3,7,9]) 所以 finction 也必须在较低数字的末尾添加 0 ([1,2,2] = [1,2,2,0,0].)
然后我尝试像这样实现 sumTwoLists 函数:
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists (x:xs) (y:ys) = reverseList ((reverseList (x:xs)) add (reverseList (y:ys)))
但是这段代码没有考虑到元素不能大于9的事实。 我不想将元素转换为 Int 或 Integer,这就是我不使用它们的原因。
我基本上只是想反转列表,然后在最短列表中添加 0,然后将每个元素与另一个列表中的元素相加,如果结果 >9,则结果除以 10 ( mod?)并且相邻的数字增加
如有任何帮助,我将不胜感激!
这是以 10 为基数的 adic 和。这是一个实现。
-- odometer (add one in base b)
odom :: Int -> [Int] -> [Int]
odom b (x : xs) | x<(b-1) = (x+1) : xs
| xs==[] = [0,1]
| otherwise = 0 : odom b xs
-- iterated odometer
odom_iter :: Int -> [Int] -> Int -> [Int]
odom_iter b t n | n == 0 = t
| otherwise = odom b (odom_iter b t (n-1))
-- adic addition
sumadic :: Int -> [Int] -> [Int] -> [Int]
sumadic b (x:xs) (y:ys) | xs == [] = odom_iter b (y:ys) x
| ys == [] = odom_iter b (x:xs) y
| sumxy < b = (sumxy : (sumadic b xs ys))
| sumxy == b = (0 : (odom b (sumadic b xs ys)))
| otherwise = (1 : (odom b (sumadic b xs ys)))
where sumxy = x+y
这通过反转列表来实现:
> sumadic 10 [9, 7, 7, 5, 2] [2, 2, 1]
[1,0,9,5,2]
因此您只需将 sumadic
应用于反转列表并反转输出:
sumTwoLists x y = reverse $ sumadic 10 (reverse x) (reverse y)
用列表做这个没有多大意义,因为它会引入很多额外的问题:
- 如果两个列表的长度不同,或者求和需要额外的元素,则用零填充;和
- 考虑到将两位数字相加可能会产生大于
9
的值,因此引入了 进位。
add
函数无法正常工作,因为它会在其中一个列表用完时停止,而且它没有考虑到数字可能会“溢出”。因此,我们应该构造一个函数 add
,它有一个额外的参数:进位:
add' :: Int -> [Int] -> [Int] -> [Int]
add' 0 [] [] = []
add' n [] [] = [n]
add' n xs [] = add' n xs [0]
add' n [] xs = add' n [0] xs
add' n (x:xs) (y:ys) = r : add' q xs ys
where (q,r) = quotRem (x+y+n) 10
add
因此从零开始作为进位:
add :: [Int] -> [Int] -> [Int]
add = add' 0
如果我们这样计算反转列表的总和,我们得到:
Prelude> add [9,7,7,5,2] [2,2,1]
[1,0,9,5,2]
为了让它工作,你需要使用 add
作为中缀运算符,并且两个操作数可以是空或非空列表:
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists xs ys = reverseList ((reverseList xs) <b>`add`</b> (reverseList ys))
或 on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
:
import Data.Function(on)
sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists = add <b>`on`</b> reverse
对于给定的样本输入,我们现在得到:
Prelude> sumTwoLists [2,5,7,7,9] [1,2,2]
[2,5,9,0,1]
最后 reverseList
已经存在于 Prelude
中:reverse :: [a] -> [a]
。你实现的reverseList
函数运行在O(n2),效率不是很高,可以用累加器求线性时间。
此答案将使用 Haskell 的内置 reverse
而不是您的 reverseList
,尽管它们可以互换。
让我们先看看您的添加函数:
add :: (Num a) => [a] -> [a] -> [a]
-- look at these next 2 lines specfically
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys
如果您将非空列表添加到空列表,您当前的代码会说它是空列表,这显然不是真的(add [1, 2, 3] []
应该是 [1, 2, 3]
) .因此,您可以首先通过返回另一个列表来修复您的基本情况:
add :: (Num a) => [a] -> [a] -> [a]
-- return the other list
add [] x = x
add x [] = x
add (x:xs) (y:ys) = (x + y) : add xs ys
如果您 添加了两个空列表,那么另一个列表就是空列表,因此您仍然正确地返回了空列表。现在,我们可以解决“这段代码没有考虑元素不能大于 9 的事实”部分。因为你的加法是模拟你在笔和纸上做加法的方式,所以继续这样做。例如,如果结果为 12,则数字为 2,进位 1。请记住,mod 是除法的余数,因此 12 `mod` 10
(backticks in Haskell makes a function infix) 是 2
,而 12 `div` 10
,由于整数除法向下舍入的性质,将为您提供第一个数字后的每个数字,即 1
.
废话少说,让我们来写点代码吧:
-- change Num to Integral because we need to work with integers
add :: (Integral a) => [a] -> [a] -> a -> [a]
-- we need to add a carry now ^
-- these base cases break down if carry is non-zero
add [] x c
-- if carry is zero we're fine
| c == 0 = x
-- just add the carry in as a digit
| otherwise = add [c] x 0
-- same applies here
add x [] c
| c == 0 = x
| otherwise = add x [c] 0
add (x:xs) (y:ys) c = dig : add xs ys rst
where sum = x + y + c -- find the sum of the digits plus the carry
-- these two lines can also be written as (rst, dig) = sum `divMod` 10
dig = sum `mod` 10 -- get the last digit
rst = sum `div` 10 -- get the rest of the digits (the new carry)
现在,您的辅助函数只需将 0 作为初始进位即可调用它:
addTwoLists :: (Num a) => [a] -> [a] -> [a]
addTwoLists x y = reverse $ add (reverse x) (reverse y) 0