Posts Tagged ‘list’

Programming Praxis – Three List Exercises

May 7, 2013

In today’s Programming Praxis exercise, we need to implement three functions that work on linked lists. Let’s get started, shall we?

The first function removes every nth element from a list.

deleteNth :: Int -> [a] -> [a]
deleteNth _ [] = []
deleteNth n xs = take (n - 1) xs ++ deleteNth n (drop n xs)

For the second function we need to remove all the duplicate elements of a list. This is the basic O(n^2) version, keep a separate Set or Hashtable for O(n log n) or O(n) performance.

nub :: Eq a => [a] -> [a]
nub = foldl (\a x -> if elem x a then a else a ++ [x]) []

And finally a function to split a list into two halves. This implementation is probably a little slower than the tortess and hare algorithm, but the code is shorter and more self-explanatory.

half :: [a] -> ([a], [a])
half xs = splitAt (div (length xs) 2) xs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ deleteNth 4 [1..10] == [1,2,3,5,6,7,9,10]
          print $ deleteNth 3 [1,2] == [1,2]
          print $ nub [1..5] == [1..5]
          print $ nub [1,1,2,3,4,5] == [1..5]
          print $ nub [1,1,2,3,4,5] == [1..5]
          print $ nub [1,2,1,3,1,4,1,5,1] == [1..5]
          print $ nub [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5] == [1..5]
          print $ half [1] == ([],[1])
          print $ half [1..5] == ([1,2],[3,4,5])
          print $ half [1..6] == ([1,2,3],[4,5,6])

Programming Praxis – Cyclic Equality

April 9, 2013

In today’s Programming Praxis exercise, our goal is to determine if one list is cyclically equal to another. Let’s get started, shall we?

import Data.List

Rather than the provided solution which involves keep track of a bunch of pointers, we use a simple fact of cyclical lists: repeating either list twice produces a list that contains the other one if they are indeed cyclically equal. In order to prevent false positives, we also have to check whether the lengths are equal.

cyclic :: Eq a => [a] -> [a] -> Bool
cyclic xs ys = length xs == length ys && isInfixOf xs (ys ++ ys)

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ cyclic [1,2,3,4,5] [3,4,5,1,2]
          print $ cyclic [1,1,2,2] [2,1,1,2]
          print $ cyclic [1,1,1,1] [1,1,1,1]
          print . not $ cyclic [1,2,3,4] [1,2,3,5]          
          print . not $ cyclic [1,1,1] [1,1,1,1]

Programming Praxis – Remove characters from a string

February 24, 2012

In today’s Programming Praxis exercise, our task is to remove all the characters in one string from the other. Let’s get started, shall we?

Since this exercise doesn’t mention any performance requirements, we’ll go with the short but naive version, which is O(m * n). If the strings used get larger, you’ll probably want to use different datastructures to have more efficient membership testing, such as a hastable which reduces the complexity to O(m).

remove :: Eq a => [a] -> [a] -> [a]
remove = filter . flip notElem

A quick test to see if it’s working properly:

main = print $ remove "aeiou" "Bonsai Code"

Programming Praxis – First Non-Repeating Character

August 19, 2011

In today’s Programming Praxis exercise, our goal is to find the first character in a string that does not occur anywhere else in the string. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.Map as M

To find the first non-repeated element, we mark each element as unique and insert them into a map. When a duplicate element is found, we remove its unique status. Afterwards, we search the list for the first unique element.

firstUnique :: Ord a => [a] -> Maybe a
firstUnique xs = find (M.fromListWith (\_ _ -> False)
                           (zip xs $ repeat True) M.!) xs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ firstUnique "aabcbcdeef"   == Just 'd'
          print $ firstUnique "aabcbcfeed"   == Just 'f'
          print $ firstUnique "aabcbcdeefdf" == Nothing

Programming Praxis – Miscellanea

April 26, 2011

In today’s Programming Praxis exercise, our goal is to write three fucntions: FizzBuzz, a function to determine if a base 36 number is prime and one to split a list down the middle while going through the list only once. Let’s get started, shall we?

Some imports:

import Data.Foldable (toList)
import Data.Numbers.Primes
import Data.Sequence (ViewL(..), (|>), fromList, viewl, empty)

First up we have the classic FizzBuzz interview question. There are plenty of ways to solve it, but I’m partial to this one.

