It’s part three already! Haskell has got me really excited about learning again. It’s not my first functional language (dabbled a little bit in Common Lisp and Erlang before), but it’s really got me curious about what people are doing with it. Anyway, onto the problems!
-- Problem 21: Insert an element at a given position into a list. -- This is exactly like `split` from the previous set of problems, only we use -- concatenation to add the specified element: insert_at :: a -> [a] -> Int -> [a] insert_at x xs n = take (n - 1) xs ++ [x] ++ (drop (n - 1) xs) -- Problem 22: Create a list containing all integers within a given range. -- Haskell already has ranges, e.g. [n..m] or `enumFromTo`, so let's do it without them: range :: Int -> Int -> [Int] range n m | n < m = n : range (n + 1) m | n > m = n : range (n - 1) m | otherwise = [n] -- Problem 23: Extract a given number of randomly selected elements from a list. -- Now, this one's tricky. If you go about it the naive way and just pick N elements from -- a list allowing repetitions, you're gonna have a hard time in the problems following -- this one (I did, anyway). Instead, I opted for using Problem 20, as the original list -- of 99 questions states, therefore allowing only for selection without repetition. -- `IO [a]` because of randomRIO: rnd_select :: [a] -> Int -> IO [a] -- Easy cases first: rnd_select _ 0 = return  rnd_select  _ = return  -- Pick an index at random, -- remove the element at that index, -- and concatenate our choices. EZ! rnd_select xs n = do index <- randomRIO (0, (length xs) - 1) rest <- rnd_select (remove_at xs (index + 1)) (n - 1) return ( (xs !! index) : rest) -- Problem 24: Draw N different random numbers from the set 1..M. -- We already implemented random element extraction, and ranges! diff_select n m = rnd_select (range 1 m) n -- Problem 25: Generate a random permutation of the elements of a list. -- Ha! We already did that! Way ahead of you, problem list! rnd_permutation xs = rnd_select xs $ length xs -- Problem 26: Generate the combinations of K distinct objects chosen from the N elements -- of a list. -- Up to this moment in time, I always had difficulty writing code to generate combinations -- in other languages (C, C++, Python, all the shit I thought I was good at). Five seconds -- after I read this problem, I knew the solution; select 1 of each element in order, then -- select N-1 from the rest recursively (wee!). -- Note that dropping the `(index + 1)` elements of `xs` makes sense if order of -- combinations does not matter. If the order matters, use `remove_at` from problem #20. combinations :: Int -> [a] -> [[a]] combinations 0 _ = [] combinations n xs = [xs !! index : x | index <- [0..(length xs)-1] , x <- combinations (n - 1) (drop (index + 1) xs) ] -- Problem 27: Group the elements of a set into disjoint subsets. -- Same as before, we're choosing elements to form combinations, recursively. This is -- exactly how the multinomial coefficient mentioned in the problem statement is -- interpreted combinatorially; the number of ways of depositing n distinct objects into m -- distinct bins, with k1 objects in the first bin, k2 in the second, and so forth: -- Discrete math is really cool. mygroup :: [Int] -> [a] -> [[[a]]] mygroup  _ = [] mygroup (n:ns) xs = [ g:gs | (g,rs) <- combinations n xs , gs <- mygroup ns rs] -- Problem 28: Sorting a list of lists according to length of sublists. -- Data.List already has implemented `sortBy` for our pleasure: import Data.List (sortBy) import Data.Ord (comparing) lsort :: [[a]] -> [[a]] lsort = sortBy (comparing length) -- Problem 29: Sorting a list of lists according to their length frequency. -- At first I got confused here because I tried replicating the order results appear, when -- in fact it does not matter in this context. So here's what we do: -- we group lists according to their length, which produces something like: -- [["o"],["de","de","mn"],["abc","fgh"],["ijkl"],["abcde"]] -- then we just sort by length and we're done: import Data.List (groupBy) lfsort :: [[a]] -> [[a]] lfsort ls = concat groups where groups = lsort $ groupBy equal_length $ lsort ls equal_length xs ys = length xs == length ys
See you next time with 31-40 - Arithmetic!« Past Future »