Home / Questions / 26374
Accepted
Ramosaurio
Asked: 2020-10-07 08:32:03 +0800 CST 2020-10-07 08:32:03 +0800 CST

Haskell, division without div

  • 772

Hello good I have a problem in hand try to make a code in Haskell with the following conditions:

We introduce two numbers a y bfor it to be divided a/b by type Integer, so that we have its module and its quotient

With the following restrictions only additions, subtractions and comparators can be used neither div, nor mod, nor anything can be used

//Edited from here

cocienteYResto:: Integer -> Integer -> (Integer, Integer)
cocienteYResto x y 
    | x < y = (x,?????)
    | otherwise = ((cocienteYResto (x - y) y))

well here as we see when x< yI am returning the rest, but I have no way, well rather I do not know how to get that quotient (this right now does not even observe that it is divided by 0, nor that x<yin a base case

you just have to divide things like 3/2 10/4, but nothing 3/8 .

Suggestions of all kinds are accepted, I'm starting and any help is good for me.

Greetings and thank you

haskell

1 Answers

  1. Best Answer

    It could be done by introducing an auxiliary function that drags the value of the quotient in each recursive iteration.

    cocienteYResto :: Integer -> Integer -> (Integer, Integer)
cocienteYResto = aux 0
    where aux c x y
            | x >= y    = aux (c+1) (x-y) y
            | otherwise = (c,x)

    But, since we're dealing with , we can take advantage of what we have to make it more elegant:

    import Data.List (span, genericLength)

cocienteYResto :: Integer -> Integer -> (Integer, Integer)
cocienteYResto x y = (genericLength l, head r)
    where (l,r) = (span (>=y) . iterate (-y+)) x

    Edited on 2016-10-07

    A better version:

    cocienteYResto :: Integer -> Integer -> (Integer,Integer)
cocienteYResto x y = head . dropWhile ((>=y).snd)
                   $ zip [0..] (iterate (-y+) x)
    • 2