2008年05月12日

[Haskell] もう一つの数学パズル

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
4桁の数値を順序を逆転させた数値(例えば、5432の場合は2345が逆転させた数値)で割ったときに、割り切れる4桁の数を求めよ。
(つまり、5432 / 2345 が割り切れればよい)
ただし、商が1のものや、割る数が4桁でないものは除外する。

この問題をHaskellで解いてみる。

import System
import Data.List

main = do print $ workout [1000..9999]

workout :: [Integer] -> [(Integer,Integer)]
workout nums = filter (\(a,b) -> (a /= b) && (b >= 1000) && (a `mod` b == 0)) maketuplelist
where
maketuplelist = zip nums ( map revnum nums )
revnum = (read :: String -> Integer) . reverse . show


別の方法も考えてみる。
今度は、タプルを使わないようにしてみた。

main = mapM_ print [n | n <- [1000..9999], cond n]

cond n = (n `mod` r == 0) && (n /= r) && (r >= 1000)
where
r = read $ reverse $ show n

ただ、ここで疑問。
r は、condの条件式の中で、3回も出てくるが、3回計算されるのだろうか?  

Posted by gushwell at 22:57Comments(2)TrackBack(1)

2008年05月01日

[Haskell] 簡単な数学パズルを解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
数学パズル
3桁の数値とその数値を2乗した値の各数字が1から9までの数字で構成されるような3桁の数値をすべて求めるプログラムを作成せよ。
例えば 763*763=582169 となるが、これは、1,2,3,5,6,7,8,9 からなり、4が抜けているからダメ。

これも、数年前に新人君向けの作ったC#の問題だが、Haskellで解いてみる。

戦略は、
[(100,10000),(101,10201),(102,10404),(103,10609)...(999,998001)]
といったタプルのリストを作成し、filter関数で条件にあうタプルを抜き出す。
というやり方でコードを書いてみることにする。

まずは、タプルのリストを作成する関数 makrtuplelist
maketuplelist :: [Integer] -> [(Integer,Integer)]
maketuplelist nums = zip nums $ map (\n -> n * n) nums

nums には、[100..999]のリストを渡す。
mapで、2乗のリストを作成し、zip関数で、numsとのタプルのリストを作る。

条件に一致するかどうかを判定する関数judgeを作成

judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"

タプルを受け取り、文字列として連結し、ソートした結果が、"123456789"と一致していれば、条件に一致しているとみなしている。
別の解法も考えられるが、ここは最もお手軽な方法を選択。

そして、条件に一致するタプルだけを抜き取る関数 workoutを作る。
workout :: [Integer] -> [(Integer,Integer)]
workout = filter jugde . maketuplelist

関数合成を使ってみた。
関数連鎖を使えば、
workout nums = filter jugde $ maketuplelist nums

だ。
まだ、関数連鎖は慣れていない。いったん、関数連鎖の形にしてからでないと、関数合成のコードを書くことができないです。

そして、最後が、main関数
main = do print $ workout [100..999]

出来あがったコードは、以下のようになる。

import System
import List
 
main = do print $ workout [100..999]
 
workout :: [Integer] -> [(Integer,Integer)]
workout = filter jugde . maketuplelist
 
maketuplelist :: [Integer] -> [(Integer,Integer)]
maketuplelist nums = zip nums $ map (\n -> n * n) nums
 
judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"

さらに、where を使ってみると、

import System
import List
 
main = do print $ workout [100..999]
 
workout :: [Integer] -> [(Integer,Integer)]
workout nums = filter judge maketuplelist
where
judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"
 
maketuplelist = zip nums $ map (\n -> n * n) nums

となる。このほうが、関数間の呼び出し関係が視覚的に分かるので良いかな。
Haskellで面白いのは、字下げそのものが文法的に意味を持つ、というところですね。

このパズルの答えを知りたい人は、自分で動かしてみてください。
  
Posted by gushwell at 21:12Comments(7)TrackBack(1)

2008年04月26日

[Haskell] 型チェックは意外と厳しい

   このエントリーをはてなブックマークに追加 Clip to Evernote
getAverage :: (Fractional a) [a] -> a
getAverage xs = div (sum xs) (length xs)

という関数を書いてみた。

最初の行では、aという型がFractionalクラスに属していることを示している。
Fractionalクラスは、小数点を扱える数値型。

でもなぜかコンパイルエラーになった。なんか型が一致しないようだ。
なぜ?

sum xs / (length xs)

って書いてもだめ。

調べてみると、この場合割り算の分子は、Fractionalである必要があるので、
fromIntegral で型変換をする必要がある。

getAverage xs = sum xs / fromIntegral (length xs)

C#のキャストのようなものかな。

Haskellの型チェックって見た目以上に厳しいようだ。  
Posted by gushwell at 21:44Comments(0)TrackBack(0)

2008年04月23日

[Haskell] foldl関数の動き

   このエントリーをはてなブックマークに追加 Clip to Evernote
Haskellのmaximum関数は,
maximum, minimum :: (Ord a) => [a] -> a
maximum [] = error "Prelude.maximum: empty list"
maximum xs = foldl1 max xs

という定義らしい。
ここで出てきた foldl1についても調べてみる。
foldl1の定義は、
foldl1           :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error "Prelude.foldl1: empty list"
foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

だ。

重要なのは、
 foldl f z (x:xs) =  foldl f (f z x) xs

の部分。
 foldl func z (x:xs)

という関数呼び出しのコードだと、
 func z x

の値を新たな z ととし、xs を新たな第3引数のリストとし、再帰的にfoldlを呼びだすというものだ。
こうすることで、f の結果を保持しながら、リストを順に処理できることになる。

