99 problems in Haskell, 21-30

-- 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