fizzbuzz :: Integral a => a -> IO ()
fizzbuzz n = mapM_ (putStrLn . f) [1..n] where
    f n = case (mod n 3, mod n 5) of (0, 0) -> "FizzBuzz"
                                     (0, _) -> "Fizz"
                                     (_, 0) -> "Buzz"
                                     _      -> show n

To determine if a word is prime we convert it from base 36 to base 10 and then determine if it’s prime.

isPrimeWord :: String -> Bool
isPrimeWord = isPrime . sum . zipWith (*) (iterate (* 36) 1) . reverse .
    map (\c -> maybe 0 id . lookup c $ zip (['0'..'9'] ++ ['A'..'Z']) [0..])

For splitting the list, the tortoise and hare algorithm seems dubious to me given the requirement that the list is only scanned once, since both of them scan the list (albeit looking only at half of the elements each). I’ve gone with a different approach. We start with two empty lists, which are balanced. If the lists are balanced, the next element will be added to the right one, which unbalances the list. If they are not balanced, the left element of the right list is added to the end of the left list.

splitList :: [a] -> ([a], [a])
splitList = f True (empty, empty) where
    f _     (l,r) [] = (toList l, toList r)
    f True  (l,r) (x:xs) = f False (l, r |> x) xs
    f False (l,r) (x:xs) = f True ((\(h :< t) -> (l |> h, t |> x)) $ viewl r) xs

Some tests to see if everything is working correctly:

main :: IO ()
main = do fizzbuzz 20
          print . not $ isPrimeWord "PRAXIS"
          print $ isPrimeWord "LISP"
          print $ splitList [] == ([],[] :: [Int])
          print $ splitList [1..4] == ([1,2],[3,4])
          print $ splitList [1..5] == ([1,2],[3,4,5])

Programming Praxis – An Early LISP Program

March 1, 2011

In today’s Programming Praxis exercise, our goal is to write a function to un-nest a list. Let’s get started, shall we?

Since Haskell is statically typed, the concept of nested lists is a bit more difficult than in Lisp, which is dynamically typed. In a regular list in Haskell all elements must be of the same type, which in a nested list is not the case. There are various ways around this, so I will give three different solutions.

Some pragmas and an import for the third and second solution, respectively:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances, UndecidableInstances #-}

import Data.Dynamic

Solution 1: create a datatype for nested lists.

First, we define a nested list:

data List a = E a | L [List a]

Collapsing this list is then a fairly trivial task: just collapse each sublist recursively.

collapse_data :: List a -> [a]
collapse_data (E x) = [x]
collapse_data (L xs) = collapse_data =<< xs

Solution 2: Use dynamic typing.

Just because Haskell is a static language doesn’t mean it can’t do dynamic typing. The only downside is that entering the list is a tad laborious with toDyns all over the place.

collapse_dyn :: Typeable a => Dynamic -> [a]
collapse_dyn x = maybe (maybe [] return $ fromDynamic x)
                       (collapse_dyn =<<) (fromDynamic x)

Solution 3: Tuples

Haskell has a way of defining lists that have elements of different types: tuples. The downside is that tuples of different lengths are considered completely different types, and it is therefore necessary to define every function for every possible tuple length. This can be automated by using Template Haskell, but I won’t go into that here. The advantage of this method is that the list literals look almost exactly like the Lisp ones (with the addition of some commas).

First, we define a typeclass for values that can be collapsed.

class Collapsible a b | a -> b where
    collapse :: a -> [b]

Next, we describe how to collapse a tuple. As mentioned, the code for 3-tuples and longer can be generated using Template Haskell.

instance (Collapsible a c, Collapsible b c) => Collapsible (a, b) c where
    collapse (a, b) = collapse a ++ collapse b

We also need to describe how to collapse literals. For production use, the other literals like Int and Float should be defined as well.

instance Collapsible Char Char where
    collapse c = [c]

Some tests to see if everything is working properly:

main :: IO ()
main = do
    print $ collapse_data (L[L[L[L[E 'a', E 'b'], L [L [E 'c']]],
                               L [L [E 'd', L [E 'e', E 'f']],
                                  L [E 'g'], L [L [E 'h']]]]]) == "abcdefgh"
    print $ collapse_dyn (toDyn [toDyn [toDyn 'a', toDyn [toDyn 'b',
              toDyn [toDyn 'c', toDyn [toDyn 'd', toDyn [toDyn 'e']]], 
              toDyn 'f', toDyn [toDyn 'g',
              toDyn [toDyn 'h', toDyn 'j']]]]]) == "abcdefghj"
    print $ collapse (((((('a'), 'b'), 'c'), 'd'), 'e')) == "abcde"

