Commits

Petro Verkhogliad committed 61a8997

Initial import. Problems 1 - 22

  • Participants

Comments (0)

Files changed (1)

+import Data.List
+import System.Random
+
+-- problem 1 - find the last element of the list
+myLast = head . reverse
+
+-- problem 2 -- find the last by one element of a list
+myButLast [] = error "Emtpy list does not have any elements"
+myButLast lst = head . reverse . take 2 . reverse 
+
+-- problem 3 -- find the kth elements of a list
+elementAt idx = head . drop (idx - 1)
+
+-- problem 4 -- find the number of elements in a list
+myLength []  = 0
+myLength lst = sum [1 | x <- lst]
+
+myLength' [] = 0
+myLength' lst = 1 + ( myLength' $ drop 1 lst )
+
+-- problem 5 -- reverse a list
+myReverse = foldl conc [] where conc = flip (:)
+
+-- problem 6 -- find out if a list is a palindrome
+isPalindrome [] = True
+isPalindrome (x:[]) = True
+isPalindrome lst = if (x == y) 
+                        then isPalindrome $ slice lst 
+                        else False where
+                            slice = reverse . (drop 1) . reverse . (drop 1)
+                            x = head lst
+                            y = myLast lst
+
+-- problem 7 -- flatten a nested list structure
+data NestedList a = List [NestedList a]| Elem a deriving (Show)
+flatten (Elem a) = [a]
+flatten (List a) = foldl (++) [] [flatten x | x <- a]
+
+--  problem 8 -- eliminate concecutive duplicate elements in a list of elements
+compress lst = compress' lst []
+compress' [] lst = lst
+compress' (x:xs) lst = compress' newList result where
+                            newList = dropWhile (\k -> x == k) xs
+                            result = lst ++ [x]
+
+
+
+-- problem 9 -- pack consecutive duplicates of list elements into sublists
+pack [] = []
+pack lst@(x:xs) = (takeWhile (==x) lst) : pack (dropWhile (==x) lst)
+
+-- problem 10 -- run-length encoding of a list
+encode :: Eq a => [a] -> [(Int, a)]
+encode = map (\lst -> (length lst, head lst)) . pack
+
+-- problem 11 -- modified run-length encoding
+data ListEncoding a = Multiple Int a | Single a deriving (Show)
+
+encodeModified :: Eq a => [a] -> [ListEncoding a]
+encodeModified = map mapper . encode where
+                     mapper (a,b) = if a > 1 then Multiple a b else Single b
+
+
+--  problem 12 -- decode a runlength encoded list. decode the result of problem 11
+decodeModified = concat . map decoder where 
+                 decoder (Single x) = [x]
+                 decoder (Multiple n x) = take n $ repeat x
+
+
+-- problem 13 -- run-length encoding of a list (direct solution)
+getValue (Single a) = a
+getValue (Multiple n a) = a
+
+increaseCount (Single val) = Multiple 2 val
+increaseCount (Multiple n val) = Multiple (n+1) val
+
+encodeDirect' source@(s:ss) [] = encodeDirect' ss [Single s]
+encodeDirect' [] result = result
+encodeDirect' source@(s:ss) result@(x:xs) = if s == (getValue x) then encodeDirect' ss updatedResult' else encodeDirect' ss updatedResult'' where
+            updatedResult' = (increaseCount x) : xs
+            updatedResult'' = (Single s) : result
+            currentVal = getValue x
+
+encodeDirect lst = reverse $ encodeDirect' lst []
+
+
+
+-- problem 14 -- duplicate elements of a list
+dupli = concatMap (replicate 2)
+
+-- problem 15 -- replicate the number of elements of a list a given number of times
+repli lst count = concatMap (replicate count) lst
+
+-- problem 16 -- drop every nth element from the list
+dropEvery [] n = []
+dropEvery lst n = (take (n-1) lst) ++ dropEvery (drop n lst) n
+
+-- problem 17 - split a list into 2 parts
+split lst n = [take n lst, drop n lst]
+
+-- problem 18 -- extract a slice from a list
+slice lst i j = take (j - i + 1) $ drop (i-1) lst
+
+-- problem 19 -- rotate a list n places to the left
+rotate lst i = if i > 0 then positive else negative where
+                   ll = length lst
+                   positive = (drop i lst) ++ (take i lst) 
+                   negative = (drop (ll + i) lst) ++ (take (ll+i) lst)
+
+-- problem 20 -- remove kth element from the list
+removeAt i lst = (element, list) where
+                    element = head $ drop (i) lst
+                    list = (take i lst) ++ (drop (i+1) lst)
+
+-- problem 21 -- insert an element at a given position
+insertAt elem lst pos = (take (pos-1) lst) ++ [elem] ++ (drop (pos-1) lst)
+
+-- problem 22 -- create a list containing all integers with a given range
+--range a b = range' a b [] where range' a b lst = if a == b then (reverse ( a : lst)) else range' (a+1) b (a : lst)
+range a b = takeWhile (<=b) $ iterate (+1) a
+
+
+-- problem 23 -- extract a given number of randonly selected elements from a list
+rnd_select lst num = do 
+    gen <- newStdGen
+    let ns = take num $ randomRs (0, -1 + (length lst)) gen
+    return $ map (\k -> lst !! k) ns
+
+-- problem 24 -- draw n different random numbers from the set 1..M
+diff_select num limit = (randomRs (1, limit)) >>= newStdGen
+    --gen <- newStdGen
+    --return $ take num $ randomRs (1, limit) gen
+
+-- problem 25 -- generate a random permutation of the elements in the list
+
+
+
+-- problem 28a -- sorting lists according to legnth of sublists
+lsort lsts = map snd $ sort $ map (\lst -> (length lst, lst)) lsts
+
+-- problem 28b -- sorting lists by their frequency
+--lfsort lsts =