Умножение элементов в пользовательских списках в Haskell

Question

Я пытаюсь реализовать пользовательскую операцию умножения для моего типа данных пользовательского списка в Haskell, в котором используются Int и [Int].
Int используется для уменьшения целых чисел путем деления на модули. to as 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

Значение индекса k в c[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  

Я понимаю проблемы в моей логике c:

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]

Я не уверен, как это исправить, я пытался и в конечном итоге просто создавать новые проблемы, пытаясь делать.

Я новичок ie на 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]

Обратите внимание на второе | вместо ,: это то, что обозначает молнию.