Posts Tagged ‘array’

Programming Praxis – An Array Of Two Symbols

March 12, 2013

In today’s exercise, our goal is to write a function that, given a list consisting of m of one symbol followed by n of another symbol, returns the starting index of the second group of symbols in O(log m) time. Let’s get started, shall we?

import qualified Data.Vector as V
import Test.QuickCheck

The basis idea is simple: starting at the first element, keep doubling the index until we encounter a symbol from the second group or we run past the end of the array. Repeat the process, only now looking at the subarray from the last m to the first n (or the end of the array). When this array has only two values (by definition an m and an n), we’ve found our answer.

Unlike the provided solution, we don’t use a binary search once we’ve found our bounds. We already have one O(log m) test, so why bother writing another?

search :: V.Vector Char -> Int
search xs = f 0 (V.length xs - 1) where
    f start end = case span ((xs V.! 0 ==) . (xs V.!)) . takeWhile (<= end) .
                       map (start +) $ 0 : iterate (*2) 1
                  of   ([_],[n]) -> n
                       (ms ,[] ) -> f (last ms) end
                       (ms ,n:_) -> f (last ms) n

To test if everything is working correctly, we use a few manual tests and quickCheck for an automated one.

test :: Property
test = forAll (choose (1,100)) $ \i ->
       forAll (choose (1,100)) $ \j ->
       search (V.fromList $ replicate i 'm' ++ replicate j 'n') == i

main :: IO ()
main = do print $ search (V.fromList "mn") == 1
          print $ search (V.fromList "mmmnn") == 3
          print $ search (V.fromList "mmmmmmnnnnnnnnnnn") == 6
          quickCheck test

Programming Praxis – Imperative Heaps

January 25, 2013

In today’s Programming Praxis exercise, our goal is to implement an array-based heap. Let’s get started, shall we?

We’ll be using Vectors as our array datatype.

import qualified Data.Vector as V

The algorithm assumes that the array is 1-based instead of the usual 0-based. Having to do this at every array lookup would be annoying, so we define a new array index operator.

(!) :: V.Vector a -> Int -> a
v ! i = v V.! (i-1)

Swapping two elements can be done without having to use a temporary variable thanks to Vector’s bulk update feature.

swap :: Int -> Int -> V.Vector a -> V.Vector a
swap i j heap = heap V.// [(i-1, heap ! j), (j-1, heap ! i)]

Sifting up is fairly simple: keep swapping elements with their parents as long as necessary.

siftup :: Ord a => Int -> V.Vector a -> V.Vector a
siftup i heap = let j = div i 2 in if i == 1 || heap ! j <= heap ! i
                then heap else siftup j $ swap i j heap

Sifting down is less convenient, since we need to count up to n, necessitating a worker function. A quick tip on recursive worker functions: make sure they call themselves rather than their parent functions. I initially didn’t, and it took me quite a while to find the bug.

siftdown :: Ord a => Int -> V.Vector a -> V.Vector a
siftdown n = f 1 where
    f i heap = if 2*i > n || heap ! i <= c  then heap
               else f j $ swap i j heap where
                   (c, j) = minimum [(heap ! x, x) | x <- [2*i, 2*i+1], x <= n]

Sorting is a matter of first sifting up and then sifting down.

hsort :: Ord a => V.Vector a -> V.Vector a
hsort heap = foldr (\i -> siftdown (i - 1) . swap 1 i)
             (foldl (flip siftup) heap [2..V.length heap]) [2..V.length heap]

And finally a test to see if everything is working properly.

main :: IO ()
main = print $ hsort (V.fromList [4,7,8,1,5,3,2,9,6]) == V.fromList [9,8..1]

Programming Praxis – Rotate An Array

October 12, 2010

In today’s Programming Praxis exercise, our goal is to write a function to rotate an array a selected number of places. Let’s get started, shall we?

While the assignment mentions arrays specifically, we’re going to be using plain lists, for the following reasons:

1. In Haskell lists are a far more common data structure than arrays.
2. The algorithm used in the Scheme solution is O(n) anyway, so it doesn’t matter all that much in terms of performance.
3. This way we can show off an alternative method, which is more fun than just implementing the provided algorithm in another language.

Instead of the triple reversing approach, we use a more straightforward method: what we effectively do when rotating a list is splitting it into a left and a right part and exchanging their places. So let’s just do that, making sure to keep the splitting point within the bounds of the list:

rotate :: Int -> [a] -> [a]
rotate _ [] = []
rotate n xs = b ++ a where (a,b) = splitAt (mod n $ length xs) xs

To see if it works, we test all the possible corner cases mentioned in the assignment, including the empty list, which the provided solution fails on (which is another reminder of why you should always consider all possible edge cases). To be honest, so did mine until I wrote ‘all possible edge cases’ and figured I’d better check if that was actually the case 🙂

main :: IO ()
main = do print $ rotate 1 [] == ([] :: [Int])
          print $ rotate 3 [1..3] == [1..3]
          print $ rotate 3 [1..3] == [1..3]
          print $ rotate 2 [1..6] == [3,4,5,6,1,2]
          print $ rotate 8 [1..6] == rotate 2 [1..6]
          print $ rotate (-2) (rotate 2 [1..6]) == [1..6]