Division in Haskell

Question

I'm making a function in Haskell that halves only the evens in a list and I am experiencing a problem. When I run the complier it complains that you can't perform division of an int and that I need a fractional int type declaration. I have tried changing the type declaration to float, but that just generated another error. I have included the function's code below and was hoping for any form of help.

halfEvens :: [Int] -> [Int]
halfEvens [] = []
halfEvens (x:xs) | odd x = halfEvens xs
                 | otherwise = x/2:halfEvens xs

Thank you for reading.

I think you want x `div` 2 in this case. I'll let someone else confirm that I'm right (not 100% sure I am) and give a more complete explanation. — Tyler, Sep 10 '11 at 00:57

score 57 · Accepted Answer · edited May 23 '17 at 11:53

57

Use div, which performs integer division:

halfEvens :: [Int] -> [Int]
halfEvens [] = []
halfEvens (x:xs) | odd x = halfEvens xs
                 | otherwise = x `div` 2 : halfEvens xs

The (/) function requires arguments whose type is in the class Fractional, and performs standard division. The div function requires arguments whose type is in the class Integral, and performs integer division.

More precisely, div and mod round toward negative infinity. Their cousins, quot and rem, behave like integer division in C and round toward zero. div and mod are usually correct when doing modular arithmetic (e.g. when calculating the day of the week given a date), while quot and rem are slightly faster (I think).

Playing around a bit in GHCi:

> :t div
div :: Integral a => a -> a -> a
> :t (/)
(/) :: Fractional a => a -> a -> a
> 3 / 5
0.6
> 3 `div` 5
0
> (-3) `div` 5
-1
> (-3) `quot` 5
0
> [x `mod` 3 | x <- [-10..10]]
[2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1]
> [x `rem` 3 | x <- [-10..10]]
[-1,0,-2,-1,0,-2,-1,0,-2,-1,0,1,2,0,1,2,0,1,2,0,1]

edited May 23 '17 at 11:53

Community

1
1

answered Sep 10 '11 at 00:57

Joey Adams

41,996
18
86
115

Yes, quot is faster because that's what the machine instruction tends to do. Except for the NS32k processor that had both kinds of division instructions. – augustss Sep 10 '11 at 09:06
1

Does ghc optimize division by a power of 2 into a right-shift? An arithmetic right shift of n bits will divide by 2**n, but it will round towards negative infinity (if you right shift -1, you still get -1). To round towards 0, you have to add (2**n)-1 if the input is negative before shifting. In this case, `div` should be faster than `quot` – pat Sep 10 '11 at 15:53
@pat, I doubt it. ghc does not do very many arithmetic tricks. – luqui Sep 11 '11 at 01:05
@luqui: I wonder if the underlying compiler (GCC, LLVM, etc.) can do it, even after the operation is obfuscated by the code that implements `div` using `quot`. – Joey Adams Sep 11 '11 at 01:24

score 1 · Answer 2 · answered Sep 08 '15 at 18:03

1

I should add that using map would simplify the code.

HalfIfEven n
  | even n = n `div` 2
  | otherwise = n

halfEvens = map halfIfEven

answered Sep 08 '15 at 18:03

Caridorc

6,222
2
31
46

2

But that doesn't give you the same result. The original code removes the odds, yours does not. Simplest would probably be `halfEvens = map (\`div\` 2) . filter even` – semicolon Jul 14 '16 at 15:40

Division in Haskell

2 Answers2

Linked

Related