Haskell練習

Haskell wupc k2pc gcj

今までHaskellで解いてみたいくつかの問題をまとめてみました。

WUPC2012 A - 招待状

与えられた2つの日付の差を求める問題。javaみたいにCalendarクラスみたいなのがないかな？と調べてみたらありました。

import A (B) でモジュールAの関数Bが使えるようになります。import AでモジュールAの全ての関数が使えるようになります。
import Data.Time.Calendar
で日付計算が簡単に出来ます。
fromGregorianで与えられた日付をカレンダーインスタンスにし、diffDays関数で差分を求めて終わり。カレンダーは自分で実装すると結構面倒なので、便利な機能です。
ちなみに、map関数は、map A BでBのリストの各要素にAの関数を適用して、新しいリストを作る関数。
ソースコード

K2PC2012 C - 紅茶(Tea)

規則のあるtuple列の問題。
　
　アルゴリズムとしては「成分和がnになるtupleはS(n - 2) + 1からS(n - 1)番目までである（S(n)は1〜nまでの自然数の和）」という性質を使えばよいのでそんなに難しくはないです。あとはtuple数が10^8と多いので、探索は二分探索で行わないと駄目。
ソースコード

まず、注意すべきは、Haskellにはforやwhileなどのループ構文がないこと。僕はループ構文が無い言語を知らなかったので、これは驚愕でした。
Haskellでループを書くにはどうしたらいいかというと、再帰を使います。num2Tuple関数がn番目のtupleを求める関数でループで二分探索をします。where構文を使うと、constですが、変数を使うことが出来ます。

ssum n はS(n)を求める関数で、dev n1 n2はn1 / n2を求める関数です。これらの関数の実装の際に、始め型エラーが無くならなくて意味が分からなかったのですが、Haskellでは、整数 / 整数の計算は出来ないようです（参考）。

GCJ2011 練習問題 問題A. 数珠繋ぎ

シミュレーション問題。でもちょっと工夫すると簡単に答えが出せます。
k = 2^(n - 1) mod 2^n
を満たすとき、ONでそれ以外はOFFとなります。

ソースコード

import Control.Applicative

doIt c max list
	| c > max =  return()
	| otherwise = do
		[n , k] <- map (read :: String -> Int) . words <$> getLine
		putStrLn $ "Case #" ++ show c ++ ": "  ++ ( check n k list )
		doIt (c + 1) max list
		
check n k list
	| k == 0 = "OFF"
	| k `mod` list !! n == list !! n - 1 = "ON"
	| otherwise = "OFF"


main = do
	n <- (read :: String -> Int) <$> getLine
	doIt 1 n [2 ^ x | x <- [0..30]]

Control.Applicativeをインポートすると、関数適用「fmap A B」を「A <$>B」と書くことが出来ます。
また、HaskellではAをBで割った余りは「A % B」ではなく、「A `mod` B」と書くようです。
Haskellにはリストの内包表記があり、[0..n]と書くと、[0,1,2,..,n]のリストが出来、[2 ^ x | x <- [0..30]]と書くと、[1,2,4,8,16,...,2^30]のリストが出来ます。便利。


Haskellは複雑な処理も結構短く書くことが出来ますね。