結城浩のHaskell日記 RSSフィード

2006-06-03

zipWith関数 zipWith関数 - 結城浩のHaskell日記 を含むブックマーク

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith関数は二引数関数を使って二つのリストを混ぜ合わせます。

zipWith'を自作(再帰版)。

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f [] _ = []
zipWith' f _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

高階関数を使え」というアドバイスに従い、mapを使う。

zipは[a] -> [b] -> [(a, b)]で、uncurryは(a -> b -> c) -> (a, b) -> c なのでmapが使えるようになる。

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = map f' xys
  where
    f' = uncurry f
    xys = zip xs ys

赤黒木とTreap 赤黒木とTreap - 結城浩のHaskell日記 を含むブックマーク

Programming:玉手箱:その他の赤黒木のbalance関数に見とれてしまいました。回転を宣言的に表現しているようですごいなあと思います。

それではTreapはどうだろうと思って検索してみるとOnTreapsAndRandomizationというページが見つかりました。こちらでは明示的に回転していますね。赤黒木のようにシンプルなbalance関数(treapify?)が書けるように思いますが、いかがでしょうね。

(結城はまだ書けない……)

Haskellリングに参加 Haskellリングに参加 - 結城浩のHaskell日記 を含むブックマーク

Haskellリングに参加しました。

LazyLines LazyLines - 結城浩のHaskell日記 を含むブックマーク

LazyLinesは青木さんがHaskellで書いたWikiです。

『ふつうのHaskellプログラミング』サポート――LazyLinesの入手とインストールから、LazyLinesのソースコードをダウンロードし、ぱらぱらと眺めてみる。

  • 小さい関数(たとえばescapeとかulとか)は読めるけれど、大きな関数(たとえばatomicWriteFile)はまだあまり読めない。
  • お、#if WIN32 ... というのがある。そういえば、C++のプリプロセッサを通すというオプションがGHCにあったっけ。
  • そういえば、関数名にはプライム ' が使えるんだった。自作関数のときはmyXXXXではなくXXXX'にすれば見やすいな。

ふつケル写経会 ふつケル写経会 - 結城浩のHaskell日記 を含むブックマーク

nskj77さんの日記に「ふつケル写経会のお知らせ」というのがアナウンスされていました。結城は行けませんけれど、宣伝しておきます。

IntとInteger IntとInteger - 結城浩のHaskell日記 を含むブックマーク

IntはGHCなら32ビット。Integerは制限なし。

では冪乗の無限リストで確認しましょう。

powers :: Int -> [Int]
powers n = powersFrom 1 n
  where
    powersFrom p n = p:powersFrom (p * n) n

実行結果です。この間おしえてもらった!!も使おう!!

*Main> take 10 $ powers 2
[1,2,4,8,16,32,64,128,256,512]
*Main> take 20 $ powers 2
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288]
*Main> :i (!!)
-- !! is a variable
(!!) :: forall a. [a] -> Int -> a
*Main> powers 2 !! 10
1024
*Main> powers 2 !! 20
1048576
*Main> powers 2 !! 30
1073741824
*Main> powers 2 !! 31
-2147483648
*Main> powers 2 !! 32
0

次はIntegerバージョン。

powers :: Integer -> [Integer]
powers n = powersFrom 1 n
  where
    powersFrom p n = p:powersFrom (p * n) n

実行結果です。

*Main> powers 2 !! 30
1073741824
*Main> powers 2 !! 31
2147483648
*Main> powers 2 !! 32
4294967296
*Main> powers 2 !! 100
1267650600228229401496703205376
*Main> powers 2 !! 1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

すごい!!

(&&)関数と(||)関数 (&&)関数と(||)関数 - 結城浩のHaskell日記 を含むブックマーク

Haskellの(&&)関数と(||)関数はショートカットになるのだろうか。

myAndAnd :: Bool -> Bool -> Bool
myAndAnd True b = b
myAndAnd False b = False

こうかいたらショートカットになるはず。

でも、どうやって調べる?

testTrue = do putStrLn "evaluated"
              return True

これだとJust Trueが帰って来ちゃう。うう。

not関数 not関数 - 結城浩のHaskell日記 を含むブックマーク

not関数はBool->Boolで、論理反転です。

mynotを作ります。

mynot :: Bool -> Bool
mynot True = False
mynot False = True

all関数 all関数 - 結城浩のHaskell日記 を含むブックマーク

all関数は述語(a -> Bool)とリスト[a]が与えられて、すべての要素が述語を満たすかどうかを調べます。

myallを作ってみます。まずは再帰的に。

myall :: (a -> Bool) -> [a] -> Bool
myall f [] = True
myall f (x:xs) | f x = myall f xs
myall f _ = False

実行結果です。

*Main> myall even [1..5]
False
*Main> myall even [0,2..100]
True
*Main> myall even [2]
True
*Main> myall even [1]
False
*Main> myall even []
True

「ユーキ、高階関数を使え」とid:nobsunからアドバイスのあったとおり、高階関数を使ってみましょう。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = null $ dropWhile f xs

次は無理やり。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = (length xs) == (length $ takeWhile f xs)

次はド・モルガンの法則を使って作ったもの。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = not $ any (not . f) xs

次は無理矢理mapを使ったもの。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = null $ dropWhile id $ map f xs

考えてみればこれでよいか。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = and $ map f xs

andは[Bool]->Boolで、&&はBool->Bool->Boolなので、同じことがfoldrでできるはず。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = foldr (&&) True (map f xs)

mapのお仕事をfoldrに任せることもできそうだ。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = foldr foo True xs
  where
    foo x = (&&) (f x)

fooは関数合成になりそうだ。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = foldr foo True xs
  where
    foo = (&&) . f

fooはなくせそうだ。

myall :: (a -> Bool) -> [a] -> Bool
myall f xs = foldr ((&&) . f) True xs

xsもなくせそうだ。

myall :: (a -> Bool) -> [a] -> Bool
myall f = foldr ((&&) . f) True

__2006/06/04 00:54powers n = iterate (*n) 1

トラックバック - http://haskell.g.hatena.ne.jp/hyuki/20060603