haskell - 在 Haskell 中自定义列表中的元素相乘

Question

我正在尝试在 Haskell 中为我的自定义列表数据类型实现自定义乘法运算，它使用 Int 和 [Int]。
Int 用于通过模数除法来减少整数，我将称为 d。
[Int]表示列表的内容

假设 a 和 b 是两个具有相同 d 的列表。
a的长度为w，b的长度为v

c = a*b 是:

c[k] = a[0] * b[k] + a[1] * b[k - 1] + a[2] * b[k - 2] + · · · + a[k] * b[0]

最后，c[k]被mod d减少。
c = w + v - 1

的长度

意味着 c[k] 中的索引 k 可以大于 w 和 v 的长度.
为了解决这个问题，我为原始列表边界之外的索引连接了一个 0 元素列表。

澄清一下:

c[0] = (a[0] * b[0]) % d  
c[1] = (a[0] * b[1] + a[1] * b[0]) % d  
c[2] = (a[0] * b[2] + a[1] * b[1] + a[2] * b[0]) % d  
.  
.  
.  
c[w + v - 1]

例如，a = [3,2,4] 和 b = [7,9,7,2]，都有 d = 31 。

在代码中，当它们相乘时，它们是 [3,2,4,0,0,0] 和 [7,9,7,2,0,0]

在这个例子中，c = a * b = [21, 10, 5, 25, 1, 8]

这是我的代码:

module Custom where

    data CustomList = CustomList Int [Int]
    instance Num CustomList where
        (CustomList a1 b1) * (CustomList a2 b2) = 
            if length b1 >= 1 && length b2 >= 1  then do 
                let llen = (length b1) + (length b2) - 1

                --concatenating a list of 0 elements for indices outside the bounds of the original list. 
                let sub_b1 = llen - (length b1)
                let sub_b2 = llen - (length b2)
                let zeros_b1 = map (0*) [1..sub_b1]
                let zeros_b2 = map (0*) [1..sub_b2]

                --matching list lengths
                let new_b1 = b1++zeros_b1
                let new_b2 = b2++zeros_b2

                --trying to mimic a nested for loop
                let ans = [ (new_b1 !! x) * (new_b2 !! y) | x <- [0..llen-1], y <- (reverse [0..x]) ]

                CustomList (a1) (map (`mod` (a1)) ans)
            else do
                0

    instance Show CustomList where
        show (CustomList a b) = "output: " ++ (show b) ++ "\nlength: " ++ (show a)

输出:

*Custom> let a = CustomList 31 [3,2,4]  
*Custom> let b = CustomList 31 [7,9,7,2]  

不正确(我得到的)

*Custom> a * b  
output: [21,18,14,28,5,28,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]  
length: 31  

正确(我应该得到的)

output: [21, 10, 5, 25, 1, 8]  
length: 6  

我意识到我的逻辑有问题:

1. x 计数器，我需要从 a[0] 开始，到 a[k] 结束所有 c [k] 计算，但我从 a[x] 开始。
2. 答案没有汇总在一起。例如，我没有获得 c[1] = a[0] * b[1] + a[1] * b[0]，而是获得了 c[1] = a[ 0] * b[1] & c[2] = a[1] * b[0]

我不确定如何修复它，我一直在尝试并最终通过尝试做来创造新的问题。

我是 Haskell 的新手，所以我更喜欢用一种简单易读的方法来解决这个问题，而不是更“Haskell”的方法。但感谢任何帮助，提前致谢。

Answer 1

漂亮而简单:

data CustomList = CustomList Int [Int] deriving(Show)

instance Num CustomList where
  CustomList a1 b1 * CustomList a2 b2 = CustomList a1 (map (`mod` a1) ans)
    where ans = map getAnsElem [1..length b1 + length b2 - 1]
          getAnsElem k = sum $ zipWith (*) (withLength k b1) (reverse $ withLength k b2)
          withLength n xs = take n (xs ++ repeat 0)

测试它:

λ> CustomList 31 [3,2,4] * CustomList 31 [7,9,7,2]
CustomList 31 [21,10,5,25,1,8]

解释:

• withLength获取一个列表并使其具有给定的长度，如果它太长则将其截断，或者如果它太短则用零填充
• zipWith获取 2 个列表并并行遍历它们，使用给定的函数组合元素
• 您的列表理解方法失败的一个原因是因为 [f x y | x <- xs, y <- ys]取 xs 的笛卡尔积和 ys而不是压缩它们。如果你想改用列表理解，你可以，但你需要 ParallelListComp扩展名，在这种情况下你会有这个:

getAnsElem k = sum [x * y | x <- withLength k b1 | y <- reverse $ withLength k b2]

注意第二个|而不是 , : 这就是压缩的意思。