Haskell 99問 (21-28)

Haskell 99問 (21-28)

http://www.haskell.org/haskellwiki/99_questions/21_to_28

問題21　要素をリストの指定の場所に挿入する関数を作れ。

実行例
P21> insertAt 'X' "abcd" 2
"aXbcd"

解答
insertAt :: a -> [a] -> Int -> [a]
insertAt x xs (n+1) = let (ys,zs) = splitAt n xs in ys++x:zs

問題22　指定範囲の整数をすべて含むリストを作る関数を作れ。

実行例
Prelude> range 4 9
[4,5,6,7,8,9]

解答
range x y = [x..y]

問題23　リストから指定した数の要素をランダムに選び出す関数を作れ。

実行例
Prelude System.Random>rnd_select "abcdefgh" 3 >>= putStrLn
eda

解答
import System.Random

rnd_select :: [a]->Int->IO [a]
rnd_select [] _ = return []
rnd_select l  n
    | n<0 = error "N must be greater than zero."
    | otherwise = do pos<-sequence$replicate n$getStdRandom$randomR (0,(length l)-1)
                     return [l!!p | p<-pos]

乱数関連の巻数の戻り値の方は、IOモナドのようなので表示するためには、>>= 演算で putStrLn アクションに渡さないと表示できない。

問題24　ロトくじの番号を作れ。（1..M までの数字からランダムに N 個の数字を選び出す。）

実行例
Prelude System.Random>diff_select 6 49 >>= print
Prelude System.Random>[23,1,17,33,21,37]

解答
import System.Random
diff_select :: Int -> Int -> IO [Int]
diff_select n to = diff_select' n [1..to]

diff_select' 0 _  = return []
diff_select' _ [] = error "too few elements to choose from"
diff_select' n xs = do r <- randomRIO (0,(length xs)-1)
                       let remaining = take r xs ++ drop (r+1) xs
                       rest <- diff_select' (n-1) remaining
                       return ((xs!!r) : rest)

diff_select の戻り値の型はIO モナドになるので、print 関数に >>= 演算子で渡さないと表示されない。

問題25　リストを元にランダムな配列を作り出す関数を作れ。

実行例
Prelude>rnd_permu "abcdef" >>= print
Prelude>"badcef"

解答
import System.Random

rnd_permu :: [a] -> IO [a]
rnd_permu xs = diff_select' (length xs) xs

diff_select' :: Int -> [a] -> IO [a]
diff_select' 0 _  = return []
diff_select' _ [] = error "too few elements to choose from"
diff_select' n xs = do r <- randomRIO (0,(length xs)-1)
                       let remaining = take r xs ++ drop (r+1) xs
                       rest <- diff_select' (n-1) remaining
                       return ((xs!!r) : rest)

問題26　与えられたリストから n 個の要素を取り出す組み合わせをすべて表示せよ。

実行例
> combinations 3 "abcdef"
["abc","abd","abe",...]

解答
-- Import the 'tails' function
--   > tails [0,1,2,3]
--   [[0,1,2,3],[1,2,3],[2,3],[3],[]]
import Data.List (tails)

-- The implementation first checks if there's no more elements to select,
-- if so, there's only one possible combination, the empty one,
-- otherwise we need to select 'n' elements. Since we don't want to
-- select an element twice, and we want to select elements in order, to
-- avoid combinations which only differ in ordering, we skip some
-- unspecified initial elements with 'tails', and select the next element,
-- also recursively selecting the next 'n-1' element from the rest of the
-- tail, finally consing them together

-- Using list comprehensions
combinations :: Int -> [a] -> [[a]]
combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

問題27　集合を互いに素な n 個の部分集合に分割する方法をすべて挙げよ。

実行例
P27> group [2,3,4] ["aldo","beat","carla","david","evi","flip","gary","hugo","ida"]
[[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]],...]
(altogether 1260 solutions)

27> group [2,2,5] ["aldo","beat","carla","david","evi","flip","gary","hugo","ida"]
[[["aldo","beat"],["carla","david"],["evi","flip","gary","hugo","ida"]],...]
(altogether 756 solutions)

解答
combination :: Int -> [a] -> [([a],[a])]
combination 0 xs     = [([],xs)]
combination n []     = []
combination n (x:xs) = ts ++ ds
  where
    ts = [ (x:ys,zs) | (ys,zs) <- combination (n-1) xs ]
    ds = [ (ys,x:zs) | (ys,zs) <- combination  n    xs ]

group :: [Int] -> [a] -> [[[a]]]
group [] _ = [[]]
group (n:ns) xs = do
    (g,rs) <- combination n xs
    gs      <- group ns rs
    return $ g:gs

問題28　リストのリストをサブリストの長さでソートせよ。

実行例
lfsort ["abc", "de", "fgh", "de", "ijkl", "mn", "o"]
["ijkl","o","abc","fgh","de","de","mn"]

解答
import List
comparing p x y = compare (p x) (p y)
lfsort lists = sortBy (comparing frequency) lists where
    lengths = map length lists
    frequency list = length $ filter (== length list) lengths