CODEWITHSUNDEEP
haskellfunctional-programmingdivision
OneAndOnlyDaniel
OneAndOnlyDaniel

Reputation: 3

Implementing Integer Division in Haskell by Hand

For a homework assignment in Haskell I want to implement binary search, but I'm not allowed to use any predefined functions.

What I'm struggling with is implementing a way of efficiently finding the middle element of a list, so basically I want to calculate

(length x) `div` 2

for some given list x.

The only implementation I could think of is

halfOf :: Int -> Int
halfOf 0 = 0
halfOf 1 = 0
halfOf x = 1 + halfOf (x - 2)

but this is terribly slow. Is there some faster way I could implement this without using any predefined functions?

Thank you in advance.

Upvotes: 0

Views: 283

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

If I were going to try to do this without using length or div, here's what I would do. Step 1 is to "efficiently" cut the length in half; in step two we'll make sure we also have the right elements.

halfAsLong :: [a] -> [a]
halfAsLong (x:y:rest) = x:halfAsLong rest
halfAsLong short = short

Once we have that, we can use it to split a list at the halfway point by iterating along the list and its half-as-long counterpart at once1.

splitLength :: [a] -> [b] -> ([b], [b])
splitLength (a:as) (b:bs) = let (pre, post) = splitLength as bs in (b:pre, post)
splitLength _ bs = ([], bs)

We can now combine the two.

halfsies :: [a] -> ([a], [a])
halfsies as = splitLength (halfAsLong as) as

Try it out:

> mapM_ (print . halfsies) ["", "a", "ab", "abc", "abcd", "abcdefghijklmnopqrstuvwxyz"]
("","")
("a","")
("a","b")
("ab","c")
("ab","cd")
("abcdefghijklm","nopqrstuvwxyz")

1 Actually, if I were doing this, and not trying to teach a beginner, I'd at least use a lazy pattern:

... let ~(pre, post) = splitLength ... in ...

and probably also experiment with using a difference list to see if it was faster:

splitLength = go id where
    go pre (a:as) (b:bs) = go (pre . (b:)) as bs
    go pre _ bs = (pre [], bs)

If id and (.) count as "predefined functions", I'd define copies myself or just use the lambda they represent inline.

Upvotes: 2

Related Questions