具体的に見てみよう。たぶん以下のように推移するんだと思う。
maximum [1,5,3,4]
-> foldl1 max [1,5,3,4]
-> foldl max 0 [1,5,3,4]
-> foldl max (max 0 1) [5,3,4]
-> foldl max 1 [5,3,4]
-> foldl max (max 1 5) [3,4]
-> foldl max 5 [3,4]
-> foldl max (max 5 4) [4]
-> foldl max 5 [4]
-> foldl max (max 5 4) []
-> foldl max 5 []
-> 5

僕にはとても思いつきません。

  
Posted by gushwell at 23:27Comments(0)TrackBack(0)

2008年04月22日

[Haskell] 指定した長さより長い文字列を取り出す

   このエントリーをはてなブックマークに追加 Clip to Evernote
標準入力から指定した長さよりも長い行だけを
標準出力へ複写するプログラムを書け。
 
main = do {
cs <- getContents;
args <- getArgs;
putStrLn $ unlines $ selectlines (read $ head args) $ lines cs
}

selectlines :: Int -> [String] -> [String]
selectlines n list = filter (\s -> (length s) >= n) list


このコードでのポイントは filter関数かな。
関数(ここではラムダ式)で与えた条件に一致するものだけを返す関数。
この場合は、文字列のリストから、長さが n 以上の文字列だけを
抜き出すというもの。

map と filterがあれば、随分といろんなことが出来そう。

C#のLINQではSelectとWhereに対応しているような感じですね。

main の do 記法は、いつもとちょっと変えて、{ } を使ってC#風に
書いてみた。
僕には、この方がしっくりきますね。
{ }を使わなければ、

main = do cs <- getContents
args <- getArgs
putStrLn $ unlines $ selectlines (read $ head args) $ lines cs

  
Posted by gushwell at 22:51Comments(0)TrackBack(0)

2008年04月21日

[Haskell] 月の日数を求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
指定した月の日数を求める関数を作れ。
ただし、うるう年は考慮しなくてもよい。

やりたいことは実に単純なんだけど、リストのn番目を求めるのってどうやるんだろうか?
調べたら !! 演算子があるということがわかった。

なるほど、それならば、

daysOfMonth :: Int -> Int
daysOfMonth n = days !! (n-1)

days :: [Int]
days = [31, 28, 31, 30, 31, 30, 31,31, 30, 31, 30, 31]

でOKかな。

自分で、!! 演算子と同じことをやる関数を作るとするとどうやるのかも考えてみた。

valueAt :: Int -> [Int] -> Int
valueAt n (x:xs)
| n == 0 = x
| otherwise = valueAt (n-1) xs

とこんな感じか。
随分とHaskellの再帰処理にも慣れてきたようだ。

ところで、今気がついたんだけど、Haskellで例外処理って
どう書くのかな?
これこは、明日以降の課題ですね。
  
Posted by gushwell at 22:59Comments(0)TrackBack(0)

2008年04月20日

[Haskell] maximumを使わずに最大値を求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
標準関数 max, maximum を使わずに、最大値を求める関数を書け。

最初に書いたコードはこれ。

maxnum :: [Integer] -> Integer
maxnum [a] = a
maxnum (x:xs)
| x > maxnum xs = x
| otherwise = maxnum xs

ガードを使って書いてみた。
2回同じ maxnum xs が出てどうなんだろう?って思ったが、動くことには動いた。でも、ものすごく遅い。

次に書いたのがこちら。

maxnum :: [Integer] -> Integer
maxnum (x:xs) = maxnum_ x xs
 
maxnum_ :: Integer -> [Integer] -> Integer
maxnum_ n [] = n
maxnum_ n (x:xs) = maxnum_ (maxn n x) xs
 
maxn :: Integer -> Integer -> Integer
maxn a b = if a > b then a else b

これならば、速度的には問題ないようだ。
でも、意外と手こずった。

先頭の要素を2つ取り出すのに、2段階に関数を定義しなければならないのが厄介だが、これしかやり方が思いつかない。
foldl系の関数を使えばもっと簡単になるが、foldl系の関数も中身は同じようなことをやっているので、本質的には変わらない。
  
Posted by gushwell at 10:55Comments(0)TrackBack(0)

2008年04月15日

[Haskell] ローテイト関数を作る

   このエントリーをはてなブックマークに追加 Clip to Evernote
与えられたリスト内の要素を右にスライスする rrotate、左にスライスする lrotate関数を作れ。

新人君用のC#の問題は、画面フォーム上のtextBoxの内容を、スライドさせるというものだったが、内容を変更。

rrotateの場合、[1,2,3,4,5]を与えれば、[5,1,2,3,4]が返る。

lrotateは簡単だ、

lrotate :: [a] -> [a]
lrotate [] = []
lrotate (x:xs) = xs ++ [x]

先頭要素を、後ろにくっつければ良い。++ は、リスト同士の結合演算子。

一方、rrotateは、手こずった。
なんとかできたのが、以下のコード。

rrotate :: [a] -> [a]
rrotate [] = []
rrotate list = last list : take (length list - 1) list

最後の要素を取り出し、: 演算子を使い最後を除いたリストと結合している。
うーーん、美しくない。
もっと違った方法があると思うのだが...

で考えたのが、最後の要素を除いたリストを取得する lead関数を作るというもの。

rrotate :: [a] -> [a]
rrotate [] = []
rrotate xs = last xs : lead xs

と書ければ、コードの意図が読み取りやすくなる。
そこでtakeや、length関数を使わずに、lead関数を書いてみる。

lead :: [a] -> [a]
lead [] = []
lead (x:[]) = []
lead (x:xs) = x : lead xs

これも、いまいちだな。まあしょうがないか。
  
Posted by gushwell at 21:11Comments(3)TrackBack(0)