すごいHaskell読書会 in 大阪 #2 練習問題解いてみた

sugoih2.hs

{- 以下の関数を定義しなさい
* 与えられた文字列を大文字に変換する関数
* 与えられた文字列から空白を除去する関数
* リスト lst1 が lst2 を含んでいるかどうかを判定する関数
* 配列から重複する要素を削除する関数
* 与えられた正数から二進表記の文字列を得る関数
-}


import Data.Char
import Data.List
import Control.Applicative
  
  
upperCase :: String -> String
upperCase = map toUpper

                
removeSpaces :: String -> String
removeSpaces = concat . words


cover :: Eq a => [a] -> [a] -> Bool
cover lst1 lst2 = or $ map (\s -> lst1 `isPrefixOf` s) $ tails lst2

uniq :: Eq a => [a] -> [a]
uniq = foldr (\x acc -> if x `elem` acc then acc else x:acc) []

binExp :: (Integral a, Show a) => a -> String
binExp 0 = "0"
binExp 1 = "1"
binExp n = (binExp $ n `div` 2) ++ (show $ n `mod` 2)


{- ハノイの塔
三つのポール 1 2 3 の内、ポール 1 に n 個の円盤が乗っているとし、すべての円盤をポール 2 に移動する手順を返す関数を書け。
手順はポール 1 からポール 2 に円盤を移動する場合にペア (1, 2) と表記し、そのようなペアのリストを手順と見なす

ghci> hanoi 3
[(1, 2), (1, 3), (2, 3), (1, 2), (3, 1), (3, 2), (1, 2)]
-}

hanoi :: Int -> [(Int, Int)]
hanoi n = hanoi' n 1 2 3
  where
    hanoi' 0 _ _ _ = []
    hanoi' n' from to other = (hanoi' (n'-1) from other to) ++ [(from, to)] ++ (hanoi' (n'-1) other to from)


{- フィボナッチ数
第 n 番目のフィボナッチ数を得る関数を書け、ただし 1番目と 2番目のフィボナッチ数は 1 とする

ダメな例
fib :: Integer -> Integer
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)
fib 50 くらいで還らぬ人となります。
-}

fib :: Int -> Int
fib i = snd $ iterate (\(a, b) -> (b, a+b)) (1, 1) !! i

pathCount :: Int -> Int -> Int
pathCount n k = (n+k) `comb` n
  where comb _ 0 = 1
        comb a k
          | a == k = 1
          | otherwise = (a-1) `comb` k  + (a-1) `comb` (k-1)