CODEWITHSUNDEEP
haskellintegermultiplication
Max
Max

Reputation: 25

Multiplication AbstractInteger

I have a datatype:

data AbstractInteger = Zero
                     | Succ AbstractInteger
                     | Pred AbstractInteger
                     deriving (Show, Eq)

I already have two functions:

1) Convert AbstractInteger into Integer:

aiToInteger :: AbstractInteger -> Integer
aiToInteger (Zero) = 0
aiToInteger (Succ next) = 1 + (aiToInteger next)
aiToInteger (Pred prev) = (aiToInteger prev) - 1

2) Addition AbstractInteger :

plusAbs :: AbstractInteger -> AbstractInteger -> AbstractInteger
plusAbs a b | aiToInteger a == 0 = b
            | aiToInteger b == 0 = a
            | aiToInteger a > 0 = (Succ (plusAbs (Pred a) b))
            | otherwise = (Pred (plusAbs (Succ a) b))

But I don't understand how to create multiply function.

I wrote this but it's not work.

multiplyAbs :: AbstractInteger -> AbstractInteger -> AbstractInteger
multiplyAbs _ (Zero) = (Zero)
multiplyAbs (Zero) _ = (Zero)
multiplyAbs a (Succ Zero) = a
multiplyAbs (Succ Zero)  b = b
multiplyAbs a b = (plusAbs a (timesAbs a (Pred(b))))

Upvotes: 0

Views: 164

Answers (1)

Igor Drozdov
Igor Drozdov

Reputation: 15045

As you've implemented aiToInteger, you might want to implement iToAi, something like:

iToAi :: Integer -> AbstractInteger
iToAi a | a == 0 = Zero
        | a < 0 = Pred (iToAi (a + 1))
        | a > 0 = Succ (iToAi (a - 1))

Then plusAbs and multiplyAbs will come down to converting abstract integers to integers, perform the operations on them and convert them back:

plusAbs' :: AbstractInteger -> AbstractInteger -> AbstractInteger
plusAbs' a b = iToAi (aiToInteger a + aiToInteger b)

multiplyAbs' :: AbstractInteger -> AbstractInteger -> AbstractInteger
multiplyAbs' a b = iToAi (aiToInteger a * aiToInteger b)

But I'd suggest trying to implement the functions by using pattern-match on the arguments, something like:

negative :: AbstractInteger -> AbstractInteger
negative Zero = Zero
negative (Succ a) = Pred (negative a)
negative (Pred a) = Succ (negative a)

multiplyAbs :: AbstractInteger -> AbstractInteger -> AbstractInteger
multiplyAbs Zero a = Zero
multiplyAbs (Succ a) b = plusAbs (multiplyAbs a b) b
multiplyAbs (Pred a) b = plusAbs (multiplyAbs a b) (negative b)

The key point is that Succ a can be associated with (a + 1), that's why (Succ a) * b can be associated with a * b + b. According to this logic (Pred a) * b is converted to a * b - b, that's why you need negative function here.

plusAbs is implemented similarly:

  • (a + 1) + b is the same as 1 + (a + b)
  • (a - 1) + b is the same as (a + b) - 1

The logic is just like in your example, but you can avoid using aiToInteger by using pattern-match.

Upvotes: 1

Related Questions