Добавление двух чисел без использования оператора + в Haskell

Question

Я хочу добавить два положительных числа вместе без использования каких-либо базовых операторов, таких как + для сложения. Я уже обошел этот вопрос (в функции add '' ') (я думаю) может быть неэффективным, но сейчас это не главное. Однако я получаю много ошибок типа, которые я не знаю, как их обработать, и это меня очень смущает, так как это работает на бумаге, и я пришел из python.

добавить 1245 7489

--add :: Int -> Int -> Int
add x y = add'' (zip (add' x) (add' y))
 where
 add' :: Int -> [Int]
 add' 0 = []
 add' x = add' (x `div` 10) ++ [x `mod` 10]

преобразование [1,2,4,5] [7,4,8,9], затем сжатие их вместе [(1,7), (2,4) ....]

 add'' :: [(Int,Int)] -> [Int]
 add'' (x:xs) = [(add''' (head x) (last x))] ++ add'' xs 

Резюме [8,6, ...] что происходит, когда сумма достигает 10, еще не реализовано.

  where
  --add''' :: (Int,Int) -> Int
  add''' x y = last (take (succ y) $ iterate succ x)

сложение двух чисел

Answer 1

официальный ответ моего профессора

работает и для положительных и отрицательных чисел, но все равно требует одинаковой длины двух чисел

add 0 y = y
add x y
 | x>0 = add (pred x) (succ y)
 | otherwise = add (succ x) (pred y)

Answer 2

Под head и last вы имели в виду fst и snd, но они вам совсем не нужны, компоненты тут же:

add'' :: [(Int, Int)] -> [Int]
add'' (pair : pairs) = [(add''' pair)] ++ add'' pairs 
  where
  add''' :: (Int, Int) -> Int
  add''' (x, y) = last (take (succ y) $ iterate succ x)
                = iterate succ x !! y
                = [x ..] !! y          -- nice idea for an exercise!

Теперь остается большой вопрос: что делать с этими большими страшными числами от 10 и более. Вот мысль: произвести цифру и перенос с

   = ([(d, 0) | d <- [x .. 9]] ++ [(d, 1) | d <- [0 ..]]) !! y

Вы можете взять это отсюда? Подсказка: обратный порядок цифр ваш друг!

Answer 3

Другие ответы касаются того, что пошло не так в вашем подходе. С теоретической точки зрения, однако, у каждого из них есть свои недостатки: они либо дают вам [Int], а не Int, либо используют (+) при преобразовании обратно из [Int] в Int. Более того, они используют mod и div в качестве подпрограмм при определении сложения - это было бы хорошо, но тогда, чтобы быть теоретически обоснованным, вы хотели бы убедиться, что вы можете сами определять mod и div, не используя дополнение как подпрограмма!

Поскольку вы говорите, что эффективность не имеет значения, я предлагаю использовать обычное определение сложения, которое дают математики, а именно: 0 + y = y и (x + 1) + y = (x + y) +1. Здесь вы должны прочитать +1 как отдельную операцию, а не как сложение, более примитивное: то, которое просто увеличивает число. Мы пишем это succ в Хаскеле (и его "обратное" - pred). Имея в виду это теоретическое определение, Хаскелл почти пишет сам:

add :: Int -> Int -> Int
add 0 y = y
add x y = succ (add (pred x) y)

Итак: по сравнению с другими ответами мы можем взять Int и вернуть Int, и мы используем только те подпрограммы, которые «чувствуют» себя более примитивными: succ, pred и проверяют, число ноль или не равно нулю. (И мы получаем только три короткие строки кода ... около трети до самой короткой предложенной альтернативы.) Конечно, цена, которую мы платим, очень плохая производительность ... попробуйте add (2^32) 0!

Как и другие ответы, это работает только для положительных чисел. Когда вы будете готовы к обработке отрицательных чисел, мы должны снова поболтать - есть несколько захватывающих математических трюков , которые нужно потянуть.

Answer 4

1. Вы не можете использовать head и last для кортежей. ... Честно говоря, вы не должны никогда использовать эти функции вообще, потому что они небезопасны (частично), но они могут использоваться в списках. В Haskell списки являются чем-то совершенно отличным от кортежей.
   Чтобы получить доступ к элементам кортежа, используйте сопоставление с образцом .

   add'' ((x,y):xs) = [add''' x y] ++ add'' xs 
   

   (Чтобы получить доступ к элементам списка, сопоставление с образцом очень часто также является лучшим.) В качестве альтернативы, вы можете использовать fst и snd, они делают на 2-х кортежах то, что вы, очевидно, думали head и last будет.

2. Уточните, какие функции каррированы, а какие нет. То, как вы пишете add''', его подпись типа на самом деле Int -> Int -> Int. Это эквивалент до (Int, Int) -> Int, но оно все равно не совпадает с проверкой типов.

3. Результат add'' равен [Int], но вы пытаетесь использовать его как Int в результате add. Это не может работать, вам нужно снова переводить цифры или цифры.

4. add'' не обрабатывает пустой случай. Это легко исправить, но лучше, чем вообще делать эту рекурсию, использовать стандартные комбинаторы. В вашем случае это все равно должно работать поэлементно, так что вы можете просто использовать map - или сделать это прямо в zip, с zipWith. Тогда вам также не нужно разворачивать какие-либо кортежи вообще , потому что это работает с функцией карри.

---

Чистая версия вашей попытки:

add :: Int -> Int -> Int
add x y = fromDigits 0 $ zipWith addDigits (toDigits x []) (toDigits y [])
 where
       fromDigits :: Int -> [Int] -> Int
       fromDigits acc [] = acc
       fromDigits acc (d:ds)
            = acc `seq`  -- strict accumulator, to avoid thunking.
                fromDigits (acc*10 + d) ds

       toDigits :: Int -> [Int] -> [Int]                -- yield difference-list,
       toDigits 0 = id                                  -- because we're consing
       toDigits x = toDigits (x`div`10) . ((x`mod`10):) -- left-associatively.

       addDigits :: Int -> Int -> Int
       addDigits x y = last $ take (succ x) $ iterate succ y

Обратите внимание, что zipWith требует, чтобы оба числа имели одинаковое количество цифр (как и zip).

Кроме того, да, я использую + в fromDigits, что делает все это довольно бесполезным. На практике вы, конечно, будете использовать двоичный файл, тогда он будет просто побитовым, или умножение будет левым сдвигом. То, что вы на самом деле не должны делать здесь, - это проявлять особую осторожность с переполнением 10, но это только из-за хитрости использования + в fromDigits.