1

I want to add two positive numbers together without the use of any basic operators like + for addition. I've already worked my way around that (in the add''' function) (i think) may not be efficient but thats not the point right now. I am getting lots of type errors however which i have no idea how to handle, and is very confusing for me as it works on paper and i've come from python.

add 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]

conversion [1,2,4,5] [7,4,8,9] then zipping them together [(1,7),(2,4)....] 

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

summary [8,6,...] what happens when the sum reaches 10 is not implemented yet.

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

adding two numbers together

Improve this question
5
  • Your add function is Int -> Int -> Int and your add'' function returns an [Int] Commented Nov 2, 2018 at 10:14
  • There are also simpler ways to do the thing that you are trying to do, especially if the numbers are always positive, which means that they could represent the length of something... Commented Nov 2, 2018 at 10:18
  • 1
    so + is basic, but mod and div are not? :) (joking). -- nice exercise! Commented Nov 2, 2018 at 10:31
  • You realize that succ :: Int -> Int is just defined as succ x = x + 1, though, right? You're jumping through multiple layers of abstraction to avoid +, which is hidden in the final layer anyway. Commented Nov 2, 2018 at 12:47
  • 1
    You may as well define your own succ' function explicitly (succ 0 = 1; succ 1 = 2; -- etc), then figure out how to handle carrying. Commented Nov 2, 2018 at 12:48

4 Answers 4

Reset to default
3

  1. You can't use head and last on tuples. ...Frankly, you should never use these functions at all because they're unsafe (partial), but they can be used on lists. In Haskell, lists are something completely different from tuples.
    To get at the elements of a tuple, use pattern matching.

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

    (To get at the elements of a list, pattern matching is very often the best too.) Alternatively, you can use fst and snd, these do on 2-tuples what you apparently thought head and last would.

  2. Be clear which functions are curried and which aren't. The way you write add''', its type signature is actually Int -> Int -> Int. That is equivalent to (Int, Int) -> Int, but it's still not the same to the type checker.

  3. The result of add'' is [Int], but you're trying to use this as Int in the result of add. That can't work, you need to translate from digits to numbers again.

  4. add'' doesn't handle the empty case. That's fixed easily enough, but better than doing this recursion at all is using standard combinators. In your case, this is only supposed to work element-wise anyway, so you can simply use map – or do that right in the zipping, with zipWith. Then you also don't need to unwrap any tuples at all, because it works with a curried function.

A clean version of your attempt:

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

Note that zipWith requires both numbers to have the same number of digits (as does zip).

Also, yes, I'm using + in fromDigits, making this whole thing pretty futile. In practice you would of course use binary, then it's just a bitwise-or and the multiplication is a left shift. What you actually don't need to do here is take special care with 10-overflow, but that's just because of the cheat of using + in fromDigits.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

not futile at all. :) --- 9+9=18; 9+9+1=19. the carry is only ever 0, or 1. an occasional additional succ is all that's needed. right?
1

By head and last you meant fst and snd, but you don't need them at all, the components are right there:

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!

Now the big question that remains is what to do with those big scary 10-and-over numbers. Here's a thought: produce a digit and a carry with

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

Can you take it from here? Hint: reverse order of digits is your friend!

Improve this answer

Comments

1

the official answer my professor gave

works on positive and negative numbers too, but still requires the two numbers to be the same length

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

1 Comment

This doesn't require “same length”. In fact it has no notion of “length”, or rather the “length” is the value, as in unary... it's just horribly inefficient, your original approach was much faster.
0

The other answers cover what's gone wrong in your approach. From a theoretical perspective, though, they each have some drawbacks: they either land you at [Int] and not Int, or they use (+) in the conversion back from [Int] to Int. What's more, they use mod and div as subroutines in defining addition -- which would be okay, but then to be theoretically sound you would want to make sure that you could define mod and div themselves without using addition as a subroutine!

Since you say efficiency is no concern, I propose using the usual definition of addition that mathematicians give, namely: 0 + y = y, and (x+1) + y = (x + y)+1. Here you should read +1 as a separate operation than addition, a more primitive one: the one that just increments a number. We spell it succ in Haskell (and its "inverse" is pred). With this theoretical definition in mind, the Haskell almost writes itself:

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

So: compared to other answers, we can take an Int and return an Int, and the only subroutines we use are ones that "feel" more primitive: succ, pred, and checking whether a number is zero or nonzero. (And we land at only three short lines of code... about a third as long as the shortest proposed alternative.) Of course the price we pay is very bad performance... try add (2^32) 0!

Like the other answers, this only works for positive numbers. When you are ready for handling negative numbers, we should chat again -- there's some fascinating mathematical tricks to pull.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.