Yep. The first two methods are short to implement but make the actual lists less concise, the third is the other way round. Choose whichever option you prefer.

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]

Who Owns The Zebra Reloaded

June 22, 2009

For the Who Owns the Zebra problem I initially tried a solution based on a list comprehension. I was, however, unable to get it to work in any reasonable time. Today Rofl_Waffler posted a solution on reddit that showed me why: I put all the conditions at the end, which meant that all possible solutions had to be generated. By interleaving the options and the conditions, Haskell does do the smart filtering you would expect. Although it does require careful ordering of the code, the resulting solution is a lot shorter. Rofl_Waffler’s solution uses a do statement with guards, but I figured I could make it even better using a list comprehension and some other minor adjustments.

Our import:

import Data.List

In this approach all permutations of the five properties are generated. To figure out the position of a specific option we use the following function:

indexOf :: (Eq a) => [a] -> a -> Int
indexOf xs x = head $ elemIndices x xs

We also need to be able to tell if an option is next to or to the right of another option:

nextTo :: Int -> Int -> Bool
nextTo a b = abs (a - b) == 1

rightOf :: Int -> Int -> Bool
rightOf a b = a == b + 1

A small convenience function to generate the different permutations:

options :: String -> [[String]]
options = permutations . words

And the solution to the problem itself.

solution :: [[String]]
solution = head [transpose [cs, os, ds, ss, ps] |
    cs <- options "red green ivory yellow blue",
    let color = indexOf cs,
    color "green" `rightOf` color "ivory",
    os <- options "english spaniard ukranian norwegian japanese",
    let owner = indexOf os,
    owner "norwegian" == 0,
    owner "english" == color "red",
    owner "norwegian" `nextTo` color "blue",
    ds <- options "coffee tea milk juice water",
    let drinks = indexOf ds,
    drinks "milk" == 2,
    drinks "coffee" == color "green",
    owner "ukranian" == drinks "tea",
    ss <- options "old_gold kools chesterfields parliaments lucky_strike",
    let smokes = indexOf ss,
    smokes "kools" == color "yellow",
    smokes "lucky_strike" == drinks "juice",
    owner "japanese" == smokes "parliaments",
    ps <- options "dog snails fox horse zebra",
    let pet = indexOf ps,
    owner "spaniard" == pet "dog",
    smokes "old_gold" == pet "snails",
    smokes "chesterfields" `nextTo` pet "fox",
    smokes "kools" `nextTo` pet "horse"]

A quick test shows that we still get the correct answer.

main :: IO ()
main = mapM_ print solution

Now we only need 30 lines, which is a reduction of just under 50%. The lesson here: put conditions in list comprehensions as close to the generators as possible.

Programming Praxis – Feynman’s Puzzle

June 12, 2009

Today’s Programming Praxis problem is about a long division puzzle by Richard Feynman. The provided solution is 14 lines of code. Since both his and my solution are little more than a simple list comprehension, there is not going to be much room for improvement, but let’s see what we can do.

We need a way to refer to specific digits of numbers. The provided solution does so by converting the number to a list of digits. This function just returns the nth digit of a number, starting with the least significant one. For instance, digit 1 1234 equals 4.

digit :: Int -> Int -> Int
nth `digit` n = n `mod` 10 ^ nth `div` 10 ^ (nth - 1)

As mentioned, this problem is most naturally solved with a list comprehension, so that is what we will use as well. The actual conditions are of course nearly identical to the scheme version, with the exception that the condition that a * n1 has four digits is unnecessary, and therefore removed in this version.

feinman :: [(Int, Int)]
feinman = [ (n1, n2)
          | b <- [1..9], a <- [0..9], c <- [0..9],
            d <- [1..9], e <- [0..9], f <- [0..9],
            a /= b, a /= c, a /= d, a /= e, a /= f, e < d,
            let n1 = 100 * b + 10 * a + c,
            let n2 = 1000 * d + 100 * e + 10 * a + f,
            n1 * n2 > 999999, n1 * n2 < 10000000,
            digit 3 (n1 * n2) == a,
            digit 1 (d * n1) == a, digit 2 (d * n1) == a,
            digit 1 (e * n1) == a, digit 3 (a * n1) == a]

To test, we just print the list.

main :: IO ()
main = print feinman

As expected, we get the single result of (484, 7289). Runtime is about 8.5 seconds in ghci and 60 ms compiled (You’ve got to love compilers). The end result is 11 lines of code, so a slight improvement over the scheme version.